Сортировка

1.

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

2.

Формулировка задачи

3.

Оценка алгоритма сортировки
• Время — основной параметр, характеризующий быстродействие алгоритма.
Называется также вычислительной сложностью. Для упорядочения важны
худшее, среднее и лучшее поведение алгоритма в терминах мощности
входного множества A. Если на вход алгоритму подаётся множество A, то
обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n
* log n) и плохое поведение — это O(n2). Идеальное поведение для
упорядочения — O(n). Алгоритмы сортировки, использующие только
абстрактную операцию сравнения ключей, всегда нуждаются по меньшей
мере в сравнениях.
• Память — ряд алгоритмов требует выделения дополнительной памяти под
временное хранение данных. Как правило, эти алгоритмы требуют O(log n)
памяти. При оценке не учитывается место, которое занимает исходный
массив и независящие от входной последовательности затраты, например,
на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы
сортировки, не потребляющие дополнительной памяти, относят к
сортировкам на месте.

4.

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

5.

Сортировка пузырьком. Алгоритм
Алгоритм состоит из повторяющихся проходов по сортируемому
массиву. За каждый проход элементы последовательно
сравниваются попарно и, если порядок в паре неверный,
выполняется перестановка элементов. Проходы по массиву
повторяются N – 1 раз или до тех пор, пока на очередном
проходе не окажется, что обмены больше не нужны, что
означает — массив отсортирован. При каждом проходе алгоритма
по внутреннему циклу очередной наибольший элемент массива
ставится на своё место в конце массива рядом с предыдущим
«наибольшим элементом», а наименьший элемент перемещается
на одну позицию к началу массива («всплывает» до нужной
позиции, как пузырёк в воде — отсюда и название алгоритма).

6.

Сортировка пузырьком. Алгоритм
ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1
F=0
ЦИКЛ ДЛЯ I=0 ДО N-1-J ШАГ 1
ЕСЛИ A[I] > A[I+1] ТО ОБМЕН A[I],A[I+1]:F=1
СЛЕДУЮЩЕЕ I
ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА
СЛЕДУЮЩЕЕ J

7.

Шейкерная сортировка
Сортировка перемешиванием, или Шейкерная сортировка, или
двунаправленная (англ. Cocktail sort) — разновидность пузырьковой
сортировки. Анализируя метод пузырьковой сортировки, можно отметить два
обстоятельства.
• Во-первых, если при движении по части массива перестановки не
происходят, то эта часть массива уже отсортирована и, следовательно, её
можно исключить из рассмотрения.
• Во-вторых, при движении от конца массива к началу минимальный элемент
«всплывает» на первую позицию, а максимальный элемент сдвигается
только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой
сортировки. Границы рабочей части массива (то есть части массива, где
происходит движение) устанавливаются в месте последнего обмена на
каждой итерации. Массив просматривается поочередно справа налево и
слева направо.

8.

Шейкерная сортировка. Алгоритм
Будем идти не только слева направо, но и справа налево.
Будем поддерживать два указателя begin и end,
обозначающих, какой отрезок массива еще не отсортирован.
На очередной итерации при достижении end вычитаем из
него единицу и движемся справа налево, аналогично, при
достижении begin прибавляем единицу и двигаемся слева
направо. Асимптотика у алгоритма такая же, как и у
сортировки пузырьком, однако реальное время работы
лучше.

9.

Сортировка вставками

10.

Сортировка вставками. Алгоритм
Псевдокод:
for j = 2 to A.length do
key = A[j]
i = j-1
while (int i >= 0 and A[i] > key) do
A[i + 1] = A[i]
i=i-1
end while
A[i+1] = key
end

11.

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

12.

Сортировка слиянием. Алгоритм
Для решения задачи сортировки эти три этапа выглядят так:
1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым
алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один.
1.1. — 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер
массива не достигнет единицы.
3.1. Соединение двух упорядоченных массивов в один.
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в
результирующий массив. Счётчики номеров элементов результирующего массива и подмассива,
из которого был взят элемент, увеличиваем на 1.
3.3. «Прицепление» остатка.
Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго
подмассива в результирующий массив.

13.

Сортировка слиянием. Алгоритм
Процедура слияния
Итеративный алгоритм

14.

Быстрая сортировка
Быстрая сортировка, сортировка Хоара (англ. quicksort), часто
называемая qsort (по имени в стандартной библиотеке языка Си)
— алгоритм сортировки, разработанный английским
информатиком Тони Хоаром во время своей работы в МГУ в 1960
году.
Один из самых быстрых известных универсальных алгоритмов
сортировки массивов: в среднем O(n * log(n)) обменов при
упорядочении n элементов; из-за наличия ряда недостатков
на практике обычно используется с некоторыми
доработками.

15.

Быстрая сортировка. Алгоритм
Общая идея алгоритма состоит в следующем:
• Выбрать из массива элемент, называемый опорным. Это может быть любой
из элементов массива. От выбора опорного элемента не зависит
корректность алгоритма, но в отдельных случаях может сильно зависеть его
эффективность.
• Сравнить все остальные элементы с опорным и переставить их в массиве
так, чтобы разбить массив на три непрерывных отрезка, следующих друг за
другом: «элементы меньшие опорного», «равные» и «большие».
• Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту
же последовательность операций, если длина отрезка больше единицы.
На практике массив обычно делят не на три, а на две части: например,
«меньшие опорного» и «равные и большие»; такой подход в общем случае
эффективнее, так как упрощает алгоритм разделения.

16.

Быстрая сортировка. Алгоритм
В наиболее общем виде алгоритм на псевдокоде (где A —
сортируемый массив, а low и high — соответственно, нижняя и
верхняя границы сортируемого участка этого массива) выглядит
следующим образом:
algorithm quicksort(A, low, high) is
if low < high then
p:= partition(A, low, high)
quicksort(A, low, p)
quicksort(A, p + 1, high)

17.

Быстрая сортировка. Алгоритм
Здесь предполагается, что массив A передаётся по ссылке, то есть
сортировка происходит «на том же месте», а неописанная функция
partition возвращает индекс опорного элемента. Для выбора
опорного элемента и операции разбиения существуют разные
подходы, влияющие на производительность алгоритма.

18.

Быстрая сортировка. Алгоритм
В ранних реализациях, как правило, опорным выбирался первый
элемент, что снижало производительность на отсортированных
массивах. Для улучшения эффективности может выбираться средний,
случайный элемент или (для больших массивов) медиана первого,
среднего и последнего элементов. использует два индекса (один в
начале массива, другой в конце), которые приближаются друг к другу,
пока не найдётся пара элементов, где один больше опорного и
расположен перед ним, а второй меньше и расположен после. Эти
элементы меняются местами. Обмен происходит до тех пор, пока
индексы не пересекутся. Данная схема также показывает эффективность
в O(n2), когда входной массив уже отсортирован. Сортировка с
использованием данной схемы нестабильна. Следует заметить, что
конечная позиция опорного элемента необязательно совпадает с
возвращённым индексом.

19.

Быстрая сортировка. Алгоритм
algorithm partition(A, low, high) is
pivot:= A[(low + high) / 2]
i:= low
j:= high
loop forever
while A[i] < pivot
i:= i + 1
while A[j] > pivot
j:= j - 1
if i >= j then
return j
swap A[i++] with A[j--]