Algoritmus QuickSort

Obsah

Ako funguje QuickSort?
Algoritmus rýchleho triedenia
Príklady jazyka Python, Java a C / C ++
Zložitosť Quicksortu
Aplikácie Quicksort

V tomto tutoriáli sa dozviete, ako funguje quicksort. Nájdete tiež pracovné príklady rýchleho triedenia v jazykoch C, C ++ Python a Java.

Quicksort je algoritmus založený na prístupe rozdeľ a panuj, v ktorom je pole rozdelené na podskupiny a tieto podskupiny sú rekurzívne nazývané na triedenie prvkov.

Ako funguje QuickSort?

Z poľa je vybratý otočný prvok. Ako otočný prvok môžete zvoliť ľubovoľný prvok z poľa.
Tu sme vzali úplne vpravo (tj. Posledný prvok) poľa ako otočný prvok. Vyberte otočný prvok
Prvky menšie ako otočný prvok sú umiestnené vľavo a prvky väčšie ako otočný prvok sú umiestnené vpravo. Dajte všetky menšie prvky na ľavú stranu a väčšie na pravú stranu otočného prvku.
Vyššie uvedené usporiadanie sa dosiahne nasledujúcimi krokmi.
1. Ukazovateľ je upevnený na otočnom prvku. Otočný prvok sa porovnáva s prvkami začínajúcimi od prvého indexu. Ak sa dosiahne prvok väčší ako otočný prvok, nastaví sa pre tento prvok druhý ukazovateľ.
2. Teraz sa otočný prvok porovnáva s ostatnými prvkami (tretí ukazovateľ). Ak je dosiahnutý prvok menší ako otočný prvok, zamení sa menší prvok za väčší, ktorý sa našiel skôr. Porovnanie otočného prvku s ostatnými prvkami
3. Proces pokračuje, kým sa nedosiahne druhý posledný prvok.
  Nakoniec sa otočný prvok zamení za druhý ukazovateľ. Zamieňajte otočný prvok s druhým ukazovateľom
4. Teraz sú ľavá a pravá podčasti tohto otočného prvku použité na ďalšie spracovanie v nasledujúcich krokoch.
Otočné prvky sú opäť vybrané pre ľavú a pravú čiastkovú časť zvlášť. V rámci týchto čiastkových častí sú otočné prvky umiestnené v ich správnej polohe. Potom sa krok 2 opakuje. V každej polovici vyberte otočný prvok a pomocou rekurzie umiestnite na správne miesto
Podčasti sa opäť rozdelia na menšie podčasti, až kým nebude každá podčasti tvorená z jedného prvku.
V tomto okamihu je pole už zoradené.

Quicksort používa na triedenie čiastkových častí rekurziu.

Na základe prístupu Divide and conquer možno algoritmus quicksort vysvetliť ako:

Rozdeliť
Pole je rozdelené na čiastkové časti, pričom sa ako bod rozdelenia použije pivot. Prvky menšie ako čap sú umiestnené vľavo od čapu a prvky väčšie ako čap sú umiestnené vpravo.
Conquer
Ľavá a pravá podčasti sú opäť rozdelené pomocou znakov výberom otočných prvkov pre ne. To sa dá dosiahnuť rekurzívnym odovzdaním čiastkových častí do algoritmu.
Kombinovať
Tento krok nehrá pri quicksorte významnú úlohu. Pole je už zoradené na konci dobyvateľského kroku.

Fungovanie quicksortu môžete pochopiť pomocou nasledujúcich ilustrácií.

Triedenie prvkov naľavo od otočného čepu pomocou rekurzie

Algoritmus rýchleho triedenia

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightmostIndex) partitionex ) set rightmostIndex as 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

Príklady jazyka Python, Java a 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); )

Zložitosť Quicksortu

Časové zložitosti

Najhoršia zložitosť (Big-O) : Vyskytuje sa, keď je vybratý otočný prvok buď najväčší, alebo najmenší prvok. Táto podmienka vedie k prípadu, keď otočný prvok leží na krajnom konci zoradeného poľa. Jedno čiastkové pole je vždy prázdne a ďalšie čiastkové pole obsahuje prvky. Quicksort sa teda volá iba na tomto podskupine. Algoritmus rýchleho triedenia má však lepší výkon pre rozptýlené otočné body.O(n²)
n - 1
Zložitosť najlepších prípadov (Big-omega) : O(n*log n)
Vyskytuje sa, keď je otočným prvkom vždy stredný prvok alebo blízko stredného prvku.
Priemerná zložitosť prípadu (veľká-theta) : O(n*log n)
Vyskytuje sa, keď nenastanú vyššie uvedené podmienky.