Структуры и алгоритмы обработки данных презентация

государственный технологический университет
Кафедра «Системы информатики»

Методы сортировки

определены отношения порядка >, <, ≥, ≤.

Различают упорядочение множества элементов по возрастанию или убыванию.

в зависимости от размерности задачи.

Временная (пространственная) сложность не позволяет определить время (необходимый объем дополнительной памяти) работы алгоритма, но она позволяет оценить динамику роста времени (объема дополнительной памяти), необходимого для работы метода, при увеличении размерности задачи.

можно утверждать, что при увеличении размера задачи (при сортировке - размера массива) в 3 раза время работы алгоритма увеличится в 32=9 раз.

Если операция выполняется за фиксированное число шагов, не зависящее
от размера задачи, то принято писать T(1).

включением.

Для сортировки требуется дополнительная память для размещения отсортированной последовательности.
A1, A2, A3, A4, A5 - исходная последовательность
B1, B2, B3, B4, B5 - отсортированная последовательность

Исходная
память

Дополнительная
память

10

5

80

6

35

подсчетом.

Суть метода заключается в нахождении местоположения элемента в последовательности, т.е. его номер К+1

К ?

Сколько раз каждый
элемент больше других

извлечением.

Отсортированная
последовательность

данных, называемая двоичным деревом (рис 1).
При древесной сортировке нет необходимости каждый раз находить максимальный элемент. В методе поддерживается такой порядок, при котором максимальный элемент всегда будет оказываться в вершине дерева

Рисунок 1. Структура двоичного дерева

- первый элемент помещается в корень дерева (10), затем движение
осуществляется вниз и слева направо (5 и 80, далее 6 и 35)

Дана числовая последовательность: 10, 5, 80, 6, 35. Выполнить
древесную сортировку. Записать цепочку преобразований.

10

5

80

6

35

10

35

80

6

5

80

35

10

6

5

5

35

10

6

80

35

20

10

6

80

6

20

10

35

80

20

6

10

35

80

10

6

20

35

80

Отсортированные элементы обозначены красным цветом

Таким образом, последовательность упорядочена.

методом пузырька.

35

6

80

5

10

- Исходная последовательность

При простом обмене максимальный элемент последовательности за первый проход достигает своего места, т.е. подобно пузырьку «всплывает на поверхность».

В данном примере после первого прохода элемент «80» переместится на свое место

80

35

6

10

5

После второго прохода получим отсортированную последовательность

Выполнить сортировку методом Хоара.

Последовательность отсортирована относительно центра

i

j

i =j

i

j

j

i

Отсортированная последовательность

Просмотр элементов начинается с концов последовательности до тех пор, пока i не станет равнымj

Двойными стрелками показаны обмены

Выполнить сортировку слиянием.

Исходную последовательность необходимо разбить на группы по два элемента.
Внутри каждой группы элементы упорядочить, используя любой метод сортировки и т.д.

Выполнить сортировку обменом

Объединить группы и выполнить сортировку

Объединить группы и выполнить сортировку

Отсортированная последовательность

вырожденным распределением.

Создать цикл, максимальный параметр которого равен максимальному значению исходной последовательности. Затем каждый элемент исходной последовательности сравнивается с параметром цикла. Если элемент последовательности равен параметру цикла, то он записывается в результирующую последовательность.

кафедра «Системы информатики»
Восточно-Сибирский государственный технологический университет

E-mail: bilgaeval@mail.ru