QuickSort-algoritm

Innehållsförteckning

Hur fungerar QuickSort?
Snabbsorteringsalgoritm
Python, Java och C / C ++ exempel
Quicksort-komplexitet
Quicksort-applikationer

I den här handledningen lär du dig hur quicksort fungerar. Dessutom hittar du arbetsexempel på quicksort i C, C ++ Python och Java.

Quicksort är en algoritm baserad på delnings- och erövringsmetod där matrisen är uppdelad i undermatriser och dessa delmatriser kallas rekursivt för att sortera elementen.

Hur fungerar QuickSort?

Ett pivotelement väljs från matrisen. Du kan välja vilket element som helst i arrayen som pivotelement.
Här har vi tagit längst till höger (dvs. det sista elementet) i matrisen som ledelement. Välj ett pivotelement
Elementen som är mindre än pivotelementet placeras till vänster och elementen större än pivotelementet placeras till höger. Lägg alla mindre element till vänster och större till höger om svängelementet
Ovanstående arrangemang uppnås genom följande steg.
1. En pekare är fixerad vid ledelementet. Pivotelementet jämförs med elementen som börjar från det första indexet. Om elementet som är större än pivotelementet uppnås, ställs en andra pekare in för det elementet.
2. Nu jämförs ledelementet med de andra elementen (en tredje pekare). Om ett element som är mindre än pivotelementet nås, byts det mindre elementet ut med det större elementet som hittades tidigare. Jämförelse av ledelement med andra element
3. Processen pågår tills det näst sista elementet har uppnåtts.
  Slutligen byts pivotelementet ut med den andra pekaren. Byt pivotelement med den andra pekaren
4. Nu tas vänster och höger del av detta pivotelement för vidare bearbetning i stegen nedan.
Pivotelement väljs igen för vänster och höger underdel separat. Inom dessa underdelar är ledelementen placerade i rätt läge. Därefter upprepas steg 2. Välj svängelement i varje halvdel och sätt på rätt plats med rekursion
Underdelarna delas upp igen i mindre underdelar tills varje del är bildad av ett enda element.
Vid denna punkt är arrayen redan sorterad.

Quicksort använder rekursion för att sortera underdelarna.

Baserat på Divide and conquer-metoden kan quicksortsalgoritmen förklaras som:

Dela
Arrayen är uppdelad i underdelar där pivot är partitioneringspunkten. Elementen som är mindre än pivoten placeras till vänster om pivoten och elementen som är större än pivoten placeras till höger.
Erövra
De vänstra och högra delarna är åter uppdelade med hjälp av genom att välja ledelement för dem. Detta kan uppnås genom att rekordet delas in i algoritmen.
Kombinera
Detta steg spelar ingen betydande roll i snabbsort. Matrisen är redan sorterad i slutet av erövringssteget.

Du kan förstå hur quicksort fungerar med hjälp av illustrationerna nedan.

Sortera elementen till vänster om pivot med rekursion

Sortera element till höger om pivot med rekursion

Snabbsorteringsalgoritm

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndexdex, ) ställ in rightmostIndex som pivotIndex storeIndex <- leftmostIndex - 1 för i <- leftmostIndex + 1 till rightmostIndex om element (i) <pivotElement swap element (i) och element (storeIndex) storeIndex ++ swap pivotElement och element (storeIndex + 1) return store 1

Python, Java och C / C ++ exempel

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-komplexitet

Tidskomplexiteter

Värstfallskomplexitet (Big-O) : Det inträffar när det pivotelement som väljs är antingen det största eller det minsta elementet. Detta tillstånd leder till fallet där ledelementet ligger i en extrem ände av den sorterade matrisen. En undergrupp är alltid tom och en annan undergrupp innehåller element. Således kallas snabbsorter bara för denna undergrupp. Den snabba sorteringsalgoritmen har dock bättre prestanda för spridda pivoter.O(n²)
n - 1
Bästa fallkomplexitet (Big-omega) : O(n*log n)
Det inträffar när pivotelementet alltid är mittelementet eller nära mittelementet.
Genomsnittlig fallkomplexitet (Big-theta) : O(n*log n)
Det inträffar när ovanstående förhållanden inte uppstår.