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

Алгоритм:

• 1. вводятся указатели left и right для обозначения начального и конечного элементов последовательности, а также опорный элемент mid;

• 2. вычисляется значение опорного элемента (left+right)/2, и заносится в переменную mid;

• 3. указатель left смещается с шагом в 1 элемент к концу массива до тех пор, пока arr[left]<mid. А указатель last смещается от конца массива к его началу, пока arr[right]>mid;

• 3. каждые два найденных элемента меняются местами;

• 4. пункты 3 и 4 выполняются до тех пор, пока left<=right.

void qsort(int* arr, const int size)

{

int left = 0;

int right = size - 1;

int mid = arr[size / 2];

do

{

while (arr[left] < mid)

left++;

while (arr[right] > mid)

right--;

if (left <= right) std::swap(arr[left++], arr[right--]);

} while (left <= right);

if (right > 0) qsort(arr, right + 1);

if (left < size) qsort(&arr[left], size - left);

}

худший случай: О( )

средний случай: О(N log(N))

19. Карманная сортировка, поразрядная сортировка.

20. Турнирная сортировка.

Основная идея Tournamentsort заключается в использовании относительно небольшой (по сравнению с основным массивом) вспомогательной кучи, которая выполняет роль приоритетной очереди. В этой куче(дереве) сравниваются элементы на нижних уровнях, в результате чего меньшие элементы поднимаются наверх, а в корень всплывает текущий минимум из той порции элементов массива, которые попали в эту кучу. Минимум переносится в дополнительный массив «победителей», в результате чего в куче происходит сравнение/перемещение оставшихся элементов — и вот уже в корне дерева новый минимум.

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

На каждом из n шагов, требуемых для сортировки массива, нужно log n (двоичный) сравнений. Следовательно, всего потребуется nlog n сравнений, но для представления дерева понадобится 2n - 1 дополнительных единиц памяти.

21. Пирамидальная сортировка.

Пирамидальная сортировка (Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно за n*logn операций при сортировке n элементов.

Его идея состоит в том, что вместо полного дерева сравнения исходный массив a[1], a[2], ..., a[n] преобразуется в пирамиду, обладающую тем свойством, что для каждого a[i] выполняются условия a[i] <= a[2i] и a[i] <= a[2i+1]. Затем пирамида используется для сортировки.

Элементы, для которых существенны ограничения пирамиды: a[n/2], a[n/2-1], ..., a[1] для массивов с четным числом элементов и элементы a[(n-1)/2], a[(n-1)/2-1], ..., a[1] для массивов с нечетным числом элементов Пусть i - наибольший индекс из них. Тогда берется элемент a[i] в построенном дереве и для него выполняется процедура просеивания, состоящая в том, что выбирается ветвь дерева, соответствующая min(a[2i], a[2i+1]), и значение a[i] меняется местами со значением соответствующего элемента.

Флойд предложил метод построения пирамиды без явного построения дерева (хотя метод основан на тех же идеях).