logo

TechCodeview

QuickSort – навчальні посібники зі структури даних і алгоритмів

Швидке сортування це алгоритм сортування на основі Алгоритм розділяй і володарюй який вибирає елемент як опору та розбиває заданий масив навколо вибраної опори, розміщуючи опору в правильному положенні в сортованому масиві.

Як працює QuickSort?

Ключовий процес в швидке сортування це розділ () . Мета розділів полягає в тому, щоб розташувати стрижню (будь-який елемент можна вибрати як стрижню) у правильному положенні в сортованому масиві та розмістити всі менші елементи ліворуч від стрижня, а всі більші елементи — праворуч від стрижня. .

Розбиття виконується рекурсивно з кожного боку опорної точки після того, як опорна точка розміщена в правильному положенні, і це остаточно сортує масив.



Як працює 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), що виникає, коли опору вибрано невдало.
  • Це невдалий вибір для невеликих наборів даних.
  • Це нестабільне сортування, тобто якщо два елементи мають однаковий ключ, їхній відносний порядок не буде збережено у відсортованому виведенні у разі швидкого сортування, тому що тут ми міняємо елементи відповідно до позиції опорної точки (не враховуючи їх вихідний). позиції).