QuickSort algoritms

Šajā apmācībā jūs uzzināsiet, kā darbojas quicksort. Jūs atradīsit arī darbspējīgus Cort, C ++ Python un Java piemērus.

Quicksort ir algoritms, kas balstīts uz dalīšanas un iekarošanas pieeju, kurā masīvs ir sadalīts apakšrajos, un šie apakšmasīvi tiek rekursīvi aicināti kārtot elementus.

Kā darbojas QuickSort?

  1. No masīva tiek izvēlēts pagrieziena elements. Jūs varat izvēlēties jebkuru elementu no masīva kā pagrieziena elementu.
    Šeit mēs izmantojam masīva labāko (ti, pēdējo elementu) kā pagrieziena elementu. Atlasiet pagrieziena elementu
  2. Elementi, kas ir mazāki par šarnīra elementu, tiek ievietoti kreisajā pusē, bet elementi, kas ir lielāki par šarnīra elementu, tiek novietoti pa labi. Novietojiet visus mazākos elementus kreisajā pusē un lielākos - pagrieziena elementa labajā pusē
    . Iepriekšminēto izvietojumu panāk ar šādām darbībām.
    1. Rādītājs ir fiksēts pie pagrieziena elementa. Pagrieziena elements tiek salīdzināts ar elementiem, kas sākas no pirmā indeksa. Ja tiek sasniegts elements, kas ir lielāks par pagrieziena elementu, šim elementam tiek iestatīts otrais rādītājs.
    2. Tagad pagrieziena elements tiek salīdzināts ar citiem elementiem (trešais rādītājs). Ja tiek sasniegts elements, kas ir mazāks par pagrieziena elementu, mazākais elements tiek samainīts ar iepriekš atrasto lielāko elementu. Pagrieziena elementa salīdzinājums ar citiem elementiem
    3. Process turpinās, līdz tiek sasniegts otrais pēdējais elements.
      Visbeidzot, pagrieziena elements tiek samainīts ar otro rādītāju. Apmainiet pagrieziena elementu ar otro rādītāju
    4. Tagad šī pagrieziena elementa kreisā un labā apakšdaļa tiek tālāk apstrādāti, veicot tālāk norādītās darbības.
  3. Pagrieziena elementi atkal tiek izvēlēti kreisajai un labajai apakšdaļai atsevišķi. Šajās apakšdaļās šarnīra elementi ir novietoti pareizajā stāvoklī. Pēc tam atkārtojas 2. darbība. Katrā pusē atlasiet pagrieziena elementu un ievietojiet pareizajā vietā, izmantojot rekursiju
  4. Apakšdaļas atkal tiek sadalītas mazākās apakšdaļās, līdz katra apakšdaļa sastāv no viena elementa.
  5. Šajā brīdī masīvs jau ir sakārtots.

Quicksort izmanto rekursiju, lai kārtotu apakšdaļas.

Pamatojoties uz dalīšanas un iekarošanas pieeju, ātrsortu algoritmu var izskaidrot šādi:

  • Sadalīt
    Masīvs ir sadalīts apakšdaļās, ņemot par pagrieziena punktu kā sadalīšanas punktu. Elementi, kas ir mazāki par šarnīru, tiek novietoti pa kreisi no šarnīra, bet elementi, kas ir lielāki par šarnīru, - pa labi.
  • Iekarot
    Kreisās un labās apakšdaļas atkal tiek sadalītas, izmantojot tām atlasot pagrieziena elementus. To var panākt, rekursīvi nododot apakšnodaļas algoritmā.
  • Apvienot
    Šim solim nav būtiskas nozīmes ātrsortā. Masīvs jau ir sakārtots iekarošanas soļa beigās.

Izmantojot zemāk redzamās ilustrācijas, jūs varat saprast, kā darbojas ātrsorts.

Elementu kārtošana šarnīra kreisajā pusē, izmantojot rekursiju Kārtošana elementu pagrieziena labajā pusē, izmantojot rekursiju

Ātrās šķirošanas algoritms

 quickSort (masīvs, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- nodalījums (masīvs, leftmostIndex, rightmostIndex) quickSort (masīvs, leftmostIndex, pivotIndex) quickSort (masīvs, pivotIndex, leftInmostx, pa labi ) iestatiet rightmostIndex kā pivotIndex storeIndex <- leftmostIndex - 1 i <- leftmostIndex + 1 uz rightmostIndex if elements (i) <pivotElement mijmaiņas elements (i) un elements (storeIndex) storeIndex ++ mijmaiņas pivotElement un elements (storeIndex + 1) return storeIndex 1

Python, Java un C / C ++ piemēri

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 sarežģītība

Laika sarežģītība

  • Sliktākā gadījuma sarežģītība (Big-O) : Tas notiek, ja izvēlētais šarnīra elements ir vai nu lielākais, vai mazākais elements. Šis nosacījums noved pie gadījuma, kad pagrieziena elements atrodas sakārtotā masīva galējā galā. Viens apakšmasīvs vienmēr ir tukšs, un citā apakšmasīvā ir elementi. Tādējādi quicksort tiek izsaukts tikai šajā apakšmasīvā. Tomēr ātrās šķirošanas algoritmam ir labāki rezultāti izkaisītiem rakurstiem.O(n2)
    n - 1

  • Labākā gadījuma sarežģītība (Big-omega) : O(n*log n)
    tas notiek, kad pagrieziena elements vienmēr ir vidējais elements vai tuvu vidējam elementam.
  • Vidējā gadījumu sarežģītība (lielā teta) : O(n*log n)
    tas notiek, ja iepriekš minētie apstākļi nenotiek.

Kosmosa sarežģītība

Kosmosa sarežģītība ātrsortam ir O(log n).

Quicksort lietojumprogrammas

Quicksort tiek ieviests, kad

  • programmēšanas valoda ir piemērota rekursijai
  • laika sarežģītībai ir nozīme
  • kosmosa sarežģītībai ir nozīme

Interesanti raksti...