Анализ алгоритма быстрой сортировки.

Быстрая сортировка работает следующим образом: У нас есть массив из n чисел.
1.) Мы выбираем случайное число из массива ( допустим это число p).
2.) Оставшиеся числа мы отсортировываем на две группы: левую (те что меньше p) и правую (и те что больше ).
-Благодаря этому шагу, элемент p теперь стоит там же, где он будет стоять в отсортированном массиве.
-К тому же мы получаем два массива, которые можно сортировать независимо друг от друга. ( поэтому дальше используем рекурсию)
3.) Рекурсивно отсортировываем эти 2 массива по тому же принципу.

Листинг 4.12. Код для алгоритма быстрой сортировки (стр. 161):

void quicksort(item_type s[], int l, int h) {
    int p; /* Индекс элемента-разделителя */

    if (l < h) {                          //если в нашем массиве больше одного элемента
        p = partition(s, l, h);           //берём наш элемент p и сортируем массив на две части
        quicksort(s, l, p - 1);           //дальше сортируем по этому принципу левую часть
        quicksort(s, p + 1, h);           //после правую
    }                          
}

Массив можно разбить на две части относительного опорного элемента p за за один проход и линейное время O(n) с использованием трёх переменных:

1. firsthigh - справа от элемента с этим индексом находятся элементы равные или большие, чем опорный.
2. p - индекс опорного элемента.
3. i - счётчик.

Реализация процедуры разделения приведена ниже:

Листинг 4.13. Код для реализации процедуры разбиения массива на части (стр. 162):

int partition(item_type s[], int l, int h) {
    int i;          /* Счетчик */
    int p;          /* Индекс элемента-разделителя */
    int firsthigh;  /* Позиция для элемента разделителя */

    p = h;          /* Выбираем последний элемент в качестве разделителя */
    firsthigh = l;
    for (i = l; i < h; i++) {
        if (s[i] < s[p]) {
            swap(&s[i], &s[firsthigh]);
            firsthigh++;
        }
    }
    swap(&s[p], &s[firsthigh]);

    return(firsthigh);
}

Опорный элемент p временно становится в конец массива (p = h), а переменная firsthigh в начало массива (firsthigh = l). Затем, запускается цикл по элементам от i до h-1. Если текущий элемент с индексом i будет меньше опорного, то он поменяется местами с элементом с индексом firsthigh, и затем мы увеличим firsthigh = firsthigh + 1. Таким образом элементы которые меньше опорного, будут сдвигаться влево, а граница отодвигаться вправо. В случае, когда проверяемый элемент больше или равен опорного, алгоритм проходит дальше, и элемент остаётся на своём месте (справа от элемента с индексом firsthigh). В конце опорный элемент поменяется местами с элементом на позиции firsthigh, вставая на своё место в отсортированном массиве.

Алгоритмы быстрой сортировки и сортировки слиянием строят рекурсивное дерево и на каждом уровне этого дерева выполняется работы за время O(n). Главная проблема быстрой сортировки - зависимость от выбора опорного элемента:

• Если опорный элемент каждый раз делит массив пополам, то глубина рекурсии составит logn, а итоговая сложность O(nlogn).

• Если в качестве опорного элемента будет каждый раз выбираться наибольший или наименьший элемент массива, то массив будет делится на две части: 1-я пустая, 2-я размером n-1. В итоге на обработку тратиться время O(n), но задача уменьшатся всего на 1 элемент. Итоговая сложность составит O(n^2).

В итоге: в худшем случае быстрая сортировка работает хуже, чем пирамидальная сортировка или сортировка слиянием (обе гарантируют время работы O(nlogn)). Но в среднем, когда поступают случайные данные и сам опорный элемент выбирается случайно, она работает быстрее своих конкурентов.

Интуиция: ожидаемое время исполнения алгоритма быстрой сортировки.

Быстрая сортировка в среднем работает за время O(nlogn), потому что опорный элемент не обязан быть идеальной серединой, достаточно того, чтобы он находился возле центра сортируемого массива. Будем называть разделитель "хорошим", если он находится в центральной половине массива, то есть в диапазоне элементов для сортировки от n/4 до 3n/4. Вероятность выбрать такой элемент - 50%

Рис. 4.7. Демонстрация вероятности взять "хороший" элемент (стр. 163):

Даже если взять элемент на этой границе, самая большая часть после разделение будет размером не более 3n/4. Значит задача уменьшится не на 1 элемент, а сразу на 25%.

Чтобы дойти от n элементов до 1-го, потребуется k = $log_{4/3}n$ шагов (k - высота отсортированного дерева). Для идеального сбалансированного дерева, где разделителем является средний элемент, потребовалось бы k = $log_2n$ шагов. $log_{4/3}n$ больше $log_2n$ всего на 39%.

Поскольку на каждом уровне выполняется работа O(n), а глубина дерева в среднем O(logn), то итоговое время работы составит O(nlogn). И всё же, если постоянно нам не будет везти, и в качестве разделителя будет выбираться наибольший или наименьший элемент массива, то итоговое время работы составит O(n^2). Но вероятность выбрать такой элемент крайне мала.

Рандомизированные алгоритмы.

Comming soon