Алгоритм быстрой сортировки

В этом руководстве вы узнаете, как работает быстрая сортировка. Также вы найдете рабочие примеры быстрой сортировки на C, C ++, Python и Java.

Быстрая сортировка - это алгоритм, основанный на подходе «разделяй и властвуй», в котором массив разбивается на подмассивы, и эти подмассивы рекурсивно вызываются для сортировки элементов.

Как работает QuickSort?

Из массива выбирается элемент поворота. Вы можете выбрать любой элемент из массива в качестве основного.
Здесь мы приняли крайние правые (то есть. Последний элемент) из массива в качестве элемента вращения. Выберите элемент поворота
Элементы, меньшие, чем элемент поворота, помещаются слева, а элементы, превышающие элемент поворота, помещаются справа. Поместите все меньшие элементы слева, а большие - справа от поворотного элемента
. Вышеупомянутое расположение достигается следующими шагами.
1. Указатель фиксируется на элементе поворота. Сводный элемент сравнивается с элементами, начиная с первого индекса. Если достигается элемент, больший, чем элемент поворота, для этого элемента устанавливается второй указатель.
2. Теперь сводный элемент сравнивается с другими элементами (третий указатель). Если достигается элемент, меньший, чем элемент поворота, меньший элемент заменяется более крупным элементом, найденным ранее. Сравнение поворотного элемента с другими элементами
3. Процесс продолжается, пока не будет достигнут второй последний элемент.
  Наконец, элемент поворота заменяется вторым указателем. Поменять местами сводный элемент вторым указателем
4. Теперь левая и правая части этого поворотного элемента взяты для дальнейшей обработки на следующих шагах.
Элементы поворота снова выбираются отдельно для левой и правой частей. Внутри этих частей поворотные элементы размещаются в правильном положении. Затем шаг 2 повторяется. Выберите элемент поворота в каждой половине и поместите в правильное место с помощью рекурсии
Подчасти снова делятся на более мелкие подчасти, пока каждая подчасть не будет сформирована из одного элемента.
На данный момент массив уже отсортирован.

Quicksort использует рекурсию для сортировки частей.

На основе подхода «разделяй и властвуй» алгоритм быстрой сортировки можно объяснить следующим образом:

Divide
Массив делится на части, в которых точка разделения является точкой разделения. Элементы меньшего размера, чем точка поворота, помещаются слева от оси, а элементы, превышающие точку поворота, размещаются справа.
Conquer
Левая и правая части снова разделяются с помощью выбора для них элементов поворота. Это может быть достигнуто путем рекурсивной передачи частей в алгоритм.
Комбинировать
Этот шаг не играет существенной роли в быстрой сортировке. Массив уже отсортирован в конце шага завоевания.

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

Сортировка элементов слева от поворота с помощью рекурсии

Сортировка элементов справа от поворота с помощью рекурсии

Алгоритм быстрой сортировки

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndemostIndex + 1, rightmostIndex) partition ( ) установите rightmostIndex как pivotIndex storeIndex <- leftmostIndex - 1 для i <- leftmostIndex + 1 в rightmostIndex, если element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1 +) return store 1

Примеры Python, Java и C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Сложность быстрой сортировки

Временные сложности

Сложность наихудшего случая (Big-O) : это происходит, когда выбранный элемент поворота является либо самым большим, либо самым маленьким элементом. Это условие приводит к тому, что опорный элемент находится на крайнем конце отсортированного массива. Один подмассив всегда пуст, а другой подмассив содержит элементы. Таким образом, быстрая сортировка вызывается только для этого подмассива. Однако алгоритм быстрой сортировки имеет лучшую производительность для разрозненных опорных точек.O(n²)
n - 1
Сложность наилучшего случая (Big-omega) : O(n*log n)
это происходит, когда элемент поворота всегда является средним элементом или рядом с ним.
Средняя сложность кейса (Big-theta) : O(n*log n)
Это происходит, когда вышеуказанные условия не выполняются.