QuickSort

01.01.2020Разделяй и властвуй, Сортировка

Как и сортировка слиянием , QuickSort — это алгоритм «разделяй и властвуй». Он выбирает элемент как сводную и разделяет данный массив вокруг выбранной сводной. Существует много разных версий быстрой сортировки, которые выбирают сводную информацию по-разному.

Всегда выбирайте первый элемент как опорный.
Всегда выбирайте последний элемент как опорный (реализован ниже)
Выберите случайный элемент как опорный.
Выберите медиану как опору.

Ключевым процессом в быстрой сортировке является partition (). Цель разделов, заданная для массива и элемента x массива как pivot, поместить x в правильную позицию в отсортированном массиве и поместить все меньшие элементы (меньше x) перед x, а все большие элементы (больше x) после Икс. Все это должно быть сделано за линейное время.

Псевдокод для рекурсивной функции быстрой сортировки:

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Алгоритм разбиения
Существует много способов сделать разделение, после того, как псевдокод использует метод, описанный в книге CLRS. Логика проста, мы начинаем с самого левого элемента и отслеживаем индекс меньших (или равных) элементов как i. При обходе, если мы находим меньший элемент, мы меняем текущий элемент на arr [i]. В противном случае мы игнорируем текущий элемент.

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Псевдокод для раздела ()

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  // Index of smaller element

    for (j = low; j <= high- 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

Иллюстрация раздела ():

arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6 

low = 0, high =  6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1

Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j 
                                     // are same

j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 

j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] 
i = 3 
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped 

We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot) 
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped 

Now 70 is at its correct place. All elements smaller than
70 are before it and all elements greater than 70 are after
it.

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

C ++

/ * C ++ реализация QuickSort * /
#include <bits/stdc++.h>

using namespace std;

// Утилита для замены двух элементов

void swap(int* a, int* b)

{

int t = *a;

*a = *b;

*b = t;

}

/ * Эта функция принимает последний элемент в качестве точки, мест
элемент поворота в правильном положении в отсортированном
массив, и местами все меньше (меньше, чем сводная)
слева от поворота и все большие элементы вправо
оси * /

int partition (int arr[], int low, int high)

{

int pivot = arr[high]; // пивот

int i = (low - 1); // Индекс меньшего элемента

for (int j = low; j <= high - 1; j++)

{

// Если текущий элемент меньше, чем пивот

if (arr[j] < pivot)

{

i++; // увеличиваем индекс меньшего элемента

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

}

swap(&arr[i + 1], &arr[high]);

return (i + 1);

}

/ * Основная функция, реализующая QuickSort
arr [] -> Массив для сортировки,
низкий -> Начальный индекс,
высокий -> конечный индекс * /

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

/ * pi - индекс разделения, теперь arr [p]

в нужном месте * /

int pi = partition(arr, low, high);

// Отдельно сортируем элементы перед

// раздел и после раздела

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

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

void printArray(int arr[], int size)

{

int i;

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

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

cout << endl;

}

// Код драйвера

int main()

{

int arr[] = {10, 7, 8, 9, 1, 5};

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

quickSort(arr, 0, n - 1);

cout << "Sorted array: \n";

printArray(arr, n);

return 0;

}

// Этот код предоставлен rathbhupendra

/ * C реализация QuickSort * /
#include<stdio.h>

// Утилита для замены двух элементов

void swap(int* a, int* b)

{

int t = *a;

*a = *b;

*b = t;

}

/ * Эта функция принимает последний элемент в качестве точки, мест

элемент поворота в правильном положении в отсортированном

массив, и местами все меньше (меньше, чем сводная)

слева от поворота и все большие элементы вправо

оси * /

int partition (int arr[], int low, int high)

{

int pivot = arr[high]; // пивот

int i = (low - 1); // Индекс меньшего элемента

for (int j = low; j <= high- 1; j++)

{

// Если текущий элемент меньше, чем пивот

if (arr[j] < pivot)

{

i++; // увеличиваем индекс меньшего элемента

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

}

swap(&arr[i + 1], &arr[high]);

return (i + 1);

}

/ * Основная функция, реализующая QuickSort

arr [] -> Массив для сортировки,

низкий -> Начальный индекс,

высокий -> конечный индекс * /

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

/ * pi - индекс разделения, теперь arr [p]

в нужном месте * /

int pi = partition(arr, low, high);

// Отдельно сортируем элементы перед

// раздел и после раздела

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

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

void printArray(int arr[], int size)

{

int i;

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

printf("%d ", arr[i]);

printf("n");

}

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

int main()

{

int arr[] = {10, 7, 8, 9, 1, 5};

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

quickSort(arr, 0, n-1);

printf("Sorted array: n");

printArray(arr, n);

return 0;

}

Джава

// Java-программа для реализации QuickSort

class QuickSort

{

/ * Эта функция принимает последний элемент в качестве оси,

помещает элемент поворота в правильное положение

положение в отсортированном массиве, и помещает все

меньше (меньше, чем шарнир) слева от

стержень и все большие элементы направо

оси * /

int partition(int arr[], int low, int high)

{

int pivot = arr[high];

int i = (low-1); // индекс меньшего элемента

for (int j=low; j<high; j++)

{

// Если текущий элемент меньше, чем пивот

if (arr[j] < pivot)

{

i++;

// поменять местами arr [i] и arr [j]

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

// поменять местами arr [i + 1] и arr [high] (или pivot)

int temp = arr[i+1];

arr[i+1] = arr[high];

arr[high] = temp;

return i+1;

}

/ * Основная функция, которая реализует QuickSort ()

arr [] -> Массив для сортировки,

низкий -> Начальный индекс,

высокий -> конечный индекс * /

void sort(int arr[], int low, int high)

{

if (low < high)

{

/ * pi - индекс разбиения, arr [pi] -

сейчас в нужном месте * /

int pi = partition(arr, low, high);

// Рекурсивно сортировать элементы перед

// раздел и после раздела

sort(arr, low, pi-1);

sort(arr, pi+1, high);

}

/ * Утилита для печати массива размером n * /

static void printArray(int arr[])

{

int n = arr.length;

for (int i=0; i<n; ++i)

System.out.print(arr[i]+" ");

System.out.println();

}

// Драйвер программы

public static void main(String args[])

{

int arr[] = {10, 7, 8, 9, 1, 5};

int n = arr.length;

QuickSort ob = new QuickSort();

ob.sort(arr, 0, n-1);

System.out.println("sorted array");

printArray(arr);

}

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python для реализации сортировки Quicksort

# Эта функция принимает последний элемент в качестве точки, мест
# элемент поворота в правильном положении в отсортированном
# массив, и все места меньше (меньше, чем сводная)
# слева от точки поворота и всех больших элементов справа
Количество точек разворота

def partition(arr,low,high):

i = ( low-1 ) # индекс меньшего элемента

pivot = arr[high] # пивот

for j in range(low , high):

# Если текущий элемент меньше, чем пивот

if arr[j] < pivot:

# индекс приращения меньшего элемента

i = i+1

arr[i],arr[j] = arr[j],arr[i]

arr[i+1],arr[high] = arr[high],arr[i+1]

return ( i+1 )

# Основная функция, реализующая QuickSort
# arr [] -> Массив для сортировки,
# low -> Начальный индекс,
# high -> Конечный индекс

# Функция для быстрой сортировки

def quickSort(arr,low,high):

if low < high:

# pi - индекс разделения, теперь arr [p]

# в нужном месте

pi = partition(arr,low,high)

# Отдельно сортировать элементы перед

# раздел и после раздела

quickSort(arr, low, pi-1)

quickSort(arr, pi+1, high)

# Код драйвера для проверки выше

arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quickSort(arr,0,n-1)

print ("Sorted array is:")

for i in range(n):

print ("%d" %arr[i]),

# Этот код предоставлен Мохитом Кумрой

C #

// C # программа для реализации QuickSort

using System;

class GFG {

/ * Эта функция принимает последний элемент в качестве оси,

помещает элемент поворота в правильное положение

положение в отсортированном массиве, и помещает все

меньше (меньше, чем шарнир) слева от

стержень и все большие элементы направо

оси * /

static int partition(int []arr, int low,

int high)

{

int pivot = arr[high];

// индекс меньшего элемента

int i = (low - 1);

for (int j = low; j < high; j++)

{

// Если текущий элемент меньше

// чем стержень

if (arr[j] < pivot)

{

i++;

// поменять местами arr [i] и arr [j]

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

// поменять местами arr [i + 1] и arr [high] (или pivot)

int temp1 = arr[i+1];

arr[i+1] = arr[high];

arr[high] = temp1;

return i+1;

}

/ * Основная функция, которая реализует QuickSort ()

arr [] -> Массив для сортировки,

низкий -> Начальный индекс,

высокий -> конечный индекс * /

static void quickSort(int []arr, int low, int high)

{

if (low < high)

{

/ * pi - индекс разбиения, arr [pi] -

сейчас в нужном месте * /

int pi = partition(arr, low, high);

// Рекурсивно сортировать элементы перед

// раздел и после раздела

quickSort(arr, low, pi-1);

quickSort(arr, pi+1, high);

}

// Вспомогательная функция для печати массива размера n

static void printArray(int []arr, int n)

{

for (int i = 0; i < n; ++i)

Console.Write(arr[i] + " ");

Console.WriteLine();

}

// Драйвер программы

public static void Main()

{

int []arr = {10, 7, 8, 9, 1, 5};

int n = arr.Length;

quickSort(arr, 0, n-1);

Console.WriteLine("sorted array ");

printArray(arr, n);

}

// Этот код предоставлен Sam007.

Выход:

Sorted array:
1 5 7 8 9 10

Анализ быстрой сортировки
Время, занятое QuickSort в целом, можно записать следующим образом.

 T(n) = T(k) + T(n-k-1) + (n)

Первые два члена относятся к двум рекурсивным вызовам, последний — к процессу разделения. k — количество элементов, которые меньше, чем стержень.
Время, затрачиваемое QuickSort, зависит от входного массива и стратегии разделения. Ниже приведены три случая.

Худший случай: Наихудший случай возникает , когда процесс раздела всегда выбирает наибольшее или наименьший элемент в качестве опоры. Если мы рассмотрим выше стратегию секционирования, где последний элемент всегда выбирается как сводный, наихудший случай произойдет, когда массив уже отсортирован в порядке возрастания или убывания. Ниже приводится повторение в худшем случае.

 T(n) = T(0) + T(n-1) + (n)
which is equivalent to  
 T(n) = T(n-1) + (n)

Решение выше повторения (п ² ).

Лучший случай: лучший случай возникает, когда процесс разбиения всегда выбирает средний элемент как опорный. Ниже приводится повторение в лучшем случае.

 T(n) = 2T(n/2) + (n)

Решение выше повторения (NlogN). Это может быть решено в случае 2 основной теоремы .

Средний случай:
Чтобы выполнить анализ среднего случая, нам нужно учесть все возможные перестановки массива и вычислить время, затрачиваемое на каждую перестановку, что выглядит нелегко .
Мы можем получить представление о среднем случае, рассмотрев случай, когда разбиение помещает O (n / 9) элементов в один набор и O (9n / 10) элементов в другой набор. Следующее повторение для этого случая.

 T(n) = T(n/9) + T(9n/10) + (n)

Решение вышеупомянутого рецидива также O (nLogn)

Хотя наихудшая временная сложность QuickSort — это O (n ² ), что больше, чем у многих других алгоритмов сортировки, таких как Merge Sort и Heap Sort , QuickSort быстрее работает на практике, потому что его внутренний цикл может быть эффективно реализован на большинстве архитектур, и в большинстве данные реального мира. Быстрая сортировка может быть реализована по-разному, изменив выбор оси, так что наихудший случай редко встречается для данного типа данных. Однако сортировка слиянием, как правило, считается лучше, когда данные огромны и хранятся во внешнем хранилище.

QuickSort стабилен ?
Реализация по умолчанию нестабильна. Однако любой алгоритм сортировки можно сделать стабильным, рассматривая индексы в качестве параметра сравнения.
QuickSort на месте ?
В соответствии с широким определением алгоритма на месте он квалифицируется как алгоритм сортировки на месте, поскольку он использует дополнительное пространство только для хранения рекурсивных вызовов функций, но не для манипулирования вводом.

Что такое 3-Way QuickSort?
В простом алгоритме QuickSort мы выбираем элемент как pivot, разделяем массив вокруг pivot и повторяем для подмассивов слева и справа от pivot.
Рассмотрим массив, который имеет много избыточных элементов. Например, {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 2, 4, 1, 4, 4, 4}. Если в Simple QuickSort выбрана точка 4, то мы фиксируем только одну четверку и рекурсивно обрабатываем оставшиеся вхождения. В 3 Way QuickSort массив arr [l..r] делится на 3 части:
а) arr [l..i] элементов меньше, чем пивот.
б) arr [i + 1..j-1] элементы, равные pivot.
в) arr [j..r] элементы больше, чем пивот.
Смотрите это для реализации.

Как реализовать QuickSort для связанных списков?
Быстрая сортировка по односвязному списку
Быстрая сортировка по двусвязному списку

Можем ли мы реализовать QuickSort итеративно?
Да, пожалуйста, обратитесь к Итеративной быстрой сортировке .

Почему быстрая сортировка предпочтительнее сортировки MergeSort для сортировки массивов
Быстрая сортировка в общем виде представляет собой сортировку на месте (т. Е. Она не требует дополнительного хранилища), тогда как сортировка слиянием требует O (N) дополнительного хранилища, N обозначает размер массива, который может быть довольно дорогим. Выделение и перераспределение дополнительного пространства, используемого для сортировки слиянием, увеличивает время работы алгоритма. Сравнивая среднюю сложность, мы обнаруживаем, что оба типа сортов имеют O (NlogN) средней сложности, но константы различаются. Для массивов сортировка слиянием теряется из-за использования дополнительного пространства памяти O (N).

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

Быстрая сортировка также является алгоритмом сортировки, дружественным к кешу, поскольку имеет хорошую локальность при использовании для массивов.

Быстрая сортировка также является хвостовой рекурсией, поэтому выполняется оптимизация хвостовых вызовов.

Почему MergeSort предпочтительнее QuickSort для связанных списков?
В случае связанных списков случай отличается в основном из-за различий в распределении памяти массивов и связанных списков. В отличие от массивов, узлы связанного списка могут не быть смежными в памяти. В отличие от массива, в связанный список мы можем вставлять элементы посередине в O (1) дополнительное пространство и O (1) время. Поэтому операция слияния сортировки слиянием может быть реализована без дополнительного места для связанных списков.

В массивах мы можем осуществлять произвольный доступ, поскольку элементы непрерывны в памяти. Допустим, у нас есть целочисленный (4-байтовый) массив A, и пусть адрес A [0] будет равен x, чтобы получить доступ к A [i], мы можем напрямую получить доступ к памяти в (x + i * 4). В отличие от массивов, мы не можем делать произвольный доступ в связанном списке. Быстрая сортировка требует большого количества такого доступа. В связанном списке для доступа к i-му индексу мы должны перемещать каждый узел от головы до i-го узла, поскольку у нас нет непрерывного блока памяти. Поэтому накладные расходы увеличиваются для быстрой сортировки. Сортировка слиянием обращается к данным последовательно, и потребность в произвольном доступе низка.

Как оптимизировать QuickSort так, чтобы он занимал O (Log n) дополнительное место в худшем случае?
Пожалуйста, см. QuickSort Tail Call Optimization (Сокращение места наихудшего случая для регистрации n)

Фотосъёмка: