V tej vadnici boste izvedeli, kako deluje hitri sortiranje. Prav tako boste našli delovne primere hitrega sortiranja v C, C ++ Python in Java.
Quicksort je algoritem, ki temelji na pristopu deli in osvajaj, pri katerem je polje razdeljeno na podniz in ti podniz so rekurzivno poklicani za razvrščanje elementov.
Kako deluje QuickSort?
- Iz matrike je izbran vrtilni element. Kot pivot element lahko izberete kateri koli element iz polja.
Tu smo za vrtilni element vzeli skrajno desno (tj. Zadnji element) polja.
Izberite vrtilni element - Elementi, ki so manjši od vrtilnega elementa, so postavljeni na levi strani, elementi, večji od pivotnega elementa, pa na desni.
Vse manjše elemente postavite na levo, večje pa na desno na vrtilni element
. Zgornjo razporeditev dosežete z naslednjimi koraki.- Na vrtilni element je pritrjen kazalec. Vrtilni element se primerja z elementi, ki se začnejo od prvega indeksa. Če je dosežen element, večji od vrtilnega elementa, je za ta element nastavljen drugi kazalec.
- Zdaj se vrtilni element primerja z drugimi elementi (tretji kazalec). Če je dosežen element, manjši od vrtilnega elementa, se manjši element zamenja z večjim elementom, ki smo ga našli prej.
Primerjava vrtilnega elementa z drugimi elementi - Postopek se nadaljuje, dokler ni dosežen drugi zadnji element.
Na koncu se vrtilni element zamenja z drugim kazalcem.
Zamenjajte vrtilni element z drugim kazalcem - Zdaj sta levi in desni del tega vrtilnega elementa za nadaljnjo obdelavo v spodnjih korakih.
- Vrtilni elementi so znova izbrani za levi in desni poddeli posebej. V teh poddelih so vrtilni elementi postavljeni v njihov pravi položaj. Nato se ponovi korak 2.
Izberite vrtilni element v vsaki polovici in z rekurzijo postavite na pravo mesto - Poddeli so spet razdeljeni na manjše poddele, dokler vsak poddel ni iz enega samega elementa.
- Na tej točki je polje že razvrščeno.
Quicksort za razvrščanje poddelov uporablja rekurzijo.
Na podlagi pristopa Divide and conquer lahko algoritem hitrega sortiranja razložimo kot:
Polje Divide je razdeljeno na poddele, pri katerih je pivot kot razdelilna točka. Elementi, ki so manjši od vrtišča, so nameščeni levo od vrtišča, elementi, ki so večji od vrtišča, pa desno.- Osvoji
Levi in desni poddeli se znova razdelijo z uporabo z izbiro vrtilnih elementov zanje. To lahko dosežemo z rekurzivnim posredovanjem poddelov v algoritem. - Kombiniraj
Ta korak pri hitrem sortiranju ne igra pomembne vloge. Matrika je že razvrščena na koncu koraka osvajanja.
Delovanje hitrega sorta lahko razumete s pomočjo spodnjih ilustracij.
Razvrščanje elementov na levi strani vrtišča z uporabo rekurzije 
Razvrščanje elementov na desni strani vrtišča z uporabo rekurzije
Algoritem hitrega razvrščanja
quickSort (matrika, leftmostIndex, rightmostIndex), če (leftmostIndex <rightmostIndex) pivotIndex <- particija (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex, levo, most, index, levo, most, index ) nastavite rightmostIndex kot pivotIndex storeIndex <- leftmostIndex - 1 za i <- leftmostIndex + 1 na rightmostIndex if element (i) <pivotElement swap element (i) in element (storeIndex) storeIndex ++ swap pivotElement in element (storeIndex + 1) return storeIndex + 1.
Primeri Python, Java in 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); )
Hitra zapletenost
Časovne zapletenosti
-
Najslabša zapletenost (Big-O) : Pojavi se, kadar je izbrani vrtilni element največji ali najmanjši element. Ta pogoj vodi do primera, ko je vrtilni element na skrajnem koncu razvrščene matrike. Ena pod matrika je vedno prazna, druga pod matrika pa vsebuje elemente. Tako se hitro sortiranje pokliče samo na tej podnizi. Vendar ima algoritem hitrega razvrščanja boljše delovanje pri razpršenih pivotih.
O(n2)n - 1 - Zapletenost najboljšega primera (Big-omega) :
O(n*log n)
Pojavi se, kadar je vrtilni element vedno srednji element ali blizu srednjega elementa. - Povprečna zapletenost primerov (velik-theta) :
O(n*log n)
Pojavi se, ko se zgornji pogoji ne pojavijo.
Zapletenost prostora
Prostorska zapletenost za hitri sorti je O(log n).
Quicksort Applications
Quicksort se izvaja, ko
- programski jezik je primeren za rekurzijo
- pomembna je časovna zapletenost
- zapletenost prostora je pomembna
