Швидке сортування це алгоритм сортування на основі Алгоритм розділяй і володарюй який вибирає елемент як опору та розбиває заданий масив навколо вибраної опори, розміщуючи опору в правильному положенні в сортованому масиві.
Як працює QuickSort?
Рекомендована практика Швидке сортування Спробуйте!Ключовий процес в швидке сортування це розділ () . Мета розділів полягає в тому, щоб розташувати стрижню (будь-який елемент можна вибрати як стрижню) у правильному положенні в сортованому масиві та розмістити всі менші елементи ліворуч від стрижня, а всі більші елементи — праворуч від стрижня. .
Розбиття виконується рекурсивно з кожного боку опорної точки після того, як опорна точка розміщена в правильному положенні, і це остаточно сортує масив.
Як працює Quicksort
типи циклу for
Вибір Pivot:
Існує багато різних варіантів вибору опор.
- Завжди вибирайте перший елемент як опору .
- Завжди вибирайте останній елемент як опору (реалізовано нижче)
- Виберіть випадковий елемент як опору .
- Виберіть середину як опору.
Алгоритм розділення:
Логіка проста, ми починаємо з крайнього лівого елемента і відстежуємо індекс менших (або рівних) елементів як i . Під час обходу, якщо ми знаходимо менший елемент, ми міняємо поточний елемент на arr[i]. В іншому випадку ми ігноруємо поточний елемент.
Давайте зрозуміємо роботу розділу та алгоритму швидкого сортування за допомогою наступного прикладу:
Розглянемо: arr[] = {10, 80, 30, 90, 40}.
- Порівняйте 10 із опорою і, оскільки вона менша за опору, розташуйте її відповідно.
Розділ у QuickSort: порівняйте опорну частину з 10
- Порівняйте 80 з опорою. Це більше, ніж опорна.
Розділ у QuickSort: порівняйте опорну частину з 80
програми java
- Порівняйте 30 з опорою. Він менший за опорний, тому розмістіть його відповідно.
Розділ у QuickSort: порівняйте опорну частину з 30
- Порівняйте 90 з опорою. Він більший, ніж опорний.
Розділ у QuickSort: порівняйте опорну частину з 90
- Встановіть стержень у правильне положення.
Розділ у QuickSort: розмістіть опору в правильному положенні
Ілюстрація Quicksort:
Оскільки процес розділення виконується рекурсивно, він продовжує розміщувати опору в її фактичному положенні в сортованому масиві. Багаторазове розміщення опорних точок у їхньому фактичному положенні робить масив відсортованим.
Перегляньте зображення нижче, щоб зрозуміти, як рекурсивна реалізація алгоритму розділення допомагає сортувати масив.
алгоритм сортування злиттям
- Початковий розділ на основному масиві:
Швидке сортування: виконання розділу
- Розбиття підмасивів:
Швидке сортування: виконання розділу
Реалізація коду швидкого сортування:
C++ #include using namespace std; int partition(int arr[],int low,int high) { //choose the pivot int pivot=arr[high]; //Index of smaller element and Indicate //the right position of pivot found so far int i=(low-1); for(int j=low;j<=high-1;j++) { //If current element is smaller than the pivot if(arr[j] C // C program for QuickSort #include // Utility function to swap tp integers void swap(int* p1, int* p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; } int partition(int arr[], int low, int high) { // choose the pivot int pivot = arr[high]; // Index of smaller element and Indicate // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } // The Quicksort function Implement void quickSort(int arr[], int low, int high) { // when low is less than high if (low < high) { // pi is the partition return index of pivot int pi = partition(arr, low, high); // Recursion Call // smaller element than pivot goes left and // higher element goes right quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int arr[] = { 10, 7, 8, 9, 1, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call quickSort(arr, 0, n - 1); // Print the sorted array printf('Sorted Array
'); for (int i = 0; i < n; i++) { printf('%d ', arr[i]); } return 0; } // This Code is Contributed By Diwakar Jha> Java // Java implementation of QuickSort import java.io.*; class GFG { // A utility function to swap two elements static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // This function takes last element as pivot, // places the pivot element at its correct position // in sorted array, and places all smaller to left // of pivot and all greater elements to right of pivot static int partition(int[] arr, int low, int high) { // Choosing the pivot int pivot = arr[high]; // Index of smaller element and indicates // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(arr, i, j); } } swap(arr, i + 1, high); return (i + 1); } // The main function that implements QuickSort // arr[] -->Масив для сортування, // низький --> Початковий індекс, // високий --> Кінцевий індекс static void quickSort(int[] arr, int low, int high) { if (low< high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // To print sorted array public static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + ' '); } } // Driver Code public static void main(String[] args) { int[] arr = { 10, 7, 8, 9, 1, 5 }; int N = arr.length; // Function call quickSort(arr, 0, N - 1); System.out.println('Sorted array:'); printArr(arr); } } // This code is contributed by Ayush Choudhary // Improved by Ajay Virmoti> Python # Python3 implementation of QuickSort # Function to find the partition position def partition(array, low, high): # Choose the rightmost element as pivot pivot = array[high] # Pointer for greater element i = low - 1 # Traverse through all elements # compare each element with pivot for j in range(low, high): if array[j] <= pivot: # If element smaller than pivot is found # swap it with the greater element pointed by i i = i + 1 # Swapping element at i with element at j (array[i], array[j]) = (array[j], array[i]) # Swap the pivot element with # the greater element specified by i (array[i + 1], array[high]) = (array[high], array[i + 1]) # Return the position from where partition is done return i + 1 # Function to perform quicksort def quicksort(array, low, high): if low < high: # Find pivot element such that # element smaller than pivot are on the left # element greater than pivot are on the right pi = partition(array, low, high) # Recursive call on the left of pivot quicksort(array, low, pi - 1) # Recursive call on the right of pivot quicksort(array, pi + 1, high) # Driver code if __name__ == '__main__': array = [10, 7, 8, 9, 1, 5] N = len(array) # Function call quicksort(array, 0, N - 1) print('Sorted array:') for x in array: print(x, end=' ') # This code is contributed by Adnan Aliakbar> C# // C# implementation of QuickSort using System; class GFG { // A utility function to swap two elements static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // This function takes last element as pivot, // places the pivot element at its correct position // in sorted array, and places all smaller to left // of pivot and all greater elements to right of pivot static int partition(int[] arr, int low, int high) { // Choosing the pivot int pivot = arr[high]; // Index of smaller element and indicates // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(arr, i, j); } } swap(arr, i + 1, high); return (i + 1); } // The main function that implements QuickSort // arr[] -->Масив для сортування, // низький --> Початковий індекс, // високий --> Кінцевий індекс static void quickSort(int[] arr, int low, int high) { if (low< high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high); // Separately sort elements before // and after partition index quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Driver Code public static void Main() { int[] arr = { 10, 7, 8, 9, 1, 5 }; int N = arr.Length; // Function call quickSort(arr, 0, N - 1); Console.WriteLine('Sorted array:'); for (int i = 0; i < N; i++) Console.Write(arr[i] + ' '); } } // This code is contributed by gfgking> JavaScript // Function to partition the array and return the partition index function partition(arr, low, high) { // Choosing the pivot let pivot = arr[high]; // Index of smaller element and indicates the right position of pivot found so far let i = low - 1; for (let j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its correct position return i + 1; // Return the partition index } // The main function that implements QuickSort function quickSort(arr, low, high) { if (low < high) { // pi is the partitioning index, arr[pi] is now at the right place let pi = partition(arr, low, high); // Separately sort elements before partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Driver code let arr = [10, 7, 8, 9, 1, 5]; let N = arr.length; // Function call quickSort(arr, 0, N - 1); console.log('Sorted array:'); console.log(arr.join(' '));> PHP // code ?>// Ця функція розміщує останній елемент як опору // Розміщує опору як правильну позицію // у відсортованому масиві та розміщує всі менші елементи ліворуч // від опори, а всі більші елементи — праворуч від опорної функції partition(&$arr, $low,$high) { // Вибір опорного елемента $pivot= $arr[$high]; // Індекс меншого елемента та вказує на // праву позицію опори $i=($low-1); for($j=$low;$j<=$high-1;$j++) { if($arr[$j]<$pivot) { // Increment index of smaller element $i++; list($arr[$i],$arr[$j])=array($arr[$j],$arr[$i]); } } // Pivot element as correct position list($arr[$i+1],$arr[$high])=array($arr[$high],$arr[$i+1]); return ($i+1); } // The main function that implement as QuickSort // arr[]:- Array to be sorted // low:- Starting Index //high:- Ending Index function quickSort(&$arr,$low,$high) { if($low<$high) { // pi is partition $pi= partition($arr,$low,$high); // Sort the array // Before the partition of Element quickSort($arr,$low,$pi-1); // After the partition Element quickSort($arr,$pi+1,$high); } } // Driver Code $arr= array(10,7,8,9,1,5); $N=count($arr); // Function Call quickSort($arr,0,$N-1); echo 'Sorted Array:
'; for($i=0;$i<$N;$i++) { echo $arr[$i]. ' '; } //This code is contributed by Diwakar Jha> Вихід
Sorted Array 1 5 7 8 9 10>
Аналіз складності швидкого сортування :
Часова складність:
- Кращий випадок : Ω (N log (N))
Найкращий сценарій для швидкого сортування відбувається, коли опорна точка, вибрана на кожному кроці, ділить масив на приблизно рівні половини.
У цьому випадку алгоритм зробить збалансовані розділи, що призведе до ефективного сортування. - Середній випадок: θ ( N log (N))
Продуктивність Quicksort у середньому випадку зазвичай дуже добра на практиці, що робить його одним із найшвидших алгоритмів сортування. - Найгірший випадок: O(N2)
Найгірший сценарій для швидкого сортування виникає, коли зведення на кожному кроці постійно призводить до дуже незбалансованих розділів. Коли масив уже відсортовано, і опорна точка завжди вибирається як найменший або найбільший елемент. Щоб пом’якшити найгірший сценарій, використовуються різні методи, такі як вибір хорошої опорної точки (наприклад, медіана з трьох) і використання випадкового алгоритму (рандомізованого швидкого сортування) для перемішування елемента перед сортуванням. - Допоміжний простір: O(1), якщо ми не розглядаємо рекурсивний простір стека. Якщо ми розглянемо рекурсивний стековий простір, то в гіршому випадку може бути швидке сортування О ( Н ).
Переваги швидкого сортування:
- Це алгоритм «розділяй і володарюй», який полегшує вирішення проблем.
- Він ефективний для великих наборів даних.
- Він має низькі накладні витрати, оскільки для роботи потрібен лише невеликий обсяг пам’яті.
Недоліки швидкого сортування:
- Його часова складність у найгіршому випадку становить O(N2), що виникає, коли опору вибрано невдало.
- Це невдалий вибір для невеликих наборів даних.
- Це нестабільне сортування, тобто якщо два елементи мають однаковий ключ, їхній відносний порядок не буде збережено у відсортованому виведенні у разі швидкого сортування, тому що тут ми міняємо елементи відповідно до позиції опорної точки (не враховуючи їх вихідний). позиції).