Быстрая сортировка (Quicksort)

Продолжаю просмотр курса «Алгоритмы и структуры данных» от MIT: http://videolectures.net/mit6046jf05_leiserson_lec04/ Сегодня quicksort.

Несколько дополнительных ссылок

http://www.algolist.net/Algorithms/Sorting/Quicksort
http://algolist.manual.ru/sort/quick_sort.php
http://ru.wikipedia.org/wiki/Быстрая_сортировка

Быстрая сортировка заключается в рекурсивном делении сортируемого массива данных на 2 части: большую либо равную значению некоторого элемента, называемого pivot, и меньшую либо равную, чем pivot.

Ниже исходный код на java, демонстрирующий реализацию быстрой сортировки.

    // @see http://www.algolist.net/Algorithms/Sorting/Quicksort
    void quickSort(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
    }

Основная работа выполняется в функции partition. Эта функция выполняет в один проход по массиву разбиение массива на 2 части (как показано на картинке выше).

    // @see http://www.algolist.net/Algorithms/Sorting/Quicksort
    int partition(int arr[], int left, int right)
    {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;

            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }

        return i;
    }

В данном случае в качестве pivot берется элемент из середины массива. Скорость работы быстрой сортировки зависит от значения pivot, выбираемого на каждом шаге. Чтобы глубина рекурсии была наименьшей, нужно чтобы pivot попадал в медианное значение. Тогда на каждом шаге сортировки массив будет делиться на 2 примерно равные части. Это приводит к сложности алгоритма O(n * lg n). В худшем случае, если на каждом шаге в качестве pivot выберется наибольшее или наименьшее значение, тогда глубина рекурсии будет равна n, соответственно будет n рекурсивных проходов по всему массиву размером n. Отсюда сложность в худшем случае достигает O(n^2). В среднем сложность алгоритма O(n * lg n).

Для данного алгоритма при «плохих» случаях глубина рекурсии достигает n, что может вызвать переполнение стека при огромных данных, поэтому для огромных массивов полезно комбинировать Quick Sort с Merge Sort (Сортировка слиянием), а для небольших массивов с Insertion Sort (сортировка вставкой).

Т.е. огромный массив может разбиваться на части с помощью Merge Sort, части некоторого разумного размера могут сортироваться с помощью Quick Sort, а внутри алгоритма QuickSort, в свою очередь, если pivot неудачно разбил массив на большую и маленькую часть, сортировать меньшую часть не рекурсивным Quick Sort, а обычным Insertion Sort. Это позволит получить более оптимизированный алгоритм. Достоинства и недостатки алгоритма хорошо перечислены здесь: http://ru.wikipedia.org/wiki/Быстрая_сортировка. В качестве одного из вариантов улучшения алгоритма, предлагается разбиение не на две, а на три части для уменьшения глубины рекурсии: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

Наилучшая иллюстрация алгоритма деления (функции partition()), здесь: http://www.algolist.net/Algorithms/Sorting/Quicksort. Также полезно посмотреть как это работает под отладчиком:

    @Test
    public void testQuickSort() {
        int a[] = {1, 12, 5, 26, 7, 14, 3, 7, 2, 3};

        quickSort(a, 0, a.length-1);

        System.out.println(Arrays.toString(a));
    }