Алгоритм швидкого сортування

У цьому підручнику ви дізнаєтесь, як працює швидка сортування. Також ви знайдете робочі приклади швидкого сортування на мовах C, C ++ Python та Java.

Quicksort - це алгоритм, заснований на підході поділи і завоюй, при якому масив розбивається на підмасиви, і ці підмасиви рекурсивно викликаються для сортування елементів.

Як працює QuickSort?

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

Quicksort використовує рекурсію для сортування під-частин.

На основі підходу Divide and conquer алгоритм швидкого сортування можна пояснити як:

Розділити
Масив розділено на підчастини, що беруть pivot як точку розділення. Елементи, менші за шарнір, розміщуються ліворуч від шарніра, а елементи, більші за шарнір, - праворуч.
Підкорити
Ліву та праву підчастини знову розділити за допомогою, вибравши для них елементи обертання. Цього можна досягти шляхом рекурсивного передавання підрозділів в алгоритм.
Комбінувати
Цей крок не відіграє суттєвої ролі у швидкому сортуванні. Масив вже відсортовано в кінці кроку підкорення.

Ви можете зрозуміти роботу швидкого сорту за допомогою ілюстрацій нижче.

Сортування елементів зліва від зведення за допомогою рекурсії

Сортування елементів праворуч від зведення за допомогою рекурсії

Алгоритм швидкого сортування

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex, array, pivotIndex, array, pivotIndex, array, pivotIndex, rightmostmostIndex, rightmostmostIndex, Array ) встановити rightmostIndex як pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) return storeIndex + 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)
Це відбувається, коли опорний елемент завжди є середнім елементом або поблизу середнього елемента.
Середня складність справи (велика тета) : O(n*log n)
Це відбувається, коли вищезазначені умови не виникають.