logo

TechCodeview

QuickSort – Výukové programy pro datovou strukturu a algoritmus

Rychlé třídění je třídicí algoritmus založený na Algoritmus rozděl a panuj který vybere prvek jako pivot a rozdělí dané pole kolem vybraného pivotu umístěním pivotu do správné polohy v seřazeném poli.

Jak funguje QuickSort?

Klíčový proces v quickSort je rozdělit() . Cílem oddílů je umístit pivot (jako pivot lze vybrat jakýkoli prvek) na správnou pozici v seřazeném poli a umístit všechny menší prvky nalevo od pivotu a všechny větší prvky napravo od pivotu. .

Rozdělení se provádí rekurzivně na každé straně čepu poté, co se čep umístí do správné polohy a tím se pole konečně seřadí.



Jak funguje Quicksort

Jak funguje Quicksort

charakter.srovnej java
Doporučený postup Rychlé řazení Vyzkoušejte!

Volba pivotu:

Existuje mnoho různých možností výběru čepů.

  • Vždy vyberte první prvek jako pivot .
  • Vždy vyberte poslední prvek jako pivot (implementováno níže)
  • Vyberte náhodný prvek jako pivot .
  • Vyberte střed jako pivot.

Algoritmus rozdělení:

Logika je jednoduchá, začínáme od prvku zcela vlevo a sledujeme index menších (nebo stejných) prvků jako i . Pokud při procházení najdeme menší prvek, zaměníme aktuální prvek s arr[i]. Jinak aktuální prvek ignorujeme.

Pojďme pochopit fungování oddílu a algoritmu rychlého třídění pomocí následujícího příkladu:

Zvažte: arr[] = {10, 80, 30, 90, 40}.

javascript nejblíže
  • Porovnejte 10 s čepem a protože je menší než čep, uspořádejte jej podle toho.

Oddíl v QuickSort: Porovnejte pivot s 10

  • Porovnejte 80 s pivotem. Je větší než pivot.

Oddíl v QuickSort: Porovnejte pivot s 80

  • Porovnejte 30 s pivotem. Je menší než pivot, takže jej podle toho zařiďte.

Oddíl v QuickSort: Porovnejte pivot s 30

  • Porovnejte 90 s pivotem. Je větší než pivot.

Oddíl v QuickSort: Porovnejte pivot s 90

  • Umístěte čep do správné polohy.

Oddíl v QuickSort: Umístěte čep do správné polohy

Ilustrace Quicksortu:

Vzhledem k tomu, že proces rozdělení probíhá rekurzivně, stále umisťuje pivot do jeho skutečné pozice v seřazeném poli. Opakovaným vkládáním pivotů do jejich skutečné polohy se pole seřadí.

Postupujte podle obrázků níže, abyste pochopili, jak rekurzivní implementace algoritmu rozdělení pomáhá třídit pole.

osi modelové vrstvy
  • Počáteční oddíl na hlavním poli:

Quicksort: Provedení rozdělení

  • Rozdělení podpolí:

Quicksort: Provedení rozdělení

Implementace kódu rychlého řazení:

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>
Jáva 
// 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[] -->Pole k seřazení, // low --> Počáteční index, // high --> Ending index 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>
Krajta 
# 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[] -->Pole k seřazení, // low --> Počáteční index, // high --> Ending index 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 ?>// Tato funkce se uskuteční jako poslední prvek jako pivot // Umístěte pivot do správné pozice // V Sorted Array a umístí všechny menší doleva // pivotu a všechny větší elementy napravo od oddílu funkce pivotu (&$arr, $low,$high) { // Vyberte kontingenční prvek $pivot= $arr[$high]; // Index menšího prvku a označuje // Správnou pozici pivotu $i=($low-1); for($j=$nízký;$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>
Výstup 
Sorted Array 1 5 7 8 9 10>

Analýza složitosti rychlého třídění :

Časová náročnost:

  • Nejlepší případ : Ω (N log (N))
    Nejlepší scénář pro rychlé třídění nastává, když pivot zvolený v každém kroku rozděluje pole na zhruba stejné poloviny.
    V tomto případě algoritmus vytvoří vyvážené oddíly, což povede k efektivnímu třídění.
  • Průměrný případ: θ ( N log (N))
    Průměrný výkon Quicksortu je v praxi obvykle velmi dobrý, což z něj činí jeden z nejrychlejších třídicích algoritmů.
  • Nejhorší případ: O(N2)
    Nejhorší scénář pro Quicksort nastane, když pivot v každém kroku konzistentně vede k vysoce nevyváženým oddílům. Když je pole již seřazeno a pivot je vždy vybrán jako nejmenší nebo největší prvek. Ke zmírnění nejhoršího scénáře se používají různé techniky, jako je výběr dobrého pivotu (např. medián tří) a použití náhodného algoritmu (Randomized Quicksort ) k promíchání prvku před řazením.
  • Pomocný prostor: O(1), pokud neuvažujeme rekurzivní zásobníkový prostor. Pokud vezmeme v úvahu rekurzivní zásobníkový prostor, pak by v nejhorším případě mohl udělat quicksort Ó ( N ).

Výhody rychlého řazení:

  • Je to algoritmus rozděl a panuj, který usnadňuje řešení problémů.
  • Je efektivní na velkých souborech dat.
  • Má nízkou režii, protože ke své funkci vyžaduje pouze malé množství paměti.

Nevýhody rychlého řazení:

  • Má časovou složitost v nejhorším případě O(N2), ke kterému dochází, když je pivot zvolen špatně.
  • Není to dobrá volba pro malé soubory dat.
  • Nejedná se o stabilní řazení, to znamená, že pokud mají dva prvky stejný klíč, jejich relativní pořadí se v setříděném výstupu v případě rychlého řazení nezachová, protože zde zaměňujeme prvky podle polohy pivotu (bez ohledu na jejich původní pozice).