Рубрики

Может ли QuickSort быть реализован в O (nLogn) наихудшем времени сложности?

Наихудшая временная сложность типичной реализации QuickSort — O (n 2 ). Наихудший случай возникает, когда выбранный стержень всегда является крайним (наименьшим или наибольшим) элементом. Это происходит, когда входной массив сортируется или сортируется в обратном порядке, а первый или последний элемент выбирается как сводный.

Хотя рандомизированная быстрая сортировка работает хорошо даже при сортировке массива, все же существует вероятность того, что случайно выбранный элемент всегда является экстремальным. Можно ли уменьшить наихудший случай до O (nLogn)?

Ответ — да, мы можем достичь O (nLogn) в худшем случае. Идея основана на том факте, что медианный элемент несортированного массива может быть найден за линейное время . Итак, сначала мы находим медиану, а затем разбиваем массив вокруг медианного элемента.

Ниже приведена реализация C ++, основанная на представленной выше идее. Большинство функций из нижеприведенного progran скопированы из K'th Smallest / Largest Element в Unsorted Array | Набор 3 (наихудший случай линейного времени)

/ * Реализация быстрой сортировки в худшем случае O (nLogn) * /
#include<cstring>
#include<iostream>
#include<algorithm>
#include<climits>

using namespace std;

  
// Следующие функции взяты из http://goo.gl/ih05BF

int partition(int arr[], int l, int r, int k);

int kthSmallest(int arr[], int l, int r, int k);

  
/ * AO (nLogn) функция сложности времени для сортировки arr [l..h] * /

void quickSort(int arr[], int l, int h)

{

    if (l < h)

    {

        // Находим размер текущего подмассива

        int n = h-l+1;

  

        // Найти медиану обр. [].

        int med = kthSmallest(arr, l, h, n/2);

  

        // Разделим массив вокруг медианы

        int p = partition(arr, l, h, med);

  

        // Повтор для левого и правого раздела

        quickSort(arr, l, p - 1);

        quickSort(arr, p + 1, h);

    }

}

  
// Простая функция для поиска медианы arr []. Это называется
// только для массива размером 5 в этой программе.

int findMedian(int arr[], int n)

{

    sort(arr, arr+n);  // Сортировать массив

    return arr[n/2];   // Возвращаем средний элемент

}

  
// Возвращает k'ый наименьший элемент в arr [l..r] в худшем случае
// линейное время. Предположение: все элементы в ARR [] различны

int kthSmallest(int arr[], int l, int r, int k)

{

    // Если k меньше количества элементов в массиве

    if (k > 0 && k <= r - l + 1)

    {

        int n = r-l+1; // Количество элементов в arr [l..r]

  

        // Делим arr [] на группы размером 5, вычисляем медиану

        // каждой группы и сохраняем ее в массиве median [].

        int i, median[(n+4)/5]; // Будет этаж ((n + 4) / 5) groups;

        for (i=0; i<n/5; i++)

            median[i] = findMedian(arr+l+i*5, 5);

        if (i*5 < n) // Для последней группы с менее чем 5 элементами

        {

            median[i] = findMedian(arr+l+i*5, n%5);

            i++;

        }

  

        // Найти медиану всех медиан, используя рекурсивный вызов.

        // Если в медиане [] есть только один элемент, то нет необходимости

        // рекурсивного вызова

        int medOfMed = (i == 1)? median[i-1]:

                                 kthSmallest(median, 0, i-1, i/2);

  

        // Разделим массив вокруг случайного элемента и

        // получить позицию элемента pivot в отсортированном массиве

        int pos = partition(arr, l, r, medOfMed);

  

        // Если позиция совпадает с k

        if (pos-l == k-1)

            return arr[pos];

        if (pos-l > k-1)  // Если позиция больше, повторить влево

            return kthSmallest(arr, l, pos-1, k);

  

        // Остальное повторяется для правого подмассива

        return kthSmallest(arr, pos+1, r, k-pos+l-1);

    }

  

    // Если k больше чем количество элементов в массиве

    return INT_MAX;

}

  

void swap(int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

  
// Он ищет x в arr [l..r] и разбивает массив
// вокруг х.

int partition(int arr[], int l, int r, int x)

{

    // Поиск x в arr [l..r] и перемещение его до конца

    int i;

    for (i=l; i<r; i++)

        if (arr[i] == x)

           break;

    swap(&arr[i], &arr[r]);

  

    // Стандартный алгоритм разбиения

    i = l;

    for (int j = l; j <= r - 1; j++)

    {

        if (arr[j] <= x)

        {

            swap(&arr[i], &arr[j]);

            i++;

        }

    }

    swap(&arr[i], &arr[r]);

    return i;

}

  
/ * Функция для печати массива * /

void printArray(int arr[], int size)

{

    int i;

    for (i=0; i < size; i++)

        cout << arr[i] << " ";

    cout << endl;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {1000, 10, 7, 8, 9, 30, 900, 1, 5, 6, 20};

    int n = sizeof(arr)/sizeof(arr[0]);

    quickSort(arr, 0, n-1);

    cout << "Sorted array is\n";

    printArray(arr, n);

    return 0;

}

Выход:

Sorted array is
1 5 6 7 8 9 10 20 30 900 1000

Как QuickSort реализован на практике — используется ли вышеуказанный подход?
Несмотря на то, что сложность времени в наихудшем случае вышеописанного подхода — O (nLogn), он никогда не используется в практической реализации. Скрытые константы в этом подходе высоки по сравнению с обычной быстрой сортировкой. Ниже приведены некоторые методы, используемые в практических реализациях QuickSort.
1) Случайный подбор, чтобы уменьшить вероятность возникновения наихудшего случая (рандомизированная быстрая сортировка)
2) Вызов сортировки вставкой для небольших массивов, чтобы уменьшить рекурсивные вызовы.
3) Быстрая сортировка хвоста рекурсивна , так что оптимизация хвостового вызова выполнена.

Таким образом, рассмотренный выше подход является скорее теоретическим подходом с O (nLogn) сложностью времени наихудшего случая.

Эта статья составлена Шивамом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Может ли QuickSort быть реализован в O (nLogn) наихудшем времени сложности?

0.00 (0%) 0 votes