Algoritmus QuickSort

Obsah

Jak funguje QuickSort?
Algoritmus rychlého řazení
Python, Java a C / C ++ příklady
Složitost Quicksortu
Aplikace Quicksort

V tomto kurzu se dozvíte, jak funguje quicksort. Také najdete pracovní příklady rychlého řazení v jazycích C, C ++ Python a Java.

Quicksort je algoritmus založený na přístupu dělení a dobývání, při kterém je pole rozděleno do dílčích polí a tato dílčí pole jsou rekurzivně nazývána pro třídění prvků.

Jak funguje QuickSort?

Otočný prvek je vybrán z pole. Jako otočný prvek můžete vybrat libovolný prvek z pole.
Tady jsme vzali zcela vpravo (tj. Poslední prvek) pole jako otočný prvek. Vyberte otočný prvek
Prvky menší než otočný prvek jsou umístěny vlevo a prvky větší než otočný prvek jsou umístěny vpravo. Umístěte všechny menší prvky na levou stranu a větší na pravou stranu otočného prvku.
Výše uvedeného uspořádání je dosaženo následujícími kroky.
1. Ukazatel je upevněn na otočném prvku. Otočný prvek je porovnán s prvky začínajícími od prvního indexu. Pokud je dosaženo prvku většího než otočný prvek, je pro tento prvek nastaven druhý ukazatel.
2. Nyní je otočný prvek porovnán s ostatními prvky (třetí ukazatel). Pokud je dosaženo prvku menšího než otočný prvek, je menší prvek zaměněn za větší prvek nalezený dříve. Porovnání otočného prvku s jinými prvky
3. Proces pokračuje, dokud není dosaženo druhého posledního prvku.
  Nakonec je otočný prvek zaměněn druhým ukazatelem. Zaměňte otočný prvek s druhým ukazatelem
4. Nyní jsou levé a pravé části tohoto otočného prvku převzaty pro další zpracování v následujících krocích.
Otočné prvky jsou opět vybrány pro levou a pravou dílčí část samostatně. V těchto dílčích částech jsou otočné prvky umístěny ve své správné poloze. Poté se krok 2 opakuje. V každé polovině vyberte otočný prvek a pomocí rekurze vložte na správné místo
Dílčí části jsou opět rozděleny na menší dílčí části, dokud není každá dílčí část vytvořena z jednoho prvku.
V tomto okamžiku je pole již tříděno.

Quicksort používá pro třídění dílčích částí rekurzi.

Na základě přístupu Divide and conquer lze algoritmus quicksort vysvětlit jako:

Rozdělit
Pole je rozděleno na dílčí části, přičemž pivot je bod rozdělení. Prvky menší než pivot jsou umístěny nalevo od pivot a prvky větší než pivot jsou umístěny doprava.
Dobýt
Levý a pravý dílčí díl jsou opět rozděleny na oddíly pomocí výběru otočných prvků pro ně. Toho lze dosáhnout rekurzivním předáním dílčích částí do algoritmu.
Kombinovat
Tento krok nehraje v rychlém řazení významnou roli. Pole je již tříděno na konci dobyvatelského kroku.

Fungování rychlého třídění můžete pochopit pomocí níže uvedených ilustrací.

Třídění prvků nalevo od otočného čepu pomocí rekurze

Třídění prvků vpravo od otočného čepu pomocí rekurze

Algoritmus rychlého řazení

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

Python, Java a C / C ++ příklady

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); )

Složitost Quicksortu

Časové složitosti

Složitost nejhoršího případu (Big-O) : Dochází k němu, když je vybraný otočný prvek největší nebo nejmenší prvek. Tato podmínka vede k případu, kdy otočný prvek leží na extrémním konci seřazeného pole. Jedno dílčí pole je vždy prázdné a další dílčí pole obsahuje prvky. Quicksort je tedy volán pouze na tomto dílčím poli. Algoritmus rychlého řazení však má lepší výkon pro rozptýlené otočné čepy.O(n²)
n - 1
Složitost nejlepšího případu (Big-omega) : O(n*log n)
Dochází k němu, když je otočný prvek vždy prostředním prvkem nebo blízko středního prvku.
Průměrná složitost případu (velká-theta) : O(n*log n)
Dochází k němu, když nenastanou výše uvedené podmínky.