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

qsort.cpp

#include <cstdio>

const int n = 1024;

void qsort(int *array, int begin, int end)
{
    int middle = (begin + end) / 2;                             // Расчет опорного элемента как арифметического среднего
    int base = (array[begin] + array[middle] + array[end]) / 3; // ... первого, центрального и последнего элементов

    int left = begin; // истинные границы отрезка массива нужно помнить для продолжения работы при нестолкновении
    int right = end;  // ... указателей left и right
    for (;;)          // Выполняем цикл до столкновения указателей
    {                 // Инвариант цикла (!) - слева от указателей все элементы меньше опорного, справа - больше
        while (array[left] <= base && (right - left) > 1)   // Двигаем левый указатель, пока элементы меньше опорного
            left += 1;
                                 // Оба движения прерываем при столкновении указателей
        while (array[right] > base && (right - left) >= 1)  // Двигаем правый указатель, пока элементы больше опорного
            right -= 1;
                                 // Здесь совершенно непонятно, почему прервались - из-за столкновения или обычным образом
        if (array[left] > array[right])
        {                        // Меняем элементы под указателями местами, если это требуется
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
                                 // Если прервались из-за столкновения указателей, прерываем цикл. Иначе двигаем их снова
        if ((right - left) <= 1)
            break;
    }

    if ((end - begin) > 1)      // Стоить проверить - а каков наш массив - есть ли смысл бить его на два куска
    {                           // ... Это и есть (!) условие выхода из рекурсии - достижения размеров куска 1-2
        qsort(array, begin, left);  // Досортиртировываем куски
        qsort(array, right, end);
    }
}

int main(void)
{
    int array[n];
    printf("Enter array of integers: (press <Ctrl + D> to stop enter)\n");
    int i = 0;
    while ((scanf("%d", &(array[i])) != EOF) && i < n)
        i++;

    qsort(array, 0, i - 1);

    for (int j = 0; j < i; j++)
        printf("%d ", array[j]);
    putchar('\n');

    return 0;
}