Быстрая сортировка Хоара

Алгоритмы сортировки

Сортировка простым выбором осуществляется так.

Просмотрим элементы массива от первого до последнего, определим элемент с наименьшим значением, и обменяем это значение с первым. Потом так же выберем наименьшее значение среди A [2]... A [n] и обменяем его со значением A [2], потом выберем следующее наименьшее и обменяем с A [3] и т.п..

Пузырьковая сортировка.

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

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

Быстрая сортировка Хоара.

Данный алгоритм относится к распределительному и обеспечивает показатели эффективности O (N * log2 (N)) даже при наихудшем исходном распределении. Используются два индекса - i и j - с начальными значениями 1 и N соответственно. Ключ K [i] сравнивается с ключом K [j]. Если ключи удовлетворяют критерию упорядоченности, то индекс j уменьшается на 1 и делается следующее сравнение. Если ключи не удовлетворяют критерию, то записи R [i] и R [j] меняются местами. При этом индекс j фиксируется и начинает меняться индекс i (увеличиваться на 1 после каждого сравнения). После следующей перестановки фиксируется i и начинает меняться j и т.д. Проход заканчивается, когда индексы i и j становятся равными. Запись, находящегося на позиции встречи индексов, находится на своем месте в последовательности. Эта запись делит последовательность на два подмножества. Все записи, расположенные слева от нее имеют ключи, меньшие чем ключ этой записи, все записи справа - больше. Тот же самый алгоритм применяется к левой подмножества, а затем в правой. Записи подмножества распределяются по двум еще меньших подмножеств и т.д., и т.д. Распределение заканчивается, когда полученная подмножество будет состоять из единственного элемента - такая подмножество уже упорядоченной.

·
Сортировка слиянием (Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма: O(n log n). Требуется O(n) дополнительной памяти.

· Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма: O(n log n). Требуется O(n) дополнительной памяти.

· Сортировка Timsort

(англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: O(n log n). Требуется O(n) дополнительной памяти. Разработан для использования в языке Python ^[4].