Partitionering og sortering af arrays med mange gentagne poster med Java-eksempler

1. Oversigt

Kørselstidenes kompleksitet af algoritmer er ofte afhængig af inputets art.

I denne vejledning ser vi, hvordan triviel implementering af Quicksort-algoritmen har ringe ydeevne for gentagne elementer.

Desuden lærer vi et par Quicksort-varianter til effektiv partitionering og sortering af input med en høj tæthed af duplikatnøgler.

2. Trivial Quicksort

Quicksort er en effektiv sorteringsalgoritme baseret på opdeling og erobring paradigme. Funktionelt set er det fungerer på stedet på input-arrayet og omarrangerer elementerne med enkel sammenligning og swap-handlinger.

2.1. Partitionering med enkelt drejning

En triviel implementering af Quicksort-algoritmen er stærkt afhængig af en enkelt-pivot-partitioneringsprocedure. Med andre ord deler partitionering opstillingen A = [as, ap + 1, ap + 2,…, Ar] i to dele A [p..q] og A [q + 1..r] således at:

  • Alle elementer i den første partition, A [p..q] er mindre end eller lig med pivotværdien A [q]
  • Alle elementer i den anden partition, A [q + 1..r] er større end eller lig med pivotværdien A [q]

Derefter behandles de to partitioner som uafhængige inputarrays og fodres til Quicksort-algoritmen. Lad os se Lomutos Quicksort i aktion:

2.2. Ydeevne med gentagne elementer

Lad os sige, at vi har et array A = [4, 4, 4, 4, 4, 4, 4], der har alle lige elementer.

Ved partitionering af dette array med single-pivot partitioneringsskemaet får vi to partitioner. Den første partition er tom, mens den anden partition har N-1-elementer. Yderligere, hver efterfølgende påkaldelse af partitionsproceduren reducerer kun inputstørrelsen med en. Lad os se, hvordan det fungerer:

Da delingsproceduren har lineær tidskompleksitet, er den samlede tidskompleksitet i dette tilfælde kvadratisk. Dette er det værste tilfælde for vores input-array.

3. Trevejs partitionering

For effektivt at sortere en matrix med et stort antal gentagne nøgler kan vi vælge at håndtere de samme taster mere ansvarligt. Ideen er at placere dem i den rigtige position, når vi først møder dem. Så hvad vi leder efter er en tre-partitionstilstand for arrayet:

  • Den venstre partition indeholder elementer, der er strengt mindre end partitioneringsnøglen
  • Detmidtpartition indeholder alle elementer, der er lig med partitioneringsnøglen
  • Den højre partition indeholder alle elementer, der er strengt større end partitioneringsnøglen

Vi dykker nu dybere ned i et par tilgange, som vi kan bruge til at opnå trevejs partitionering.

4. Dijkstras tilgang

Dijkstras tilgang er en effektiv måde at udføre trevejs-partitionering på. For at forstå dette, lad os se på et klassisk programmeringsproblem.

4.1. Hollandsk nationalt flagproblem

Inspireret af det nederlandske trefarvede flag foreslog Edsger Dijkstra et programmeringsproblem kaldet Dutch National Flag Problem (DNF).

I en nøddeskal er det et omlejringsproblem, hvor vi får kugler i tre farver placeret tilfældigt i en linje, og vi bliver bedt om at gruppere de samme farvede kugler sammen. Desuden skal omlægningen sikre, at grupper følger den korrekte rækkefølge.

Interessant nok gør DNF-problemet en slående analogi med 3-vejs partitionering af en matrix med gentagne elementer.

Vi kan kategorisere alle numrene i en matrix i tre grupper med hensyn til en given nøgle:

  • Den røde gruppe indeholder alle elementer, der er strengt mindre end nøglen
  • Den hvide gruppe indeholder alle elementer, der er lig med nøglen
  • Den blå gruppe indeholder alle elementer, der er strengt større end nøglen

4.2. Algoritme

En af fremgangsmåderne til at løse DNF-problemet er at vælge det første element som partitioneringsnøglen og scanne arrayet fra venstre mod højre. Når vi kontrollerer hvert element, flytter vi det til sin korrekte gruppe, nemlig Mindre, Lige og Større.

For at holde styr på vores partitioneringsfremskridt har vi brug for hjælp fra tre pegepunkter, nemlig lt, nuværendeog gt. På ethvert tidspunkt, elementerne til venstre for lt vil være strengt mindre end partitioneringsnøglen og elementerne til højre for gt vil være strengt større end nøglen.

Yderligere bruger vi nuværende markør til scanning, hvilket betyder, at alle elementer ligger mellem nuværende og gt henvisninger er endnu ikke udforsket:

Til at begynde med kan vi indstille lt og nuværende pegepinde i begyndelsen af ​​arrayet og gt pointer i slutningen af ​​det:

For hvert element læses via nuværende pointer, vi sammenligner det med partitioneringsnøglen og tager en af ​​de tre sammensatte handlinger:

  • Hvis indtast [aktuel] <-tast, så udveksler vi input [nuværende] og input [lt] og forøg begge dele nuværende og lt henvisninger
  • Hvis input [nuværende] == nøgle, så øges vi nuværende markør
  • Hvis indtast [aktuel]> -tast, så udveksler vi input [nuværende] og input [gt] og nedgang gt

Til sidst, vi stopper, når nuværende og gt pekere krydser hinanden. Med det reduceres størrelsen på den uudforskede region til nul, og vi har kun tre nødvendige partitioner.

Lad os endelig se, hvordan denne algoritme fungerer på et input-array, der har duplikatelementer:

4.3. Implementering

Lad os først skrive en hjælpeprocedure med navnet sammenligne() at lave en trevejs sammenligning mellem to tal:

offentlig statisk int sammenligning (int num1, int num2) {hvis (num1> num2) returnerer 1; ellers hvis (num1 <num2) returnerer -1; ellers returnere 0; }

Lad os derefter tilføje en metode kaldet bytte rundt() at udveksle elementer på to indekser i samme matrix:

offentlig statisk ugyldig swap (int [] array, int position1, int position2) {if (position1! = position2) {int temp = array [position1]; array [position1] = array [position2]; array [position2] = temp; }}

For entydigt at identificere en partition i matrixen har vi brug for dens venstre og højre grænseindeks. Så lad os gå videre og oprette en Skillevæg klasse:

offentlig klasse Partition {privat int venstre; privat int ret; }

Nu er vi klar til at skrive vores trevejs skillevæg() procedure:

offentlig statisk partitionspartition (int [] input, int begynder, int slut) {int lt = start, nuværende = start, gt = slut; int partitioningValue = input [start]; mens (nuværende <= gt) {int CompareCurrent = Sammenlign (input [nuværende], partitioningValue); switch (CompareCurrent) {case -1: swap (input, current ++, lt ++); pause; sag 0: nuværende ++; pause; tilfælde 1: swap (input, strøm, gt--); pause; }} returner ny partition (lt, gt); }

Lad os endelig skrive en hurtig sort () metode, der udnytter vores 3-vejs partitioneringsplan til at sortere venstre og højre partitioner rekursivt:

offentlig statisk ugyldig quicksort (int [] input, int start, int slut) {if (end <= begin) return; Partition middlePartition = partition (input, start, slut); quicksort (input, start, middlePartition.getLeft () - 1); quicksort (input, middlePartition.getRight () + 1, end); }

5. Bentley-McIlroy's tilgang

Jon Bentley og Douglas McIlroy var medforfatter til en optimeret version af Quicksort-algoritmen. Lad os forstå og implementere denne variant i Java:

5.1. Opdelingsordning

Kernen i algoritmen er en iteration-baseret partitioneringsordning. I starten er hele antallet af tal et uudforsket område for os:

Vi begynder derefter at udforske elementerne i arrayet fra venstre og højre retning. Hver gang vi går ind i eller forlader udforskningsløkken, vi kan visualisere arrayet som en sammensætning af fem regioner:

  • I de yderste to ender ligger regionerne med elementer, der er lig med partitioneringsværdien
  • Den uudforskede region forbliver i centrum, og dens størrelse bliver ved med at krympe for hver iteration
  • Til venstre for den uudforskede region ligger alle elementer mindre end partitioneringsværdien
  • På højre side af det uudforskede område er elementer, der er større end partitioneringsværdien

Til sidst ophører vores sløjfe med udforskning, når der ikke er nogen elementer, der skal udforskes længere. På dette stadium er størrelsen af ​​den uudforskede region er faktisk nul, og vi har kun fire regioner tilbage:

Næste, vi flyt alle elementerne fra de to lige regioner i midten således at der kun er en lige region i centrum, der omgiver den mindre region til venstre og den større region til højre. For at gøre det, bytter vi først elementerne i venstre lige region med elementerne i højre ende af den mindre region. Tilsvarende byttes elementerne i den højre lige region med elementerne i venstre ende af større regionen.

Endelig bliver vi det tilbage med kun tre partitioner, og vi kan yderligere bruge den samme tilgang til at opdele mindre og større regioner.

5.2. Implementering

I vores rekursive implementering af trevejs Quicksort er vi nødt til at påkalde vores partitionsprocedure for underarrays, der har et andet sæt nedre og øvre grænser. Så vores skillevæg() metoden skal acceptere tre indgange, nemlig arrayet sammen med dets venstre og højre grænse.

offentlig statisk partitionspartition (int input [], int start, int end) {// returnerer partitionsvindue}

For nemheds skyld kan vi vælg partitioneringsværdien som det sidste element i arrayet. Lad os også definere to variabler venstre = begynde og højre = ende for at udforske arrayet indad.

Yderligere skal vi også holde styr på antallet af lige elementer, der ligger længst til venstre og højre. Så lad os initialisere leftEqualKeysCount = 0 og rightEqualKeysCount = 0, og vi er nu klar til at udforske og opdele arrayet.

Først begynder vi at bevæge os fra begge retninger og finde en inversion hvor et element til venstre ikke er mindre end partitioneringsværdien, og et element til højre ikke er større end partitioneringsværdien. Derefter bytter vi de to elementer, medmindre de to markører til venstre og højre har krydset hinanden.

I hver iteration flytter vi elementer svarende til partitioningValue mod de to ender, og stig den passende tæller:

while (true) {while (input [left] partitioningValue) {if (right == begin) break; ret--; } hvis (venstre == højre && input [venstre] == partitioningValue) {swap (input, start + leftEqualKeysCount, venstre); leftEqualKeysCount ++; venstre ++; } hvis (venstre> = højre) {pause; } swap (input, venstre, højre); if (input [left] == ​​partitioningValue) {swap (input, start + leftEqualKeysCount, left); leftEqualKeysCount ++; } if (input [right] == ​​partitioningValue) {swap (input, right, end - rightEqualKeysCount); rightEqualKeysCount ++; } venstre ++; ret--; }

I den næste fase skal vi flyt alle de lige elementer fra de to ender i midten. Når vi forlader sløjfen, vil venstrepegeren være ved et element, hvis værdi ikke er mindre end partitioningValue. Ved hjælp af denne kendsgerning begynder vi at flytte lige elementer fra de to ender mod midten:

højre = venstre - 1; for (int k = start; k = start + leftEqualKeysCount) swap (input, k, højre); } for (int k = end; k> end - rightEqualKeysCount; k--, left ++) {if (left <= end - rightEqualKeysCount) swap (input, left, k); } 

I den sidste fase kan vi returnere grænserne for den midterste partition:

returner ny partition (højre + 1, venstre - 1);

Lad os endelig tage et kig på en demonstration af vores implementering på et eksempel på input

6. Algoritmeanalyse

Generelt har Quicksort-algoritmen en gennemsnitskompleksitetstid på O (n * log (n)) og worst-case tidskompleksitet på O (n2). Med en høj tæthed af duplikatnøgler får vi næsten altid worst-case ydeevne med den trivielle implementering af Quicksort.

Men når vi bruger trevejs-partitioneringsvarianten af ​​Quicksort, såsom DNF-partitionering eller Bentleys partitionering, er vi i stand til at forhindre den negative effekt af duplikatnøgler. Efterhånden som densiteten af ​​duplikatnøgler øges, forbedres ydeevnen af ​​vores algoritme også. Som et resultat får vi den bedste ydeevne, når alle nøgler er ens, og vi får en enkelt partition, der indeholder alle lige nøgler i lineær tid.

Ikke desto mindre skal vi bemærke, at vi i det væsentlige tilføjer overhead, når vi skifter til en trevejs partitioneringsplan fra den trivielle single-pivot partitionering.

For DNF-baseret tilgang afhænger omkostningerne ikke af tætheden af ​​gentagne nøgler. Så hvis vi bruger DNF-partitionering til et array med alle unikke nøgler, får vi dårlig ydeevne sammenlignet med den trivielle implementering, hvor vi optimalt vælger omdrejningspunktet.

Men Bentley-McIlroy's tilgang gør en smart ting, da omkostningerne ved at flytte lige nøgler fra de to ekstreme ender afhænger af deres antal. Som et resultat, hvis vi bruger denne algoritme til en matrix med alle unikke nøgler, selv da, får vi rimelig god ydelse.

Sammenfattende er den værst tænkelige tidskompleksitet for både single-pivot partitionering og tre-vejs partitioneringsalgoritmer O (nlog (n)). Imidlertid, den virkelige fordel er synlig i de bedste tilfælde, hvor vi ser tidskompleksiteten gå fra O (nlog (n)) til en-drejelig partitionering til På) til trevejs partitionering.

7. Konklusion

I denne vejledning lærte vi om præstationsproblemerne med den trivielle implementering af Quicksort-algoritmen, når input har et stort antal gentagne elementer.

Med en motivation til at løse dette problem, vi lært forskellige trevejs partitioneringsordninger og hvordan vi kan implementere dem i Java.

Som altid er den komplette kildekode til Java-implementeringen, der bruges i denne artikel, tilgængelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found