Innehåll

• Jämförelsediagram
• Definition av Quick Sort
• Definition av Merge Sort
• Slutsats

De snabba sorterings- och sammanslagningsalgoritmerna är baserade på dividerings- och erövringsalgoritmen som fungerar på ett ganska lika sätt. Den tidigare skillnaden mellan snabb- och sammanslagningssorten är att i snabbsortering används pivotelementet för sorteringen. Å andra sidan använder sammanslagningssortering inte pivotelement för att utföra sorteringen.

Både sorteringstekniker, snabbsortering och sammanslagningssortering bygger på dividerings- och erövringsmetoden i vilken uppsättningen av element delas och kombineras sedan efter omarrangemang. Den snabba sorteringen kräver vanligtvis fler jämförelser än sammanslagningssortering för att sortera en stor uppsättning element.

1. 1. Jämförelsediagram
   2. Definition
   3. Viktiga skillnader
   4. Slutsats

Jämförelsediagram

Grund för jämförelse	Snabb sortering	Slå samman sortering
Partitionering av elementen i matrisen	Uppdelningen av en lista med element delas inte nödvändigtvis i hälften.	Array är alltid uppdelat i hälften (n / 2).
Värsta fall komplexitet	På2)	O (n log n)
Fungerar bra på	Mindre matris	Fungerar bra i alla typer av arrayer.
Fart	Snabbare än andra sorteringsalgoritmer för små datamängder.	Konsekvent hastighet i alla typer av datamängder.
Ytterligare lagringsutrymme	Mindre	Mer
Effektivitet	Ineffektivt för större matriser.	Mer effektiv.
Sorteringsmetod	Inre	Extern

Definition av Quick Sort

Snabb sortering används genomgående sorteringsalgoritm eftersom det är snabbt för de korta matriserna. Uppsättningen av elementen delas upp i delar upprepade gånger tills det inte går att dela upp det ytterligare. Snabb sortering kallas också partitionsbytesort. Den använder ett nyckelelement (känd som pivot) för att dela upp elementen. En partition innehåller de element som är mindre än nyckelelementet. En annan partition innehåller de element som är större än nyckelelementet. Elementen sorteras rekursivt.

Anta att A är ett array A, A, A, …… .., A med n-nummer som måste sorteras. Den snabba sorteringsalgoritmen består av följande steg.

1. Det första elementet eller vilket slumpmässigt element som valts som nyckel, antar nyckeln = A (1).
2. Den "låga" pekaren placeras vid den andra och "upp" -pekaren är placerad vid det sista elementet i arrayen, dvs låg = 2 och upp = n;
3. Öka konsekvent den "låga" pekaren med en position tills (A> -tangenten).
4. Avlägsna konstant “upp” -pekaren med en position tills (A <= -tangenten).
5. Om upp är större än låg växel A med A.
6. Upprepa steg 3,4 och 5 tills tillståndet i steg 5 misslyckas (dvs upp <= lågt) och byt sedan A med nyckeln.
7. Om elementen till vänster om nyckeln är mindre än nyckeln och elementen till höger om nyckeln är större än nyckeln, indelas matrisen i två undermatriser.
8. Ovanstående procedur tillämpas upprepade gånger på delområdena tills hela matrisen är sorterad.

   

   
   

Fördelar och nackdelar

Det har ett bra genomsnitt i fallfall. Den snabba sortens driftstidskomplexitet är bra, det är den är snabbare än algoritmer som bubbelsortering, insättningssortering och urvalssortering. Det är dock komplext och mycket rekursivt, det är därför det inte är lämpligt för stora matriser.

Definition av Merge Sort

Slå samman sortering är en extern algoritm som också bygger på splittring och erövringsstrategi. Elementen delas upp i delmatriser (n / 2) om och om igen tills bara ett element finns kvar, vilket avsevärt minskar sorteringstiden. Den använder extra lagring för att lagra hjälpfältet. Merge sort använder tre matriser där två används för att lagra varje hälft, och den tredje används för att lagra den slutliga sorterade listan. Varje grupp sorteras sedan rekursivt. Slutligen slås delområdena samman för att göra det till elementets storlek. Listan är alltid uppdelad i bara hälften (n / 2) som är olika för snabb sortering.

Låt A vara matrisen med n antal element som ska sorteras A, A, ..........., A. Sorteringssorteringen följer de givna stegen.

1. Dela upp matrisen A i ungefär n / 2-sorterad deluppsättning med 2, vilket innebär att elementen i (A, A), (A, A), (A, A), (A, A) undermatriser måste vara i sorterad ordning.
2. Kombinera varje par av par för att få en lista över sorterade delområden i storlek 4; elementen i delområdena är också i sorterad ordning, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Steg 2 utförs upprepade gånger tills det bara finns en sorterad matris med storlek n.

   

Fördelar och nackdelar

Sorteringsalgoritmen utförs på exakt samma och exakta sätt oavsett antalet element som är involverade i sorteringen. Det fungerar bra även med den stora datauppsättningen. Men det förbrukar större del av minnet.

1. I sammanslagningssorteringen måste matrisen delas in i bara två halvor (dvs n / 2). Till skillnad från, i snabb sortering, finns det ingen tvång att dela upp listan i lika delar.
2. Det värsta fallet med snabb sortering är O (n²) eftersom det krävs mycket fler jämförelser i värsta skick. Däremot har sammanslagningssortering samma sämsta fall och genomsnittskomplexitet, det vill säga O (n log n).
3. Merge sort kan fungera bra på alla typer av datauppsättningar oavsett om de är stora eller små. Tvärtom, den snabba sorteringen kan inte fungera bra med stora datasätt.
4. Snabbsortering är snabbare än sammanslagningssortering i vissa fall, till exempel för små datamängder.
5. Sammanfogningssortering kräver extra minnesutrymme för att lagra hjälpmatriserna. Å andra sidan kräver den snabba sorteringen inte mycket utrymme för extra lagring.
6. Slå samman är mer effektiv än snabb sortering.
7. Den snabba sorteringen är intern sorteringsmetod där data som ska sorteras justeras åt gången i huvudminnet. Omvänt är sammanslagningssorteringen extern sorteringsmetod där data som ska sorteras inte kan rymmas i minnet samtidigt och vissa måste förvaras i hjälpminnet.

Slutsats

Den snabba sorteringen är snabbare fall men är ineffektiv i vissa situationer och utför också en hel del jämförelser jämfört med sammanslagningssortering. Även om sammanslagningssortering kräver mindre jämförelse behöver den ett extra minneutrymme på 0 (n) för att lagra den extra matrisen medan snabb sortering behöver utrymme på O (log n).