Сортировка вставками
Алгоритм сортировки вставками: добавляем элементы один за другим к отсортированной части массива. Именно таким способом обычно сортируют карты: держа в левой руке уже упорядоченные карты и взяв правой рукой очередную карту, мы вставляем ее в нужное место, сравнивая с имеющимися. Запишем этот алгоритм в виде процедуры.
Пусть необходимо отсортировать массив А из n элементов. Последовательность сортируется на месте без дополнительной памяти. Помимо массива мы используем только 1 дополнительную ячейку памяти.
После выполнения процедуры массив упорядочен по возрастанию.
insertionSort(element_type a[], int n)
{
element_type key;
int i, j;
for(j=1; j < n; j++)
{
key=a[j];
// берем элемент а[j] и сдвигаем идущие
// перед ним и большие его по величине
// элементы вправо, освобождая место
// для взятого элемента
for( i = j-1; i>=0 && a[i]>key ; i-- )
a[i+1]=a[i];
a[i+1]=key;
// элемент помещается
// на освобожденное место
} // for j
}
Временная сложность алгоритма сортировки вставками О(n2)
Быстрая сортировка
Быстрая сортировка Хоара – алгоритм с временем выполнения О(n log n) в среднем и О(n2) в худшем случае.
Основан на принципе «разделяй и властвуй».
Сортировка участка а[p],…,a[r] происходит следующим образом
-
элементы массива а представляются так, чтобы любой из элементов a[p],…,a[q] был не больше любого из элементов a[q+1],…,a[r]. Эту операцию будем называть разделением.
-
процедура сортировки рекурсивно вызывается для массивов a[p],…,a[q] и a[q+1],…,a[r].
Void Quicksort( int *a, int p, int r)
{
int q;
if ( p < r)
{
q = Partition(a, p, r);
Quicksort(a, p, q);
Quicksort(a, q+1, r);
}
}
Для сортировки всего массива необходимо выполнить процедуру Quicksort(a, 0 , n-1).
Разбиение массива
int Partition(int *a, int p, int r)
{
int x, i, j;
x = a[p]; i = p-1; j = r+1;
while(1)
{
do
j--;
while(a[j] <= x);
do
i++;
while(a[i]>=x);
if(i<j)
{
temp=a[i]; a[i]=a[j]; a[j]=temp;
}
else
return j;
}
}
В виду сложности дальнейших алгоритмов, разбирать их не будем, ознакомимся с их основными характеристиками.
Пирамидальная сортировка
Свое название алгоритм получил вследствие того, что применяемое здесь частично упорядоченное сортирующее дерево имеет вид «пирамиды».
Время выполнения этого алгоритма в худшем случае такое как и в среднем, и имеет порядок О(n log n).
Хотя этот алгоритм и имеет время выполнения порядка О(n log n) в самом худшем случае, в среднем его время несколько хуже, чем в быстрой сортировке, хотя и имеет тот же порядок.
На практике этот алгоритм полезен тогда, когда надо не сортировать все n элементов списка, а только отобрать k наименьших элементов, и при этом k значительно меньше n.
«Карманная» сортировка
Часто можно получить время сортировки меньшее, чем О(n log n), но необходима дополнительная информация о ключах. Например, что они не повторяются (уникальный ключ).
Предположим, что значения ключей есть целые числа от 0 до n-1.
Пусть
а[] – массив, подлежащий сортировке,
b[] – отсортированный массив той же величины, тогда можно организовать поочередное помещение в массив b записей в порядке возрастания значений ключей следующим образом:
for(i=0; i<n; i++)
b[a[i].key]=a[i];
Этот цикл требует времени порядка О(n) и работает корректно только тогда, когда значения всех ключей различны и являются целыми числами из интервала от 0 до n-1. Это пример простой «карманной» сортировки. «Карманами» для записи являются элементы массива b.