635
правок
Изменения
→Улучшенная быстрая сортировка
Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может
привести к существенному повышению эффективности быстрой сортировки. Данная реализация осуществляет разделение по медиане из первого, Функция median возвращает индекс среднего элемента в массиве. После этого он и последнего элементов крайний правый элемент массиваменяются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной <tex>M = 11</tex> и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется [[Сортировка вставками | сортировка вставками]].
'''const int''' M = 10
'''if''' (r - 1 <tex> \leqslant </tex> M)
'''return'''
'''int''' i = partition(l + 1, r - 1)
quicksort(a, l, i - 1)
