Hurtig sortering i Java forklaret

Halveringskonvention

Når antallet af elementer på en liste er lige, betyder halvering af listen, at den bogstavelige første halvdel af listen er den første halvdel, og den bogstavelige anden halvdel af listen er den anden halvdel. Det midterste (midterste) element på hele listen er det sidste element i den første liste. Det betyder, at det midterste indeks er længde / 2 - 1, da indekstællingen begynder fra nul. Længde er antallet af elementer på listen. For eksempel, hvis antallet af elementer er 8, har den første halvdel af listen 4 elementer, og den anden halvdel af listen har også 4 elementer. Det er fint. Da indekstællingen begynder fra 0, er det midterste indeks 3 = 8 /2 - 1.

Hvad med sagen, når antallet af elementer på listen eller underlisten er ulige? I starten er længden stadig divideret med 2. Efter konventionen er antallet af elementer i første halvdel af denne division længde / 2 + 1/2. Indekstælling begynder fra nul. Det midterste indeks er givet ved længde / 2 - 1/2. Dette betragtes som mellemperioden efter konvention. For eksempel, hvis antallet af elementer på en liste er 5, så er det midterste indeks 2 = 5/2 - 1/2. Og der er tre elementer i første halvdel af listen og to elementer i anden halvdel. Det midterste element i hele listen er det tredje element ved indeks, 2, som er det midterste indeks, fordi indekstællingen begynder fra 0.

Division på denne måde er et eksempel på heltal aritmetik.

Median af tre værdier

Spørgsmål: Hvad er medianen for sekvensen:

C B A

Løsning:
Arranger listen i stigende rækkefølge:

A B C

Mellemtiden, B, er medianen. Det er størrelsen, der ligger mellem de to andre størrelser.

At lede efter medianen på en liste er ikke den slags. For eksempel i en liste med 19 usorterede elementer kan medianen for det første element, det midterste element og det sidste element være påkrævet. Disse tre værdier er muligvis ikke i stigende rækkefølge; og derfor skal deres indeks tages i betragtning.

Med Hurtig sortering er medianen for hele listen og underlister påkrævet. Pseudokoden til at lede efter medianen af ​​tre værdier fordelt på en liste (array) er:

Udtrykket arr betyder array. Dette kodesegment leder efter medianen og foretager også en sortering. Dette kodesegment ser enkelt ud, men det kan være ret forvirrende. Vær derfor opmærksom på følgende forklaring:

Sorteringen i denne vejledning vil producere en liste, hvor den første værdi er den mindste værdi, og den sidste værdi er den største værdi. Med alfabetet er A mindre end Z.

Her er omdrejningspunktet den resulterende median. Lav er det laveste indeks på listen eller underlisten (ikke nødvendigvis for den laveste værdi); høj er det højeste indeks på listen eller underlisten (ikke nødvendigvis for den højeste værdi), og midten er det konventionelle mellemindeks (ikke nødvendigvis for hele værdien af ​​hele listen).

Så medianen, der skal opnås, er mellem værdien af ​​det laveste indeks, værdien af ​​det midterste indeks og værdien af ​​det højeste indeks.

I koden opnås det konventionelle midterindeks først. Ved denne start er listen usorteret. Sammenligningen og en vis omlægning i stigende rækkefølge af de tre værdier skal finde sted på samme tid. Den første if-sætning sammenligner værdien for det laveste indeks og værdien for det midterste indeks. Hvis det i det midterste indeks er mindre end det for det laveste indeks, skifter de to værdier positioner. Dette begynder at sortere og ændrer arrangementet af værdier i listen eller underlisten. Den anden if-sætning sammenligner værdien for det højeste indeks og værdien for det laveste indeks. Hvis det for det højeste indeks er mindre end det for det laveste indeks, bytter de to værdier positioner. Dette fortsætter med at sortere og ændre ordningen af ​​værdier i listen eller underlisten. Den tredje if-sætning sammenligner værdien for det midterste indeks og værdien for det højeste indeks. Hvis det for det højeste indeks er mindre end det midterste indeks, skifter de to værdier positioner. En vis sortering eller omlægning kan også forekomme her. Denne tredje if-betingelse er ikke som de to foregående.

Ved afslutningen af ​​disse tre swaps ville den midterste værdi af de tre pågældende værdier være A [høj], hvis oprindelige indhold muligvis er blevet ændret i kodesegmentet. Overvej f.eks. Den usorterede sekvens:

C B A

Vi ved allerede, at medianen er B. Dette bør imidlertid bevises. Målet her er at opnå medianen af ​​disse tre værdier ved hjælp af ovenstående kodesegment. Den første if-sætning sammenligner B og C. Hvis B er mindre end C, skal positionerne for B og C byttes. B er mindre end C, så det nye arrangement bliver:

B C A

Bemærk, værdierne for det laveste indeks og det midterste indeks er ændret. Den anden if-sætning sammenligner A og B. Hvis A er mindre end B, skal positionerne for A og B byttes. A er mindre end B, så det nye arrangement bliver:

A C B

Bemærk, værdierne for det højeste indeks og det laveste indeks er ændret. Den tredje if-sætning sammenligner C og B. Hvis C er mindre end B, skal positionerne for C og B byttes. C er ikke mindre end B, så ingen udskiftning finder sted. Det nye arrangement forbliver som det tidligere, det vil sige:

A C B

B er medianen, hvilket er, A [høj], og det er drejepunktet. Så pivotten er født i den yderste ende af listen eller underlisten.

Byttefunktionen

En anden funktion, der er nødvendig for Quick Sort, er byttefunktionen. Byttefunktionen udveksler værdierne for to variabler. Pseudokoden for byttefunktionen er:

Her refererer x og y til de faktiske værdier og ikke til kopierne.

Sorteringen i denne artikel vil producere en liste, hvor den første værdi er den mindste værdi, og den sidste værdi er den største værdi.

Artikelindhold

• Hurtig sorteringsalgoritme
• En partition Pseudokode
• Illustration af hurtig sortering
• Java -kodning
• Konklusion

Hurtig sorteringsalgoritme

Den normale måde at sortere en usorteret liste på er at overveje de to første værdier. Hvis de ikke er i orden, skal du sætte dem i orden. Overvej derefter de tre første værdier. Scan de to første for at se, hvor den tredje værdi passer, og tilpass den korrekt. Overvej derefter de fire første værdier. Scan de tre første værdier for at se, hvor den fjerde værdi passer, og tilpass den korrekt. Fortsæt med denne procedure, indtil hele listen er sorteret.

Denne procedure, også kendt som brute-force-sorten, i computerprogrammeringssprog er for langsom. Quick Sort -algoritmen leveres med en meget hurtigere procedure.

Trinene til quicksort -algoritmen er som følger:

1. Sørg for, at der er mindst 2 tal at sortere på den usorterede liste.
2. Få en estimeret central værdi for listen, kaldet pivot. Medianen, som beskrevet ovenfor, er en måde at opnå drejen på. Forskellige måder kommer med deres fordele og ulemper. - Se senere.
3. Opdel listen. Det betyder, at placere pivot på listen. På en sådan måde er alle elementerne til venstre mindre end pivotværdien, og alle elementerne til højre er større end eller lig med pivotværdien. Der er forskellige måder at opdele på. Hver partitionsmetode har sine fordele og ulemper. Partitionering er deling i divider-og-erobre paradigmet.
4. Gentag trin 1, 2 og 3 rekursivt for de nye underlistepar, der dukker op, indtil hele listen er sorteret. Dette erobrer i del-og-erobre-paradigmet.

Hurtig sorterings pseudokoden er:

En partition Pseudokode

Partitionspseudokoden, der bruges i denne vejledning, er:

I illustrationen af ​​Hurtig sortering herunder bruges denne kode:

Illustration af hurtig sortering

Overvej følgende usorterede liste (matrix) med alfabetiske bogstaver:

Q W E R T Y U I O P

Ved inspektion er den sorterede liste:

E I O P Q R T U W Y

Den sorterede liste vil nu blive bevist ved hjælp af ovenstående algoritme og pseudokodesegmenter fra den usorterede liste:

Q W E R T Y U I O P

Den første pivot bestemmes ud fra arr [0] = Q, arr [4] = T og arr [9] = P og identificeres som Q og placeres yderst til højre på listen. Så listen med enhver sortering af pivotfunktioner bliver:

P W E R T Y U I O Q

Den nuværende pivot er Q. Pivotproceduren foretog en lille sortering og placerede P på den første position. Den resulterende liste skal omarrangeres (opdeles), således at alle elementerne til venstre er mindre i værdi, derefter er pivoten og alle elementerne til højre for pivoten lig med eller større end pivoten. Computeren kan ikke foretage partitionering ved inspektion. Så det gør det ved at bruge indekserne og ovenstående partitionsalgoritme.

De lave og høje indekser er nu 0 og 9. Så computeren starter med at scanne fra indekset 0, indtil det når et indeks, hvis værdi er lig med eller større end pivoten og stopper der midlertidigt. Det scanner også fra den høje (højre) ende, indeks 9, nedad, indtil det når et indeks, hvis værdi er mindre end eller lig med pivot og stopper der midlertidigt. Det betyder to stopstillinger. Hvis i, den trinvise indeksvariabel fra lav endnu ikke er lig med eller større end den faldende indeksvariabel, j fra høj, så byttes disse to værdier. I den nuværende situation stoppede scanningen fra begge ender ved W og O. Så listen bliver:

P O E R T Y U I W Q

Pivoten er stadig Q. Scanningen i modsatte retninger fortsætter og stopper i overensstemmelse hermed. Hvis i endnu ikke er lig med eller større end j, byttes de to værdier, ved hvilke scanning fra begge ender stoppede, ud. Denne gang stoppede scanningen fra begge ender ved R og I. Så arrangementet af listen bliver:

P O E I T Y U R W Q

Pivoten er stadig Q. Scanningen i modsatte retninger fortsætter og stopper i overensstemmelse hermed. Hvis i endnu ikke er lig med eller større end j, byttes de to værdier, ved hvilke scanningen stoppede. Denne gang stoppede scanningen fra begge ender ved T for i og I for j. jeg og j har mødt eller krydset. Så der kan ikke byttes. Listen forbliver den samme som:

P O E I T Y U R W Q

På dette tidspunkt skal pivoten, Q, placeres i sin endelige position i sorteringen. Dette gøres ved at bytte arr [i] med arr [høj], bytte T og Q. Listen bliver:

P O E I Q Y U R W T

På dette tidspunkt er partitionering for hele listen afsluttet. Pivot = Q har spillet sin rolle. Der er nu tre underlister, som er:

P O E I Q Y U R W T

Partitionen er division og erobring (sortering) i paradigmet. Q er i den korrekte sorteringsposition. Hvert element til venstre for Q er mindre end Q, og hvert element til højre for Q er større end Q. Den venstre liste er dog stadig ikke sorteret; og den rigtige liste er stadig ikke sorteret. Hele Quick Sort-funktionen skal kaldes rekursivt for at sortere den venstre underliste og den højre underliste. Denne tilbagekaldelse af Quick Sort skal fortsætte; nye underlister udvikler sig, indtil hele den originale liste er fuldstændig sorteret. For hver genkaldelse af Quick Sort-funktionen behandles den venstre underside først, før den tilsvarende højre underliste behandles. Der skal opnås en ny pivot for hver underliste.

Til underlisten:

P O E I

Pivoten (medianen) for P, O og I bestemmes. Pivoten ville være O. For denne underliste og for hele listen er den nye arr [lav] arr [0], og den nye arr [høj] er den sidste arr [i-1] = arr [ 4-1] = arr [3], hvor i er det sidste pivotindeks fra den forrige partition. Efter at funktionen pivot () er blevet kaldt, skal den nye pivotværdi, pivot = O. Forveksles ikke mellem pivot -funktionen og pivotværdien. Pivot-funktionen kan foretage en lille sortering og placere pivoten yderst til højre på underlisten. Denne underliste bliver,

I P E O

Med denne ordning ender pivoten altid i højre ende af underlisten eller listen efter dens funktionsopkald. Scanning fra begge ender begynder fra arr [0] og arr [3], indtil i og j mødes eller krydser. Sammenligningen foretages med pivot = O. De første stop er ved P og E. De byttes, og den nye underliste bliver:

I E P O

Scanning fra begge ender fortsætter, og de nye stop er ved P for i og ved E for j. Nu har jeg og j mødt eller krydset. Så underlisten forbliver den samme som:

I E P O

Opdelingen af ​​en underliste eller liste slutter, når pivoten er sat i sin endelige position. Så de nye værdier for arr [i] og arr [høj] byttes. Det vil sige, at P og O byttes. Den nye underliste bliver:

I E O P

O er nu på sin endelige position for hele listen. Dens rolle som omdrejningspunkt er slut. Underlisten er i øjeblikket opdelt i yderligere tre lister, som er:

I E O P

På dette tidspunkt skal Quick Sort i den første højre underliste kaldes. Det bliver dog ikke kaldt. I stedet vil det blive noteret og reserveret, for at blive ringet op senere. Da udsagnene fra partitionsfunktionen blev udført, fra toppen af ​​funktionen, er det Hurtig sortering for venstre underliste, der skal kaldes nu (efter pivot () er blevet kaldt). Det vil blive kaldt til listen:

I E

Det vil begynde med at lede efter medianen for I og E. Her skal arr [low] = I, arr [mid] = I og arr [high] = E. Så medianen, pivot, skal bestemmes af pivotalgoritmen som , I. Imidlertid vil ovenstående pseudokode bestemme pivoten som E. Denne fejl opstår her, fordi ovenstående pseudokode er beregnet til tre elementer og ikke to. I implementeringen herunder er der en vis justering af koden. Underlisten bliver,

E I

Pivoten slutter altid i højre ende af underlisten eller listen efter dens funktionsopkald. Scanning fra begge ender begynder fra arr [0] og arr [1] eksklusiv, indtil i og j mødes eller krydser. Sammenligningen foretages med pivot = I. De første og eneste stop er ved I og E: ved I for i og ved E for j. Nu har jeg og j mødt eller krydset hinanden. Så underlisten forbliver den samme som:

E I

Opdelingen af ​​en underliste eller liste slutter, når pivoten er sat i sin endelige position. Så de nye værdier for arr [i] og arr [høj] byttes. Det sker her, at arr [i] = I og arr [high] = I. Så den samme værdi byttes med sig selv. Den nye underliste bliver:

E I

Jeg er nu på den endelige position for hele listen. Dens rolle som omdrejningspunkt er slut. Underlisten er nu opdelt i yderligere to lister, som er,

E I

Nu har pivoterne hidtil været Q, O og I. Pivoter slutter ved deres endelige positioner. En underliste over et enkelt element, såsom P ovenfor, ender også ved sin endelige position.

På dette tidspunkt er den første venstre underliste blevet fuldstændig sorteret. Og sorteringsproceduren er nu på:

E I O P Q Y U R W T

Den første højre underliste:

Y U R W T

mangler stadig at blive sorteret.

Erobring af den første højre underliste
Husk, at Quick Sort-opkaldet til den første højre underliste blev noteret og reserveret i stedet for at blive udført. På dette tidspunkt vil det blive udført. Og så er den nye arr [lav] = arr [5] = arr [QPivotIndex+1], og den nye arr [høj] forbliver arr [9]. Et lignende sæt aktiviteter, der skete for den første venstre underliste, vil ske her. Og denne første højre underliste er sorteret til:

R T U W Y

Og den originale usorterede liste er blevet sorteret til:

E I O P Q R T U W Y

Java -kodning

At sætte algoritmen i Java er bare at sætte alle de ovenstående pseudokodesegmenter i Java -metoder i en klasse. Glem ikke, at der skal være en hovedmetode () i klassen, der vil kalde quicksort () -funktionen med det usorterede array.

Pivot () -metoden

Java -pivot () -metoden, der returnerer værdien, pivot, skal være:

Swap () -metoden

Swap () -metoden skal være:

Metoden Quicksort ()

Quicksort () -metoden skal være:

Partition () Metoden

Partition () metoden skal være:

Hovedmetoden ()

Hovedmetoden () kan være:

Alle ovenstående metoder kan indgå i en klasse.

Konklusion

Hurtig sortering er en sorteringsalgoritme, der bruger opdel-og-erobre-paradigmet. Det begynder med at opdele en usorteret liste i to eller tre underlister. I denne vejledning har Quick Sort opdelt en liste i tre underlister: en venstre underliste, en midterliste over et enkelt element og en højre underliste. Conquering in Quick Sort er at dele en liste eller underliste, mens du sorterer den ved hjælp af en pivotværdi. Denne vejledning har forklaret en implementering af Quick Sort på Java -computersproget.

Om forfatteren

Chrysanthus Forcha

Opdager af matematik Integration fra First Principles og relaterede serier. Kandidat i teknisk uddannelse med speciale i elektronik og computersoftware. BSc Elektronik. Jeg har også viden og erfaring på kandidatniveau i computing og telekommunikation. Ud af 20.000 forfattere var jeg den 37. bedste forfatter på devarticles.com. Jeg har arbejdet på disse områder i mere end 10 år.

RELATEREDE LINUX HINT INDLÆG

• Sammenligning af strenge i Java
• Sådan bruges HashMap i Java
• Hurtig sortering i Java forklaret
• Forhåndsbestilling af binært træ i Java
• Fletning Sorter i Java Forklaret
• Sådan bruges scanner i Java
• Java skrive til fil