logo

TechCodeview

QuickSort – samouczki dotyczące struktury danych i algorytmów

Szybkie sortowanie to algorytm sortowania oparty na Algorytm Dziel i Rządź który wybiera element jako element przestawny i dzieli daną tablicę wokół wybranego elementu przestawnego, umieszczając element przestawny w jego prawidłowej pozycji w posortowanej tablicy.

Jak działa QuickSort?

Kluczowy proces w szybkie sortowanie jest przegroda() . Celem partycji jest umieszczenie elementu obrotowego (dowolny element może zostać wybrany jako element obrotowy) w jego prawidłowej pozycji w posortowanej tablicy i umieszczenie wszystkich mniejszych elementów po lewej stronie elementu obrotowego, a wszystkich większych elementów po prawej stronie elementu obrotowego .

Partycjonowanie odbywa się rekurencyjnie po każdej stronie osi po umieszczeniu osi w prawidłowej pozycji, co ostatecznie sortuje tablicę.



Jak działa Quicksort

Jak działa Quicksort

Unix kontra Windows
Zalecana praktyka Szybkie sortowanie Wypróbuj!

Wybór obrotu:

Istnieje wiele różnych możliwości wyboru sworzni.

  • Zawsze wybieraj pierwszy element jako oś obrotu .
  • Zawsze wybieraj ostatni element jako oś (zaimplementowano poniżej)
  • Wybierz losowy element jako oś obrotu .
  • Wybierz środek jako oś obrotu.

Algorytm partycji:

Logika jest prosta, zaczynamy od skrajnego lewego elementu i śledzimy indeks mniejszych (lub równych) elementów jako I . Jeśli podczas przechodzenia znajdziemy mniejszy element, zamieniamy bieżący element za pomocą arr[i]. W przeciwnym razie ignorujemy bieżący element.

Przyjrzyjmy się działaniu partycji i algorytmu szybkiego sortowania na poniższym przykładzie:

Rozważmy: arr[] = {10, 80, 30, 90, 40}.

  • Porównaj 10 z osią i ponieważ jest ona mniejsza od osi, ułóż ją odpowiednio.

Partycja w QuickSort: porównaj przestaw z 10

  • Porównaj 80 z osią. Jest większy niż obrót.

Partycja w QuickSort: porównaj przestaw z 80

alfabet z cyframi
  • Porównaj 30 z przegubem. Jest mniejszy niż obrotowy, więc odpowiednio go ułóż.

Partycja w QuickSort: porównaj przestaw z 30

  • Porównaj 90 z osią. Jest większa od osi obrotu.

Partycja w QuickSort: porównaj przestaw z 90

  • Ustaw sworzeń we właściwej pozycji.

Partycja w QuickSort: Umieść element obrotowy we właściwej pozycji

Ilustracja Quicksortu:

Ponieważ proces partycjonowania odbywa się rekurencyjnie, przesuwa on element przestawny w jego rzeczywistej pozycji w posortowanej tablicy. Wielokrotne umieszczanie osi w ich rzeczywistej pozycji powoduje posortowanie tablicy.

Postępuj zgodnie z poniższymi ilustracjami, aby zrozumieć, w jaki sposób rekurencyjna implementacja algorytmu partycjonowania pomaga sortować tablicę.

scalanie sortowania Java
  • Początkowa partycja na głównej tablicy:

Quicksort: Wykonywanie partycji

  • Partycjonowanie podtablic:

Quicksort: Wykonywanie partycji

Implementacja kodu szybkiego sortowania:

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>
Jawa 
// 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[] -->Tablica do posortowania, // niska --> Indeks początkowy, // wysoki --> Indeks końcowy 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>
Pyton 
# 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[] -->Tablica do posortowania, // niska --> Indeks początkowy, // wysoki --> Indeks końcowy 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 ?>// Ta funkcja umieszcza ostatni element jako element przestawny // Umieść element przestawny we właściwej pozycji // W sortowanej tablicy i umieszcza wszystkie mniejsze elementy po lewej // osi obrotu, a wszystkie większe elementy po prawej stronie podziału funkcji przestawnej (&$arr, $low,$high) { // Wybierz element przestawny $pivot= $arr[$high]; // Indeks mniejszego elementu i wskazuje // Prawą pozycję obrotu $i=($low-1); for($j=$niski;$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>
Wyjście 
Sorted Array 1 5 7 8 9 10>

Analiza złożoności szybkiego sortowania :

Złożoność czasowa:

  • Najlepszy przypadek : Ω (N log (N))
    Najlepszy scenariusz szybkiego sortowania ma miejsce, gdy element przestawny wybrany na każdym kroku dzieli tablicę na mniej więcej równe połowy.
    W tym przypadku algorytm dokona zrównoważonych partycji, co doprowadzi do wydajnego sortowania.
  • Przypadek przeciętny: θ ( N log (N))
    Wydajność Quicksort w średnich przypadkach jest zwykle bardzo dobra w praktyce, co czyni go jednym z najszybszych algorytmów sortowania.
  • Najgorszy przypadek: O(N2)
    Najgorszy scenariusz dla Quicksort ma miejsce, gdy obrót na każdym kroku konsekwentnie skutkuje wysoce niezrównoważonymi partycjami. Gdy tablica jest już posortowana i element przestawny jest zawsze wybierany jako najmniejszy lub największy element. Aby zapobiec najgorszemu scenariuszowi, stosuje się różne techniki, takie jak wybór dobrego elementu przestawnego (np. mediany z trzech) i użycie algorytmu Randomizowanego (Randomized Quicksort ) w celu przetasowania elementu przed sortowaniem.
  • Przestrzeń pomocnicza: O(1), jeśli nie weźmiemy pod uwagę rekurencyjnej przestrzeni stosu. Jeśli weźmiemy pod uwagę rekursywną przestrzeń stosu, w najgorszym przypadku może wystąpić szybkie sortowanie O ( N ).

Zalety szybkiego sortowania:

  • Jest to algorytm typu „dziel i zwyciężaj”, który ułatwia rozwiązywanie problemów.
  • Jest skuteczny w przypadku dużych zbiorów danych.
  • Ma niski narzut, ponieważ do działania wymaga tylko niewielkiej ilości pamięci.

Wady szybkiego sortowania:

  • Ma złożoność czasową w najgorszym przypadku O (N2), co ma miejsce, gdy czop jest źle wybrany.
  • Nie jest to dobry wybór w przypadku małych zbiorów danych.
  • Nie jest to sortowanie stabilne, co oznacza, że ​​jeśli dwa elementy mają ten sam klucz, to w przypadku sortowania szybkiego ich względna kolejność nie zostanie zachowana w posortowanym wyniku, ponieważ tutaj zamieniamy elementy zgodnie z pozycją obrotu (bez uwzględnienia ich pierwotnego stanowiska).