Video: Week 4 2024
Hier kom je te weten hoe een van de meest gebruikte sorteertechnieken in Java eigenlijk werkt. Deze techniek wordt Quicksort, genoemd en het is een zeer ingenieus gebruik van recursie.
Voor de meesten van ons is het uitzoeken hoe sorteringsalgoritmen zoals QuickSort werken slechts een intellectuele oefening. De Java API heeft sortering al ingebouwd.
De QuickSort-techniek sorteert een reeks waarden met behulp van recursie. De basisstappen zijn dus:
-
Kies een willekeurige waarde die binnen het bereik van waarden in de array ligt.
Deze waarde is het draaipunt . De meest gebruikelijke manier om het draaipunt te kiezen, is door simpelweg de eerste waarde in de array te kiezen. Mensen hebben een doctorstitel geschreven over meer verfijnde manieren om een draaipunt te kiezen dat resulteert in snellere sortering. Blijf bij het gebruik van het eerste element in de array.
-
Herschik de waarden in de array zo dat alle waarden die minder zijn dan het draaipunt zich aan de linkerkant van de array bevinden en alle waarden die groter zijn dan of gelijk zijn aan het draaipunt zich aan de rechterkant van de array bevinden. matrix.
De spilwaarde geeft de grens aan tussen de linkerkant en de rechterkant van de array. Het zal waarschijnlijk geen dood punt zijn, maar dat doet er niet toe. Deze stap wordt partitionering, genoemd en de linker- en rechterzijde van de arrays zijn partities.
-
Behandel nu elk van de twee secties van de array als een afzonderlijke array en begin opnieuw met stap 1 voor die sectie.
Dat is het recursieve deel van het algoritme.
Het moeilijkste onderdeel van het QuickSort-algoritme is de partitioneringsstap, die de partitie opnieuw moet rangschikken, zodat alle waarden die kleiner zijn dan het draaipunt zich aan de linkerkant bevinden en alle elementen groter zijn dan het draaipunt punt zijn aan de rechterkant. Stel dat de array deze tien waarden heeft:
38 17 58 22 69 31 88 28 86 12
Hier is het draaipunt 38 en de taak van de partitioneringsstap is om de array anders in te delen: < 17 12 22 28 31 38 88 69 86 58
Merk op dat de waarden nog steeds niet in orde zijn. De array is echter verdeeld over de waarde 38: alle waarden die kleiner zijn dan 38 bevinden zich links van 38 en alle waarden die groter zijn dan 38 bevinden zich rechts van 38.
Nu kunt u de waarden splitsen matrix in twee partities op de waarde 38 en herhaal het proces voor elke zijde. De spilwaarde zelf hoort bij de linkerdeel, dus de linker partitie is deze:
17 12 22 28 31 38
Deze keer kiest de partitioneringsstap 17 als draaipunt en herschikt de elementen als volgt: > 12 17 22 28 31 38
Zoals u kunt zien, is dit gedeelte van de array nu gesorteerd.Helaas beseft Quicksort dat op dit moment nog niet, dus het vergt nog een paar herhalingen om zeker te zijn. Maar dat is het basisproces.
