Snabbsortering i Java förklaras

Halveringskonvention

När antalet element i en lista är jämnt betyder halvering av listan den bokstavliga första halvan av listan är den första halvan, och den bokstavliga andra halvan av listan är den andra halvan. Det mellersta (mellersta) elementet i hela listan är det sista elementet i den första listan. Det betyder att det mellersta indexet är längd / 2 - 1, eftersom indexräkningen börjar från noll. Längd är antalet element i listan. Till exempel, om antalet element är 8, har den första halvan av listan 4 element och den andra halvan av listan har också 4 element. Det är bra. Eftersom indexräkningen börjar från 0 är mittindexet 3 = 8 /2 - 1.

Hur är det med fallet, när antalet element i listan eller underlistan är udda? I början delas längden fortfarande med 2. Enligt konvention är antalet element i den första halvan av denna division längd / 2 + 1/2. Indexräkning börjar från noll. Det mellersta indexet anges med längden / 2 - 1/2. Detta betraktas som mellantiden, enligt konvention. Till exempel, om antalet element i en lista är 5, är det mellersta indexet 2 = 5/2 - 1/2. Och det finns tre element i listans första hälft och två element i den andra halvan. Det mellersta elementet i hela listan är det tredje elementet vid index, 2, vilket är det mellersta indexet eftersom indexräkningen börjar från 0.

Delning på detta sätt är ett exempel på heltal aritmetik.

Median av tre värden

Fråga: Vad är medianen för sekvensen:

C B A

Lösning:
Ordna listan i stigande ordning:

A B C

Mellantiden, B, är medianen. Det är storleken som ligger mellan de andra två storheterna.

Att leta efter medianen i en lista är inte den sorten. Till exempel, i en lista med 19 osorterade element kan medianen för det första elementet, mellersta elementet och det sista elementet krävas. Dessa tre värden kanske inte är i stigande ordning; och därför måste deras index beaktas.

Med Snabbsortering krävs medianen för hela listan och underlistor. Pseudokoden för att leta efter medianen för tre värden fördelade i en lista (array) är:

Termen arr betyder array. Det här kodsegmentet letar efter medianen och sorterar också. Det här kodsegmentet ser enkelt ut, men det kan vara ganska förvirrande. Så var uppmärksam på följande förklaring:

Sorteringen i den här självstudien ger en lista där det första värdet är det minsta värdet och det sista värdet är det största värdet. Med alfabetet är A mindre än Z.

Här är pivot den resulterande medianen. Låg är det lägsta indexet i listan eller underlistan (inte nödvändigtvis för det lägsta värdet); hög är det högsta indexet i listan eller underlistan (inte nödvändigtvis för det högsta värdet), och mitten är det konventionella mittindexet (inte nödvändigtvis för det mellersta värdet för hela listan).

Medianen som ska erhållas är alltså mellan värdet på det lägsta indexet, värdet på mittindexet och värdet på det högsta indexet.

I koden erhålls först det konventionella mittindexet. Vid denna start är listan osorterad. Jämförelsen och viss omorganisation i stigande ordning av de tre värdena ska ske samtidigt. Den första if-satsen jämför värdet för det lägsta indexet och det för det mellersta indexet. Om det i det mellersta indexet är mindre än det för det lägsta indexet, byter de två värdena positioner. Detta börjar sortera och ändrar ordningen av värden i listan eller underlistan. Den andra if-satsen jämför värdet för det högsta indexet och det för det lägsta indexet. Om det för det högsta indexet är lägre än det för det lägsta indexet byter de två värdena positioner. Detta fortsätter att sortera och ändra ordningen av värden i listan eller underlistan. Den tredje if-satsen jämför värdet för mittindex och värdet för det högsta indexet. Om det för det högsta indexet är mindre än det mellersta indexet byter de två värdena positioner. Viss sortering eller omorganisation kan också förekomma här. Det tredje if-villkoret är inte som de två föregående.

I slutet av dessa tre swappar skulle mittvärdet för de tre värdena i fråga vara A [hög], vars ursprungliga innehåll kan ha ändrats i kodsegmentet. Tänk till exempel på den osorterade sekvensen:

C B A

Vi vet redan att medianen är B. Detta bör dock bevisas. Syftet här är att erhålla medianen för dessa tre värden med ovanstående kodsegment. Den första if-satsen jämför B och C. Om B är mindre än C måste positionerna för B och C bytas ut. B är mindre än C, så det nya arrangemanget blir:

B C A

Observera att värdena för det lägsta indexet och det mellersta indexet har ändrats. Den andra if-satsen jämför A och B. Om A är mindre än B måste positionerna för A och B bytas ut. A är mindre än B, så det nya arrangemanget blir:

A C B

Lägg märke till att värdena för det högsta indexet och det lägsta indexet har ändrats. Den tredje if-satsen jämför C och B. Om C är mindre än B måste positionerna för C och B bytas ut. C är inte mindre än B, så ingen byte sker. Det nya arrangemanget förblir som det tidigare, det vill säga:

A C B

B är medianen, vilket är A [hög], och det är pivot. Så, pivot föds i den yttersta änden av listan eller underlistan.

Växlingsfunktionen

En annan funktion som behövs för Quick Sort är bytesfunktionen. Växlingsfunktionen, utbyter värdena för två variabler. Pseudokoden för bytesfunktionen är:

Här hänvisar x och y till de faktiska värdena och inte kopiorna.

Sorteringen i denna artikel ger en lista där det första värdet är det minsta värdet och det sista värdet är det största värdet.

Artikelinnehåll

• Snabbsorteringsalgoritm
• En partitionspseudokod
• Illustration av snabbsortering
• Java -kodning
• Slutsats

Snabbsorteringsalgoritm

Det normala sättet att sortera en osorterad lista är att överväga de två första värdena. Om de inte är i ordning, lägg dem i ordning. Tänk sedan på de tre första värdena. Skanna de två första för att se var det tredje värdet passar och passa det på lämpligt sätt. Tänk sedan på de fyra första värdena. Skanna de tre första värdena för att se var det fjärde värdet passar och passa det på lämpligt sätt. Fortsätt med denna procedur tills hela listan är sorterad.

Denna procedur, även känd som brute-force sort, i datorprogrammeringsspråk är för långsam. Snabbsorteringsalgoritmen har en mycket snabbare procedur.

Stegen för kvicksortalgoritmen är följande:

1. Se till att det finns minst 2 nummer att sortera i den osorterade listan.
2. Skaffa ett uppskattat centralt värde för listan, kallad pivot. Medianen, som beskrivits ovan, är ett sätt att erhålla svängningen. Olika sätt kommer med sina fördelar och nackdelar. - Ses senare.
3. Dela listan. Det betyder att du placerar pivoten i listan. På ett sådant sätt är alla element till vänster mindre än pivotvärdet, och alla element till höger är större än eller lika med pivotvärdet. Det finns olika sätt att partitionera. Varje partitionsmetod har sina fördelar och nackdelar. Partitionering är att dela sig i del-och-erövra paradigmet.
4. Upprepa steg 1, 2 och 3 rekursivt för de nya underlistans par som dyker upp tills hela listan är sorterad. Detta är att erövra i paradigmet divide-and-conquer.

Snabbsorteringspseudokoden är:

En partitionspseudokod

Partitionspseudokoden som används i den här självstudien är:

I illustrationen av Snabbsortering nedan används den här koden:

Illustration av snabbsortering

Tänk på följande osorterade lista (array) med alfabetiska bokstäver:

QWERTYUIOP

Genom inspektion är den sorterade listan:

E I O P Q R T U W Y

Den sorterade listan kommer nu att bevisas med hjälp av ovanstående algoritm och pseudokodsegment från den osorterade listan:

QWERTYUIOP

Den första pivoten bestäms från arr [0] = Q, arr [4] = T och arr [9] = P, och identifieras som Q och placeras längst till höger i listan. Så listan med valfri sorteringsfunktion blir:

P W E R T Y U I O Q

Den nuvarande pivoten är Q. Pivotproceduren gjorde en liten sortering och placerade P på den första positionen. Den resulterande listan måste ordnas om (partitioneras), så att alla element till vänster är mindre i värde, då är pivot och alla element till höger om pivot lika med eller större än pivot. Datorn kan inte göra partitionering genom inspektion. Så det gör det genom att använda indexen och ovanstående partitionsalgoritm.

De låga och höga indexen är nu 0 och 9. Så, datorn börjar med att skanna från index 0 tills det når ett index, vars värde är lika med eller större än pivot och stannar där tillfälligt. Den kommer också att skanna från den höga (högra) änden, index 9, nedåt, tills den når ett index vars värde är mindre än eller lika med pivot och stannar där tillfälligt. Detta innebär två hållplatser. Om i, variabeln inkrementell index, från låg ännu inte är lika med eller större än den minskande indexvariabeln, j från hög, då byts dessa två värden. I den nuvarande situationen stannade skanning från båda ändar vid W och O. Så listan blir:

P O E R T Y U I W Q

Pivot är fortfarande Q. Skanningen i motsatta riktningar fortsätter och stannar i enlighet därmed. Om i ännu inte är lika med eller större än j, byts de två värden vid vilka skanning från båda ändarna stoppades. Den här gången stannade skanning från båda ändarna vid R och I. Så blir listans ordning:

P O E I T Y U R W Q

Pivot är fortfarande Q. Skanningen i motsatta riktningar fortsätter och stannar i enlighet därmed. Om i ännu inte är lika med eller större än j, byts de två värdena vid vilka skanningen avbröts. Den här gången stannade skanning från båda ändar vid T för i och jag för j. jag och j har träffats eller korsat. Så det går inte att byta. Listan förblir densamma som:

P O E I T Y U R W Q

Vid denna punkt måste pivot, Q, placeras i sitt slutliga läge i sorteringen. Detta görs genom att byta arr [i] med arr [hög], byta T och Q. Listan blir:

P O E I Q Y U R W T

Vid denna tidpunkt har partitionering för hela listan slutat. Pivot = Q har spelat sin roll. Det finns nu tre underlistor, som är:

P O E I Q Y U R W T

Partitionen är division och erövring (sortering) i paradigmet. Q har rätt sorteringsposition. Varje element till vänster om Q är mindre än Q, och varje element till höger om Q är större än Q. Men den vänstra listan är fortfarande inte sorterad; och rätt lista är fortfarande inte sorterad. Hela snabbsorteringsfunktionen måste kallas rekursivt för att kunna sortera vänster underlista och höger underlista. Denna återkallelse av Quick Sort måste fortsätta; nya underlistor kommer att utvecklas tills hela den ursprungliga listan är helt sorterad. För varje återkallelse av snabbsorteringsfunktionen behandlas den vänstra underlistan först innan motsvarande högra underlista behandlas. En ny pivot måste erhållas för varje underlista.

För underlistan:

P O E I

Pivot (median) för P, O och I bestäms. Pivot skulle vara O. För denna underlista och för hela listan är ny arr [låg] arr [0] och ny arr [hög] är den sista arr [i-1] = arr [ 4-1] = arr [3], där i är det sista pivotindexet från föregående partition. Efter att pivot () -funktionen har anropats ska det nya pivotvärdet, pivot = O. Blanda inte mellan pivotfunktionen och pivotvärdet. Pivotfunktionen kan göra en liten sortering och placera pivoten längst ut till höger i underlistan. Denna underlista blir,

I P E O

Med detta schema slutar pivoten alltid i den högra änden av underlistan eller listan efter dess funktionsanrop. Skanning från båda ändar börjar från arr [0] och arr [3] tills i och j möts eller korsar. Jämförelsen görs med pivot = O. De första hållplatserna är vid P och E. De byts och den nya underlistan blir:

I E P O

Skanning från båda ändar fortsätter, och de nya hållplatserna är vid P för i och vid E för j. Nu har jag och j träffats eller korsat. Så underlistan förblir densamma som:

I E P O

Delningen av en underlista eller lista slutar när pivoten har placerats i sin slutliga position. De nya värdena för arr [i] och arr [hög] byts alltså. Det vill säga att P och O byts. Den nya underlistan blir:

I E O P

O är nu på sin slutliga position för hela listan. Dess roll som en pivot har slutat. Underlistan är för närvarande uppdelad i ytterligare tre listor, som är:

I E O P

Vid denna tidpunkt måste Snabbsortering av den första högra underlistan anropas. Det kommer dock inte att kallas. Istället kommer det att noteras och reserveras, för att kallas senare. När påståendena från partitionsfunktionen kördes, från toppen av funktionen, är det Snabbsortering för vänster underlista som måste anropas nu (efter att pivot () har anropats). Det kommer att kallas för listan:

I E

Det börjar med att leta efter medianen för I och E. Här, arr [low] = I, arr [mid] = I och arr [high] = E. Så medianen, pivot, bör bestämmas av pivotalgoritmen som , I. Ovanstående pseudokod kommer dock att bestämma pivoten som E. Detta fel uppstår här eftersom ovanstående pseudokod är avsedd för tre element och inte två. I implementeringen nedan finns det en viss justering av koden. Underlistan blir,

E jag

Pivot slutar alltid i den högra änden av underlistan eller listan efter dess funktionsanrop. Skanning från båda ändar börjar från arr [0] och arr [1] exklusivt tills i och j möts eller korsar. Jämförelsen görs med pivot = I. De första och enda stoppen är vid I och E: vid I för i och vid E för j. Nu har jag och j träffats eller korsat varandra. Så, underlistan förblir densamma som:

E jag

Delningen av en underlista eller lista slutar när pivoten har placerats i sin slutliga position. De nya värdena för arr [i] och arr [hög] byts alltså. Det händer här att arr [i] = I och arr [high] = I. Så samma värde byts med sig själv. Den nya underlistan blir:

E jag

Jag är nu på den slutliga positionen för hela listan. Dess roll som en pivot har slutat. Underlistan är nu uppdelad i ytterligare två listor, som är,

E jag

Nu har pivoterna hittills varit Q, O och I. Pivoter slutar på deras slutliga positioner. En underlista med ett enda element, som P ovan, slutar också vid dess slutliga position.

Vid denna tidpunkt har den första vänstra underlistan sorterats helt. Och sorteringsförfarandet är nu på:

E I O P Q Y U R W T

Första högerlistan:

Y U R W T

behöver fortfarande sorteras.

Erövrar den första högra underlistan
Kom ihåg att snabbsorteringsanropet för den första högra underlistan noterades och reserverades istället för att köras. Vid denna tidpunkt kommer det att köras. Och så, den nya arr [låg] = arr [5] = arr [QPivotIndex+1], och den nya arr [hög] förblir arr [9]. En liknande uppsättning aktiviteter som hände för den första vänstra underlistan kommer att hända här. Och den här första högra underlistan sorteras till:

R T U W Y

Och den ursprungliga osorterade listan har sorterats till:

E I O P Q R T U W Y

Java -kodning

Att sätta algoritmen i Java är bara att sätta alla ovanstående pseudokodsegment i Java -metoder i en klass. Glöm inte att det måste finnas en huvudmetod () i klassen som kallar quicksort () -funktionen med den osorterade matrisen.

Pivot () -metoden

Java pivot () -metoden som returnerar värdet, pivot, ska vara:

Swap () -metoden

Swap () -metoden ska vara:

Quicksort () -metoden

Quicksort () -metoden bör vara:

Partition () -metoden

Metoden partition () bör vara:

Huvudmetoden ()

Huvudmetoden () kan vara:

Alla ovanstående metoder kan sättas in i en klass.

Slutsats

Snabbsortering är en sorteringsalgoritm som använder paradide för dela och erövra. Det börjar med att dela upp en osorterad lista i två eller tre underlistor. I den här självstudien har Snabbsortering delat upp en lista i tre underlistor: en vänster underlista, en mittlista med ett enda element och en höger underlista. Conquering i Quick Sort är att dela upp en lista eller underlista medan du sorterar den, med hjälp av ett pivotvärde. Denna handledning har förklarat en implementering av Quick Sort på Java -datorspråket.

Om författaren

Chrysanthus Forcha

Upptäckare av matematikintegration från First Principles och relaterade serier. Magisterexamen i teknisk utbildning, specialiserat på elektronik och datorprogramvara. BSc Electronics. Jag har också kunskap och erfarenhet på masternivå i datorer och telekommunikation. Av 20 000 författare var jag den 37: e bästa författaren på devarticles.com. Jag har arbetat inom dessa områden i mer än 10 år.

RELATERADE LINUX TIPS INLÄGG

• Jämför strängar i Java
• Hur man använder HashMap i Java
• Snabbsortering i Java förklaras
• Binary Tree Preorder Traversal i Java
• Slå ihop Sortera i Java förklarat
• Hur man använder skanner i Java
• Java skriva till fil