quick sort c with examples
Snabbsort i C ++ med illustration.
Quicksort är en allmänt använd sorteringsalgoritm som väljer ett specifikt element som kallas 'pivot' och partitionerar arrayen eller listan som ska sorteras i två delar baserat på denna pivot s0 så att elementen mindre än pivoten är till vänster om listan och elementen större än pivoten är till höger om listan.
Listan är alltså uppdelad i två underlistor. Underlistorna kanske inte är nödvändiga för samma storlek. Sedan kallar Quicksort sig rekursivt för att sortera dessa två underlistor.
=> Kolla in den perfekta C ++ träningsguiden här.
Vad du kommer att lära dig:
- Introduktion
- Allmän algoritm
- Pseudokod för snabbsort
- Illustration
- C ++ Exempel
- Java-exempel
- Komplexitetsanalys av Quicksort-algoritmen
- 3-vägs snabbsort
- Slumpmässigt snabbsort
- Quicksort vs. Merge Sort
- Slutsats
- Rekommenderad läsning
Introduktion
Quicksort fungerar effektivt och snabbare även för större matriser eller listor.
I denna handledning kommer vi att utforska mer om hur Quicksort fungerar tillsammans med några programmeringsexempel på quicksort-algoritmen.
Som ett pivotvärde kan vi välja antingen första, sista eller medelvärdet eller vilket slumpmässigt värde som helst. Den allmänna idén är att i slutändan vridvärdet placeras på rätt läge i matrisen genom att flytta de andra elementen i matrisen åt vänster eller höger.
Allmän algoritm
Den allmänna algoritmen för Quicksort ges nedan.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Låt oss nu titta på pseudokoden för Quicksort-teknik.
Pseudokod för snabbsort
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Arbetet med partitioneringsalgoritmen beskrivs nedan med hjälp av ett exempel.
I den här bilden tar vi det sista elementet som pivot. Vi kan se att arrayen successivt delas upp kring pivotelementet tills vi har ett enda element i arrayen.
Nu presenterar vi en illustration av Quicksort nedan för att bättre förstå konceptet.
Illustration
Låt oss se en illustration av quicksort-algoritmen. Betrakta följande array med det sista elementet som pivot. Det första elementet är också märkt lågt och det sista elementet är högt.
Vilka är faserna i programvaruutvecklingens livscykel
Från illustrationen kan vi se att vi flyttar pekarna högt och lågt i båda ändarna av matrisen. När låga punkter till elementet är större än pivoten och höga punkter till elementet mindre än pivoten, byter vi ut dessa elementens positioner och förflyttar de låga och höga pekarna i deras respektive riktningar.
Detta görs tills de låga och höga pekarna korsar varandra. När de väl korsar varandra placeras ledelementet i rätt läge och matrisen är uppdelad i två. Sedan sorteras båda dessa underarrayer oberoende med hjälp av quicksort rekursivt.
C ++ Exempel
Nedan följer implementeringen av Quicksort-algoritmen i C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Produktion:
Inmatningsmatris
12 23 3 43 51 35 19 45
Array sorterad med quicksort
3 12 19 23 35 43 45 51
Här har vi få rutiner som används för att partitionera arrayen och anropa quicksort rekursivt för att sortera partitionen, grundläggande quicksort-funktion och verktygsfunktioner för att visa array-innehållet och byta de två elementen därefter.
Först kallar vi quicksort-funktionen med inmatningsmatrisen. Inuti quicksort-funktionen kallar vi partitionsfunktionen. I partitionsfunktionen använder vi det sista elementet som pivotelement för arrayen. När pivoten väl har bestämts delas arrayen i två delar och sedan kallas quicksort-funktionen för att oberoende sortera båda underarrayerna.
När snabbsorteringsfunktionen återvänder sorteras matrisen så att pivotelementet befinner sig på rätt plats och elementen mindre än pivoten är till vänster om pivoten och elementen större än pivoten är till höger om pivoten.
Därefter implementerar vi quicksort-algoritmen i Java.
Java-exempel
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Produktion:
Inmatningsmatris
12 23 3 43 51 35 19 45
Array efter sortering med quicksort
3 12 19 23 35 43 45 51
Även i Java-implementeringen har vi använt samma logik som vi använde vid C ++ -implementering. Vi har använt det sista elementet i arrayen när pivot och quicksort utförs på arrayen för att placera pivotelementet i rätt position.
Komplexitetsanalys av Quicksort-algoritmen
Tiden det tar för att sortera en matris beror på inmatningsmatrisen och partitionsstrategin eller metoden.
Om k är antalet element som är mindre än pivoten och n är det totala antalet element, kan den generella tiden som tas av snabbsortet uttryckas enligt följande:
T (n) = T (k) + T (n-k-1) + O (n)
den bästa mp3-nedladdaren för Android
Här är T (k) och T (n-k-1) den tid det tar av rekursiva samtal och O (n) är den tid det tar av partitioneringssamtalet.
Låt oss analysera denna tidskomplexitet för quicksort i detalj.
# 1) Värsta fall : Det värsta fallet i quicksort-teknik uppstår mest när vi väljer det lägsta eller högsta elementet i matrisen som en pivot. (I ovanstående illustration har vi valt det högsta elementet som pivot). I en sådan situation uppstår värsta fall när matrisen som ska sorteras redan är sorterad i stigande eller fallande ordning.
Därför ändras ovanstående uttryck för den totala tid som tas:
T (n) = T (0) + T (n-1) + O (n) det löser sig att Påtvå)
# 2) Bästa fallet: Det bästa fallet för quicksort uppstår alltid när det valda pivotelementet är mitten av arrayen.
Således är återfallet i bästa fall:
hur man skapar en strängmatris Java
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Genomsnittsfall: För att analysera det genomsnittliga fallet för quicksort bör vi överväga alla array-permutationer och sedan beräkna den tid det tar för var och en av dessa permutationer. I ett nötskal blir den genomsnittliga tiden för quicksort också O (nlogn).
Nedan följer de olika komplexiteten för Quicksort-teknik:
Värsta fallets tidskomplexitet O (n 2) stabilitet Inte stabilt eftersom två element med samma värden inte kommer att placeras i samma ordning. Stabilt - två element med samma värden visas i samma ordning i den sorterade utdata. Komplexitet i bästa fall O (n * log n) Genomsnittlig tidskomplexitet O (n * log n) Rymdkomplexitet O (n * log n)
Vi kan implementera quicksort på många olika sätt bara genom att ändra valet av pivotelementet (mitt, första eller sista), men i värsta fall inträffar sällan quicksort.
3-vägs snabbsort
I original quicksort-teknik väljer vi vanligtvis ett pivotelement och delar sedan arrayen i underarrayer runt denna pivot så att en underarray består av element som är mindre än pivoten och en annan består av element som är större än pivot.
Men tänk om vi väljer ett pivotelement och det finns mer än ett element i arrayen som är lika med pivot?
Till exempel, överväga följande array {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Om vi utför en enkel quicksort på den här matrisen och väljer 4 som ett pivotelement, fixar vi bara en förekomst av element 4 och resten kommer att partitioneras tillsammans med de andra elementen.
Istället, om vi använder 3-vägs quicksort, kommer vi att dela upp arrayen (l ... r) i tre underarrayer enligt följande:
- Array (l ... i) - Här är i pivot och denna array innehåller element som är mindre än pivot.
- Array (i + 1 ... j-1) - Innehåller de element som är lika med pivoten.
- Array (j… r) - Innehåller element som är större än pivoten.
Således kan 3-vägs quicksort användas när vi har mer än ett redundant element i matrisen.
Slumpmässigt snabbsort
Quicksort-tekniken kallas randomiserad quicksort-teknik när vi använder slumptal för att välja ledelement. I randomiserad kvicksort kallas det 'central pivot' och det delar upp matrisen på ett sådant sätt att varje sida har åtminstone ¼-element.
Pseudokoden för randomiserad snabbsort ges nedan:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureI ovanstående kod på 'randomQuickSort' väljer vi i steg 2 den centrala pivoten. I steg 2 är sannolikheten för att det valda elementet är det centrala ledet ½. Därför förväntas slingan i steg 2 gå två gånger. Således är tidskomplexiteten för steg 2 i randomiserad snabbsort O (n).
Att använda en slinga för att välja den centrala pivoten är inte det perfekta sättet att implementera randomiserat snabbsort. Istället kan vi slumpmässigt välja ett element och kalla det centrala pivot eller blanda om matriselementen. Den förväntade värsta fallkomplexiteten för randomiserad quicksort-algoritm är O (nlogn).
Quicksort vs. Merge Sort
I det här avsnittet kommer vi att diskutera de viktigaste skillnaderna mellan Snabbsortering och Sammanfoga sortering.
Jämförelse Parameter Snabb sortering Slå ihop sortering partitionering Matrisen är uppdelad runt ett ledelement och är inte nödvändigtvis alltid i två halvor. Den kan delas upp i valfritt förhållande. Arrayen är uppdelad i två halvor (n / 2). Värsta fallets komplexitet O (n 2) - i värsta fall krävs många jämförelser. O (nlogn) - samma som det genomsnittliga fallet Användning av datamängder Kan inte fungera bra med större datamängder. Fungerar bra med alla datamängder oavsett storlek. Ytterligare utrymme På plats - behöver inte extra utrymme. Inte på plats - behöver extra utrymme för att lagra hjälparray. Sorteringsmetod Internt - data sorteras i huvudminnet. Externt - använder externt minne för lagring av dataarrayer. Effektivitet Snabbare och effektivare för småstorlekslistor. Snabbt och effektivt för större listor. Arrays / länkade listor Mer föredraget för matriser. Fungerar bra för länkade listor.
Slutsats
Som namnet själv antyder är quicksort algoritmen som sorterar listan snabbt än någon annan sorteringsalgoritm. Precis som sammanslagningssort antar snabbsortering också en delnings- och erövringsstrategi.
Som vi redan har sett delar vi upp listan i underarrayer med hjälp av pivotelementet med hjälp av snabb sortering. Sedan sorteras dessa underarrayer oberoende. I slutet av algoritmen sorteras hela matrisen helt.
Quicksort är snabbare och fungerar effektivt för att sortera datastrukturer. Quicksort är en populär sorteringsalgoritm och föredras ibland framför algoritm för sammanslagning.
I vår nästa handledning kommer vi att diskutera mer om Shell-sortering i detalj.
=> Se upp den enkla C ++ träningsserien här.
Rekommenderad läsning
- MongoDB Sort () -metod med exempel
- Unix Sortera kommando med syntax, alternativ och exempel
- Slå ihop sortering i C ++ med exempel
- Heapsortering i C ++ med exempel
- Skalsortering i C ++ med exempel
- Urvalssortering i C ++ med exempel
- Bubblesortering i C ++ med exempel
- Insättningssortering i C ++ med exempel
