void quicksort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
1 hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--; if (left != right)
{
numbers[left] = numbers[right]; left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++; if (left != right)
{
numbers[right] = numbers[left]; right--; } }
numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot)
q_sort(numbers, left, pivot-1); if (right > pivot)
q_sort(numbers, pivot+1, right); }
Анализ алгоритма[3]. Ожидаемое число обменов равно (п - 1п)1в. Если предположить, что в качестве разрешающего элемента всегда выбирается медиана, то каждое разделение разбивает массив на две равные части, и число проходов, необходимых для сортировки, равно log п. Тогда общее число сравнений составит и-log «, а общее число обменов — (w/6)-log п. Вероятность попадания на медиану составляет 1п. Однако, если граница выбирается случайным образом, эффективность алгоритма в среднем хуже оптимального варианта лишь в 2-In 2 раз. Основной недостаток алгоритма — недостаточно высокая производительность при небольших п.