QuickSorti algoritm

Lang L: none (table-of-contents)

Kuidas QuickSort töötab?
Kiire sorteerimise algoritm
Pythoni, Java ja C / C ++ näited
Kiirvaliku keerukus
Quicksorti rakendused

Selles õpetuses saate teada, kuidas quicksort töötab. Samuti leiate toimivaid näiteid kiirsordist C, C ++ Pythonis ja Java keeles.

Quicksort on jagamise ja vallutamise lähenemisviisil põhinev algoritm, kus massiiv on jaotatud alamjaotisteks ja neid alammassiive kutsutakse elementide sortimiseks rekursiivselt.

Kuidas QuickSort töötab?

Massiivist valitakse pöördelement. Pivoti elemendiks saate massiivist valida mis tahes elemendi.
Siin oleme võtnud massiivi parempoolseima (st viimase elemendi) pöördelemendiks. Valige pöördelement
Pöördelemendist väiksemad elemendid pannakse vasakule ja pöördelemendist suuremad paremale. Pange kõik väiksemad elemendid pöördelemendi vasakule ja suuremale paremale
. Ülaltoodud paigutus saavutatakse järgmiste sammudega.
1. Pöördelemendi külge on kinnitatud osuti. Pöördelementi võrreldakse elementidega, mis algavad esimesest indeksist. Kui pöördelemendist suurem element saavutatakse, määratakse selle elemendi jaoks teine osuti.
2. Nüüd võrreldakse pöördelementi teiste elementidega (kolmas osuti). Kui jõutakse pöördelemendist väiksema elemendini, vahetatakse väiksem element varem leitud suurema elemendiga. Pöördelemendi võrdlus teiste elementidega
3. Protsess kestab seni, kuni on saavutatud teine viimane element.
  Lõpuks vahetatakse pöördelement teise kursoriga. Vaheta pöördelement teise kursoriga
4. Nüüd võetakse selle pöördelemendi vasak ja parem alamosa alltoodud sammude abil edasiseks töötlemiseks.
Pöördelemendid valitakse vasakule ja paremale alaosale eraldi eraldi. Nendes alaosades asetatakse pöördelemendid oma õigesse asendisse. Seejärel korratakse 2. sammu. Valige mõlemas pooles pöördelement ja pange rekursiooni abil õigesse kohta
Alaosad jagunevad jälle väiksemateks, kuni iga osa moodustub ühest elemendist.
Sel hetkel on massiiv juba sorditud.

Quicksort kasutab alaosade sorteerimiseks rekursiooni.

Jagamise ja vallutamise lähenemisviisi põhjal saab quicksorti algoritmi seletada järgmiselt:

Jaga
Massiiv jaguneb alamrühmadeks, võttes jaotuspunktiks pöördetapi. Pöördest väiksemad elemendid asetatakse pöördest vasakule ja pöördest suuremad elemendid paremale.
Valluta
Vasak ja parem alamosa jagatakse uuesti, kasutades neile pöördelemente. Seda saab saavutada rekursiivselt suunates alamrubriigid algoritmi.
Kombineeri
See samm ei mängi kiirsordis olulist rolli. Massiiv on juba vallutusetapi lõpus sorteeritud.

Järgnevate illustratsioonide abil saate aru saada kiirsordi toimimisest.

Pöördel vasakul olevate

elementide sorteerimine rekursiooni abil Pöördega paremal olevate elementide sorteerimine rekursiooni abil

Kiire sorteerimise algoritm

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partitsioon (massiiv, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex, leftInmostx, parempoolne ) määrake rightmostIndex pivotIndexi poodIndex <- leftmostIndex - 1 i jaoks <- leftmostIndex + 1 väärtusele rightmostIndex if element (i) <pivotElement vahetage element (i) ja element (storeIndex) storeIndex ++ vahetage pivotElement ja element (storeIndex + 1) return storeIndex 1

Pythoni, Java ja C / C ++ näited

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

Kiirvaliku keerukus

Aja keerukus

Halvima juhtumi keerukus (Big-O) : see juhtub siis, kui valitud pöördelement on kas suurim või väikseim element. See tingimus toob kaasa juhtumi, kus pöördelement asub sorteeritud massiivi äärmises otsas. Üks alammassiiv on alati tühi ja teine alammassiiv sisaldab elemente. Seega kutsutakse kiirkorda ainult sellel alammassiivil. Kiire sorteerimise algoritmil on aga hajutatud pöördliikmete jaoks parem jõudlus.O(n²)
n - 1
Parima juhtumi keerukus (suur-omega) : O(n*log n)
see juhtub siis, kui pöördelement on alati keskmine element või keskmise elemendi lähedal.
Keskmine juhtumi keerukus (suur-teeta) : O(n*log n)
see juhtub siis, kui ülaltoodud tingimusi ei esine.