Lec_06

ОБРАБОТКА МАССИВОВ ДАННЫХ

2014		Парамонов А.И.

АЛГОРИТМЫ СОРТИРОВКИ

2

Пусть есть	последовательность {a0,	a1 ... an}
и функция сравнения, которая на любых двух
элементах	этой последовательности	принимает

одно из трех значений: меньше, больше или равно.

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

ai <= ai+1, для всех i от 0 до n.

Задача сортировки имеет множество решений.

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

Оценка алгоритмов сортировки

3

Время сортировки. Основной параметр, характеризующий быстродействие алгоритма.

Память. Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных.

Устойчивость. Сортировка не меняет взаимного расположения равных элементов.

Естественность поведения. Эффективность метода при обработке уже отсортированных, или частично отсортированных данных.

Основные методы сортировки

4

Квадратичные и субквадратичные алгоритмы:

Сортировка выбором(SelectSort)

Сортировка пузырьком(BubbleSort) и ее улучшения

Сортировка простыми вставками(InsertSort)

Cортировка Шелла (ShellSort)

Сравнение времени выполнения сортировок

5

Сортировка пузырьком

6

Идея метода:

шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов.

Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент – аналогия с пузырьком.

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

Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент.

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

Улучшения пузырьковой сортировки

7

Если на каком-либо из проходов не произошло ни одного обмена, то сортировка закончена.

Можно запоминать индекс последнего обмена k и дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.

Можно менять направление следующих один за другим проходов (опускать «тяжелые» элементы и поднимать «пузырьки»). Получившийся алгоритм также называют

"шейкер-сортировкой".

Свойства алгоритма

8

Оценка алгоритма:

Среднее число сравнений и обменов имеют квадратичный порядок роста: O(n2).

Дополнительная память не требуется.

Поведение усовершенствованного (но не базового) метода вполне естественное, т.к. почти отсортированный массив будет отсортирован намного быстрее случайного.

Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.

Сортировка выбором

9

Идея метода – создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1).

Просматривая элементы массива от А[0] до A[n-1], найдем элемент с наименьшим значением и поменяем его с А[0].

Аналогично, для подмассива A[1]…A[n-1].

На i-м шаге выбираем наименьший из элементов подмассива A[i] ... A[n] и меняем его местами с A[i].

Вне зависимости от номера текущего шага i, последовательность A[0]...A[i] является уже упорядоченной

Свойства сортировки выбором

10

Сложность алгоритма:

Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений.

Т.к. количество рассматриваемых на очередном шаге элементов уменьшается на единицу, то общее количество операций:

n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = O(n2)

Значит, т.к. число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Алгоритм не использует дополнительной памяти: все операции происходят сразу.

Метод неустойчив.