QuickSort-algoritmi

Sisällysluettelo

Kuinka QuickSort toimii?
Pikalajittelualgoritmi
Python-, Java- ja C / C ++ -esimerkkejä
Quicksort-monimutkaisuus
Quicksort-sovellukset

Tässä opetusohjelmassa opit kuinka quicksort toimii. Löydät myös toimivia esimerkkejä pikalajikkeista C, C ++ Python ja Java.

Quicksort on jakamis- ja valloitusmenetelmään perustuva algoritmi, jossa matriisi on jaettu alirakenteisiin ja näitä aliryhmiä kutsutaan rekursiivisesti lajittelemaan elementit.

Kuinka QuickSort toimii?

Sarjasta valitaan kääntöelementti. Voit valita minkä tahansa elementin taulukosta pivot-elementiksi.
Tässä olemme ottaneet taulukon oikeanpuoleisen (eli viimeisen elementin) kääntöelementiksi. Valitse pivot-elementti
Kääntöelementtiä pienemmät elementit laitetaan vasemmalle ja kääntöelementtiä suuremmat elementit oikealle. Aseta kaikki pienemmät elementit kääntöelementin vasemmalle ja suuremmalle oikealle.
Edellä oleva järjestely saavutetaan seuraavilla vaiheilla.
1. Osoitin on kiinnitetty kääntöelementtiin. Kääntöelementtiä verrataan ensimmäisestä indeksistä alkaviin elementteihin. Jos saavutetaan kääntöelementtiä suurempi elementti, tälle elementille asetetaan toinen osoitin.
2. Nyt pivot-elementtiä verrataan muihin elementteihin (kolmas osoitin). Jos saavutetaan kääntöelementtiä pienempi elementti, pienempi elementti vaihdetaan aiemmin löydetyn suuremman elementin kanssa. Kääntöelementin vertailu muihin elementteihin
3. Prosessi jatkuu, kunnes toinen viimeinen elementti on saavutettu.
  Lopuksi kääntöelementti vaihdetaan toisen osoittimen kanssa. Vaihda kääntöelementti toisen osoittimen kanssa
4. Nyt tämän kääntöelementin vasen ja oikea alaosa viedään jatkokäsittelyyn alla olevissa vaiheissa.
Kääntöelementit valitaan jälleen vasemmalle ja oikealle alaosalle erikseen. Näissä alaosissa kääntöelementit sijoitetaan oikeaan asentoonsa. Sitten vaihe 2 toistetaan. Valitse kummankin puoliskon pivot-elementti ja aseta oikea paikka rekursiota käyttämällä
Alaosat jaetaan jälleen pienempiin alaosiin, kunnes kukin osa muodostuu yhdestä elementistä.
Tässä vaiheessa taulukko on jo lajiteltu.

Quicksort käyttää rekursiota osien lajittelussa.

Divide and Conquer -lähestymistavan perusteella quicksort-algoritmi voidaan selittää seuraavasti:

Divide
Matriisi on jaettu osioihin, joissa pivot on osiointipiste. Saranaa pienemmät elementit sijoitetaan saranan vasemmalle puolelle ja saranaa suuremmat elementit oikealle.
Valloita
Vasen ja oikea alaosa jaetaan jälleen käyttämällä valitsemalla pivot-elementit heille. Tämä voidaan saavuttaa rekursiivisesti siirtämällä osiot algoritmiin.
Yhdistä
Tämä vaihe ei ole merkittävä rooli pikalajittelussa. Taulukko on lajiteltu jo valloitusvaiheen lopussa.

Voit ymmärtää quicksortin toiminnan alla olevien kuvien avulla.

Pivotin vasemmalla puolella

olevien elementtien lajittelu rekursiolla Pivotin oikealla puolella olevien elementtien lajittelu rekursiolla

Pikalajittelualgoritmi

 quickSort (taulukko, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- osio (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex, leftmostmost ) aseta rightmostIndex pivotIndex-nimeksi storeIndex <- leftmostIndex - 1 i: lle <- leftmostIndex + 1 arvoon rightmostIndex jos elementti (i) <pivotElement -vaihto-elementti (i) ja elementti (storeIndex) storeIndex ++ vaihda pivotElement ja elementti (storeIndex + 1) return storeIndex 1

Python-, Java- ja C / C ++ -esimerkkejä

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

Quicksort-monimutkaisuus

Ajan monimutkaisuus

Pahimman tapauksen monimutkaisuus (Big-O) : Se tapahtuu, kun valittu kääntöelementti on joko suurin tai pienin elementti. Tämä ehto johtaa tapaukseen, jossa kääntöelementti on lajitellun matriisin ääripäässä. Yksi alaryhmä on aina tyhjä ja toinen alaryhmä sisältää elementtejä. Siten quicksort kutsutaan vain tälle alaryhmälle. Pikalajittelualgoritmilla on kuitenkin parempi suorituskyky hajautetuille pivoteille.O(n²)
n - 1
Parhaan tapauksen monimutkaisuus (Big-omega) : O(n*log n)
Se tapahtuu, kun kääntöelementti on aina keskielementti tai lähellä keskielementtiä.
Keskimääräinen tapauksen monimutkaisuus (iso-theta) : O(n*log n)
Se tapahtuu, kun yllä olevia ehtoja ei esiinny.