Algoritm QuickSort

Cuprins

Cum funcționează QuickSort?
Algoritm de sortare rapidă
Exemple Python, Java și C / C ++
Complexitatea Quicksort
Aplicații Quicksort

În acest tutorial, veți afla cum funcționează quicksort. De asemenea, veți găsi exemple de lucru de tip rapid în C, C ++ Python și Java.

Quicksort este un algoritm bazat pe abordarea de împărțire și cucerire în care matricea este împărțită în subarraiuri și aceste subraje sunt apelate recursiv pentru a sorta elementele.

Cum funcționează QuickSort?

Un element pivot este ales din matrice. Puteți alege orice element din matrice ca element pivot.
Aici, am luat cel mai drept (adică ultimul element) al tabloului ca element pivot. Selectați un element pivot
Elementele mai mici decât elementul pivot sunt puse în stânga și elementele mai mari decât elementul pivot sunt puse în dreapta. Puneți toate elementele mai mici în stânga și mai mari în dreapta elementului pivot
. Aranjamentul de mai sus este realizat prin pașii următori.
1. Un indicator este fixat la elementul pivot. Elementul pivot este comparat cu elementele care încep de la primul index. Dacă este atins elementul mai mare decât elementul pivot, este setat un al doilea indicator pentru acel element.
2. Acum, elementul pivot este comparat cu celelalte elemente (un al treilea indicator). Dacă este atins un element mai mic decât elementul pivot, elementul mai mic este schimbat cu elementul mai mare găsit mai devreme. Compararea elementului pivot cu alte elemente
3. Procesul continuă până la atingerea celui de-al doilea ultim element.
  În cele din urmă, elementul pivot este schimbat cu al doilea indicator. Schimbați elementul pivot cu al doilea indicator
4. Acum, sub-părțile stânga și dreapta ale acestui element pivot sunt luate pentru procesare ulterioară în pașii de mai jos.
Elementele pivot sunt din nou alese separat pentru părțile secundare stânga și dreapta. În cadrul acestor sub-părți, elementele pivotante sunt plasate în poziția lor corectă. Apoi, pasul 2 se repetă. Selectați elementul de pivotare din fiecare jumătate și puneți-l la locul corect folosind recursivitatea
Sub-părțile sunt din nou împărțite în sub-părți mai mici până când fiecare sub-parte este formată dintr-un singur element.
În acest moment, matricea este deja sortată.

Quicksort folosește recursivitatea pentru sortarea sub-părților.

Pe baza abordării Divide and conquer, algoritmul rapid poate fi explicat ca:

Împărțiți
Matricea este împărțită în sub-părți, luând pivotul ca punct de partiționare. Elementele mai mici decât pivotul sunt plasate în stânga pivotului și elementele mai mari decât pivotul sunt plasate în dreapta.
Conquer Subpartele
stânga și dreapta sunt din nou partiționate folosind elementele pivot selectând pentru ele. Acest lucru poate fi realizat prin trecerea recursivă a părților secundare în algoritm.
Combinați
Acest pas nu joacă un rol semnificativ în rapid. Matricea este deja sortată la sfârșitul etapei de cucerire.

Puteți înțelege funcționarea quicksort cu ajutorul ilustrațiilor de mai jos.

Sortarea elementelor din stânga pivotului folosind recursivitatea

Sortarea elementelor din dreapta pivotului folosind recursivitatea

Algoritm de sortare rapidă

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partiție (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + array, rightmostIndex) ) setați rightmostIndex ca pivotIndex storeIndex <- leftmostIndex - 1 pentru i <- leftmostIndex + 1 la rightmostIndex if element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) return storeIndex + 1

Exemple Python, Java și 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); )

Complexitatea Quicksort

Complexități de timp

Complexitatea celui mai grav caz (Big-O) : apare atunci când elementul pivot ales este fie cel mai mare, fie cel mai mic element. Această condiție duce la cazul în care elementul pivot se află într-un capăt extrem al matricei sortate. Un sub-tablou este întotdeauna gol și un alt sub-tablou conține elemente. Astfel, quicksort este apelat numai pe această sub-matrice. Cu toate acestea, algoritmul de sortare rapidă are o performanță mai bună pentru pivotii împrăștiați.O(n²)
n - 1
Complexitatea celui mai bun caz (Big-omega) : O(n*log n)
apare atunci când elementul pivot este întotdeauna elementul de mijloc sau aproape de elementul de mijloc.
Complexitatea medie a cazurilor (Big-theta) : O(n*log n)
apare atunci când nu apar condițiile de mai sus.