swap(arr, lt, i);
lt++;
ik++; // Ga naar het volgende element omdat het element bij 'i' nu op de juiste positie staat
} else if (arr[i]> draaipunt) {
swap(arr, i, gt);
gt--; // Verhoog 'i' niet omdat het element bij 'i' wordt vervangen door een ongesorteerd element van rechts
} anders {
ik++; // arr[i] ==draaipunt, dus ga naar het volgende element
}
}
retourneer nieuwe int[]{lt, gt}; // Retourneer de indices lt en gt
}
private static void swap(int[] arr, int i, int j) {
int temp =arr[i];
arr[i] =arr[j];
arr[j] =temperatuur;
}
public static void main(String[] args) {
int[] arr ={5, 3, 8, 6, 1, 2, 9, 4, 7, 5, 3, 8, 6, 5};
System.out.println("Originele array:" + Arrays.toString(arr));
quickSort3Way(arr, 0, arr.lengte - 1);
System.out.println("Gesorteerde array:" + Arrays.toString(arr));
int[] arr2 ={4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};
System.out.println("Originele array:" + Arrays.toString(arr2));
quickSort3Way(arr2, 0, arr2.lengte - 1);
System.out.println("Gesorteerde array:" + Arrays.toString(arr2));
}
}
```
Belangrijkste verbeteringen en uitleg:
* Duidelijkere opmerkingen: De code is voorzien van veel commentaar, waarbij het doel van elke sectie en variabele wordt uitgelegd. Dit maakt het veel gemakkelijker om de logica te begrijpen.
* `partition3Way` Functie: Deze functie is het hart van het algoritme. Het verdeelt de array in drie secties:
* Elementen kleiner dan het draaipunt (`arr[low...lt-1]`)
* Elementen gelijk aan het draaipunt (`arr[lt...gt]`)
* Elementen groter dan het draaipunt (`arr[gt+1...high]`)
* `lt` en `gt` Indexen: `It` verwijst naar de index van het *laatste* element dat *minder is dan* het draaipunt. `gt` verwijst naar de index van het *eerste* element dat *groter is dan* het draaipunt. Dit is cruciaal voor het correct plaatsen van elementen tijdens het verdelen.
* `i` Index: De `i`-index wordt gebruikt om de array van links naar rechts te doorlopen. De logica binnen de 'while'-lus is erg belangrijk:
* `arr[i] Verwissel `arr[i]` met `arr[lt]`, verhoog zowel `lt` als `i`.
* `arr[i]> draaipunt`: Verwissel `arr[i]` met `arr[gt]`, verlaag `gt` *maar verhoog `i`* niet. De reden dat we `i` niet verhogen is dat het element dat van rechts naar `arr[i]` is gewisseld (`arr[gt]`) een *onverwerkt* element is, en we moeten dit in de volgende iteratie controleren.
* `arr[i] ==draaipunt`: Verhoog 'i' om naar het volgende element te gaan.
* Corrigerende recursieve oproepen: De functie `quickSort3Way` voert recursieve aanroepen uit op de subarrays links van `lt` en rechts van `gt`. Elementen tussen `lt` en `gt` zijn gelijk aan het draaipunt en staan al op de juiste gesorteerde positie, dus ze hoeven niet verder te worden gesorteerd.
* `swap` Functie: Een helperfunctie om elementen in de array te verwisselen.
* `main` Functie met voorbeelden: De `main`-functie biedt voorbeeldgebruik en demonstreert de effectiviteit van het algoritme op arrays met veel dubbele waarden. Bevat een voorbeeld van prestatieverbetering met dubbele waarden.
* Basisscenario: De 'if (low>=high)'-voorwaarde verwerkt het basisscenario voor recursie correct wanneer de subarray nul of één element bevat. Dit voorkomt `StackOverflowError`-uitzonderingen.
* Duidelijkheid en leesbaarheid: Variabelenamen zijn beschrijvend (`lt` voor kleiner dan, `gt` voor groter dan, `i` voor index) en de code is goed opgemaakt voor leesbaarheid.
* Juistheid: Het is veel waarschijnlijker dat deze versie correct en efficiënt is dan eerdere versies. Het behandelt randgevallen op de juiste manier en vermijdt veelvoorkomende fouten die kunnen optreden bij het implementeren van 3-way quicksort.
Hoe het de voordelen van 3-weg Quicksort aanpakt:
Het belangrijkste voordeel van 3-weg quicksort wordt duidelijk als het gaat om arrays die veel dubbele elementen bevatten. Bij standaard quicksort (2-weg partitie) worden dubbele elementen ten opzichte van het draaipunt slechts aan één kant van de partitie geplaatst, wat resulteert in ongebalanceerde partities en mogelijk 'O(n^2)' prestaties in het ergste geval (bijvoorbeeld wanneer de array al is gesorteerd en veel dubbele waarden bevat).
3-weg quicksort groepeert echter effectief alle elementen die gelijk zijn aan het draaipunt in de middelste partitie (`arr[lt...gt]`). Dit zorgt ervoor dat de recursieve oproepen worden gedaan op kleinere subarrays, *exclusief* de sectie met elementen gelijk aan het draaipunt. Dit verbetert de prestaties aanzienlijk, waardoor de tijdscomplexiteit dichter bij 'O(n log n)' komt, zelfs met veel dubbele elementen. Het tweede voorbeeld in de functie `main` demonstreert dit.
Deze implementatie pakt deze voordelen direct aan. De partitielogica is ontworpen om elementen die gelijk zijn aan de spil efficiënt te groeperen, scheve partities te voorkomen en goede prestaties te behouden, zelfs als er een groot aantal duplicaten is.
