Sorteren is een van de basisbewerkingen die we op objecten uitvoeren. Zelfs in de kindertijd wordt kinderen geleerd om te sorteren terwijl ze hun denkvaardigheden ontwikkelen. Computers en software zijn geen uitzondering. Er is een grote verscheidenheid aan sorteeralgoritmen in Java . Ik stel voor dat je uitzoekt wat ze zijn en hoe ze werken. Wat als je op een dag tijdens een interview naar een van hen wordt gevraagd?
Invoering
Het sorteren van elementen is een van de categorieën algoritmen die een ontwikkelaar moet kennen. Als informatica ooit niet serieus werd genomen toen ik op school zat, moeten de studenten van vandaag sorteeralgoritmen kunnen implementeren en begrijpen. Basisalgoritmen, de eenvoudigste, worden geïmplementeerd met behulp van een for- lus. Om een verzameling elementen, zoals een array, te sorteren, moet je natuurlijk op de een of andere manier door de verzameling gaan. Bijvoorbeeld:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Wat kan er over dit codesegment worden gezegd? We hebben een lus waarin we de index ( int i) veranderen van 0 naar het laatste element in de array. In feite nemen we gewoon elk element in de array en drukken we de inhoud ervan af. Hoe meer elementen in de array, hoe langer het duurt voordat de code is voltooid. Dat wil zeggen, als nhet aantal elementen is, wanneer n = 10het programma twee keer zo lang duurt om te draaien dan wanneer n = 5. Als ons programma een enkele lus heeft, groeit de uitvoeringstijd lineair: hoe meer elementen er zijn, hoe langer de uitvoeringstijd. Het blijkt dat het bovenstaande algoritme in lineaire tijd werkt (een lineaire functie van n). In dergelijke gevallen zeggen we dat de complexiteit van het algoritme "O(n)" is. Deze notatie wordt ook wel "grote O" of "asymptotisch gedrag" genoemd. Maar je kunt het je gewoon herinneren "
Het eenvoudigste sorteeralgoritme (bellensortering)
Stel dat we een array hebben en we kunnen er doorheen itereren. Geweldig. Laten we nu proberen het in oplopende volgorde te sorteren. Wat betekent dit? Het betekent dat gegeven twee elementen (bijvoorbeeld , a = 6) b = 5, we moeten herschikken aen bals agroter is dan b(als a > b). Wat betekent dit als we een index gebruiken om met een collectie te werken (zoals het geval is met een array)? Het betekent dat als het element met index a groter is dan het element met index b( array[a] > array[b]), de elementen moeten worden verwisseld. Er zijn verschillende manieren om van plaats te wisselen. Maar we zullen een techniek gebruiken die eenvoudig, begrijpelijk en gemakkelijk te onthouden is:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Nu kunnen we het volgende schrijven:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Zoals je kunt zien, zijn de elementen echt verwisseld. We zijn begonnen met index 1, want als de array slechts één element heeft, array[i] < array[i-1]is de uitdrukking ongeldig voor index 0. Dit beschermt ons ook tegen gevallen waarin de array geen elementen of slechts één element heeft, en het zorgt ervoor dat de code er beter uitziet. Maar de resulterende array is nog steeds niet gesorteerd, omdat één keer niet genoeg is om te sorteren. We zullen nog een lus moeten toevoegen waarin we keer op keer passen zullen uitvoeren totdat we een gesorteerde array krijgen:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Dus we hebben ons eerste sorteeralgoritme voltooid. We herhalen de buitenste lus ( while) totdat we besluiten dat er geen iteraties meer nodig zijn. Standaard gaan we er voor elke nieuwe iteratie van uit dat onze array is gesorteerd en dat we niet meer hoeven te herhalen. Dienovereenkomstig gaan we opeenvolgend door de elementen en controleren we deze aanname. Maar als de elementen niet in orde zijn, dan verwisselen we elementen en begrijpen we dat we nu geen garantie hebben dat de elementen in de juiste volgorde staan. Dit betekent dat we nog een iteratie moeten uitvoeren. Stel dat we hebben [3, 5, 2]. 5is meer dan 3- alles is goed. Maar 2is minder dan 5. Vereist echter [3, 2, 5]nog een pas, aangezien3 > 2en ze moeten worden verwisseld. Omdat we een lus in een lus gebruiken, neemt de complexiteit van ons algoritme toe. Gegeven nelementen, wordt het n * n, dat wil zeggen, O(n^2). Dit wordt kwadratische complexiteit genoemd. Over het algemeen kunnen we niet precies weten hoeveel iteraties er nodig zullen zijn. De uitdrukking van complexiteit van een algoritme laat zien hoe de complexiteit toeneemt in het slechtste geval. Dat wil zeggen, het geeft aan hoeveel de uitvoeringstijd zal toenemen naarmate het aantal elementen nverandert. Bubble sort is een van de eenvoudigste en meest inefficiënte sorteeralgoritmen. Het wordt ook wel eens "domme soort" genoemd. Materiaal over dit onderwerp:
Een ander sorteeralgoritme is selectiesortering. Het heeft ook kwadratische complexiteit, maar daarover later meer. Het idee is dus simpel. Bij elke passage selecteren we het kleinste element en verplaatsen het naar het begin. Bovendien begint elke pas een stap naar rechts. Met andere woorden, de eerste doorgang begint vanaf het nulde element, de tweede doorgang vanaf het eerste, enz. Het ziet er als volgt uit:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Deze sortering is onstabiel, omdat identieke elementen (in termen van welk kenmerk we ook gebruiken om de elementen te sorteren) hun relatieve posities kunnen veranderen. Er is een goed voorbeeld in het Wikipedia-artikel over selectiesortering . Materiaal over dit onderwerp:
Insertion sort heeft ook kwadratische complexiteit, aangezien we weer een lus binnen een lus hebben. Wat maakt invoegsortering anders? Dit sorteeralgoritme is "stabiel". Dit betekent dat identieke elementen hun relatieve volgorde niet zullen veranderen. Nogmaals, we bedoelen identiek in termen van de kenmerken waarop we sorteren.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Shuttle soort
Er is nog een eenvoudig sorteeralgoritme: shuttle sort. Dit staat ook bekend als een bidirectionele bubbelsoort of de cocktailshakersoort. Deze alternatieve namen vertellen ons dat de shuttle-soort niet over de spaceshuttle gaat. Het gaat om iets dat heen en weer beweegt. Nu kun je daaraan denken als je aan dit algoritme denkt. Wat is de essentie van het algoritme? De essentie van het algoritme is dat we van links naar rechts herhalen, elementen verwisselen en controleren of een van de elementen die in de andere richting overblijven, moet worden verwisseld.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Een ander eenvoudig sorteeralgoritme is shell sort. De kern ervan is vergelijkbaar met het sorteren van bellen, maar in elke iteratie hebben we een andere opening tussen de vergeleken elementen. Het wordt bij elke iteratie in tweeën gesneden. Hier is een implementatie:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Naast deze eenvoudige sorteeralgoritmen zijn er ook meer gecompliceerde sorteeralgoritmen. Bijvoorbeeld samenvoegen sorteren. Er zijn twee dingen om op te merken. Ten eerste komt recursie ons hier te hulp. Ten tweede is de complexiteit van het algoritme niet langer kwadratisch, zoals we gewend zijn. De complexiteit van dit algoritme is logaritmisch. Dit is geschreven als O(n log n). Dus laten we het implementeren. Eerst schrijven we een recursieve aanroep naar de sorteermethode:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Laten we nu de hoofdactie aan onze implementatie toevoegen. Dit is onze supermethode:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Wij kunnen ons voorbeeld geven door te bellenmergeSort(array, 0, array.length-1). Zoals u kunt zien, komt het proces neer op het accepteren van een invoerarray samen met indicaties van het begin en einde van de sectie die moet worden gesorteerd. Wanneer het sorteren begint, zijn dit het begin en het einde van de array. Vervolgens berekenen we het scheidingsteken, de index waar we de array zullen splitsen. Als de array in 2 delen kan worden verdeeld, dan noemen we de sorteermethode recursief voor de twee helften van de array. We bereiden een hulpbuffer voor waar we de gesorteerde sectie invoegen. Stel vervolgens de index in aan het begin van de sectie die moet worden gesorteerd en loop door elk element van de lege buffer en vul deze met de kleinste elementen. Als het element waarnaar wordt verwezen door de index kleiner is dan het element waarnaar wordt verwezen door het scheidingsteken, plaatsen we het element in de buffer en verschuiven we de index. Anders, we plaatsen het element waarnaar de begrenzer verwijst in de buffer en verschuiven de begrenzer. Zodra het scheidingsteken de grenzen van de sectie die wordt gesorteerd overschrijdt of we de hele array vullen, wordt het opgegeven bereik als gesorteerd beschouwd.Materiaal over dit onderwerp:
Een ander interessant sorteeralgoritme is het tellen van sorteringen. De algoritmische complexiteit is hier O(n+k), waar nis het aantal elementen en kis de maximale waarde van een element. Dit algoritme heeft één tekortkoming: we moeten de minimum- en maximumwaarden in de array weten. Hier is een voorbeeld van de telsoort:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
U begrijpt dat het erg onhandig is als we vooraf de minimale en maximale waarden moeten weten. En we hebben hier nog een algoritme: radix sort. Ik zal het algoritme hier alleen visueel presenteren. Zie de aanvullende materialen voor de uitvoering: Materialen:
Nou, het is tijd voor het toetje - snel sorteren, een van de beroemdste sorteeralgoritmen. Het heeft een logaritmische complexiteit: O(n log n). Dit sorteeralgoritme is ontwikkeld door Tony Hoare. Interessant genoeg vond hij het uit toen hij in de Sovjet-Unie woonde, waar hij machinevertaling studeerde aan de Universiteit van Moskou en een Russisch-Engels taalgids ontwikkelde. Bovendien gebruikt Java een complexere versie van dit algoritme in Arrays.sort. Hoe zit het met Collections.sort? Waarom zou u niet eens kijken hoe de dingen "onder de motorkap" worden gesorteerd? Hier is de code:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Dit zijn allemaal heel enge dingen, dus laten we er dieper op ingaan. Voor invoerarray ( int[]bron) maken we twee markeringen: links ( L) en rechts ( R). Tijdens de eerste methodeaanroep komen ze overeen met het begin en einde van de array. Vervolgens identificeren we het spilelement, dat de toepasselijke naam heeft pivot. Hierna is het onze taak om waarden die kleiner zijn dan pivotnaar links van te verplaatsen pivot, en grotere naar rechts. Om dit te doen, verplaatsen we eerst de Lmarkering totdat we een waarde groter dan vinden pivot. Als er geen kleinere waarde wordt gevonden, dan
L wordt gelijk aan
pivot. Vervolgens verplaatsen we de
Rmarkering totdat we een waarde vinden die kleiner is dan
pivot. Als er geen grotere waarde wordt gevonden,
Rwordt deze gelijk aan
pivot. Vervolgens, als de
Lmarkering vóór de
Rmarkering staat of ermee samenvalt, proberen we de elementen te verwisselen als het
Lelement kleiner is dan het
Relement. Dan verschuiven we
Lnaar rechts met 1, en we verschuiven
Rnaar links met 1. Wanneer de
Lmarkering voorbij de
Rmarkering komt, betekent dit dat het verwisselen voltooid is: kleinere waarden staan links van
pivot, grotere waarden staan rechts van
pivot. Hierna roepen we dezelfde sorteermethode recursief aan op de subarrays - van het begin van de te sorteren sectie tot de rechtermarkering en van de linkermarkering tot het einde van de te sorteren sectie. Waarom van het begin naar de rechter markering? Omdat aan het einde van een iteratie blijkt dat de rechtermarkering genoeg beweegt om de grens van het linkerdeel te worden. Dit algoritme is complexer dan eenvoudig sorteren, dus het is het beste om het te schetsen. Neem een wit vel papier en schrijf: 4 2 6 7 3. Schrijf dan
pivotin het midden, dus onder nummer 6. Omcirkel het. Schrijf onder 4
Len schrijf onder 3
R. 4 minder dan 6, 2 minder dan 6. We gaan uiteindelijk
Lnaar de
pivotpositie, want
Lwe kunnen er niet voorbij
pivot, volgens de voorwaarde. Schrijf opnieuw 4 2 6 7 3. Omcirkel 6 (
pivot) en zet
Leronder. Verplaats nu de
Rmarkering. 3 is minder dan 6, dus zet de
Rmarkering op 3. Aangezien 3 kleiner is dan 6 (
pivot), voeren we een
swap. Noteer het resultaat: 4 2 3 7 6. Omcirkel 6, want het is nog steeds de
pivot. De
Lmarkering staat op 3. De
Rmarkering staat op 6. Onthoud dat we de markeringen verplaatsen tot
Lvoorbij gaat
R. Ga
Lnaar het volgende nummer. Hier wil ik twee mogelijkheden verkennen: 1) het geval waarin het voorlaatste getal 7 is en 2) het geval waarin het 1 is, niet 7.
Als het voorlaatste getal 1 is: Verplaats de
Lmarkering naar 1, omdat we kunnen verplaatsen
Lzolang de
Lmarkering wijst naar een getal kleiner dan
pivot. Maar we kunnen niet
Rvan 6 af, omdat we R alleen kunnen verplaatsen als de
Rmarkering wijst naar een getal dat groter is dan
pivot. We voeren geen a uit
swap, omdat 1 kleiner is dan 6. Schrijf de huidige situatie op: 4 2 3 1 6. Omcirkel 6 (
pivot).
Lschuift voorbij
pivoten stopt met bewegen.
Rbeweegt niet. Wij doen geen ruil. Verschuiving
Len
Rmet één positie. Schrijf de
Rmarkering onder 1. De
Lmarkering is buiten de baan. Omdat
Lhet verboden terrein is, doen we niets. Maar we schrijven weer 4 2 3 1, omdat dit onze linkerkant is, die kleiner is dan
pivot(6). Selecteer de nieuwe
pivoten start alles opnieuw :)
Als het voorlaatste getal 7 is:Verplaats de
Lmarkering naar 7. We kunnen de rechter markering niet verplaatsen, omdat deze al naar het draaipunt wijst. 7 is groter dan
pivot, dus voeren we a uit
swap. Schrijf het resultaat op: 4 2 3 6 7. Omcirkel 6, want het is de
pivot. De
Lmarkering is nu verschoven naar 7, en de
Rmarkering is verschoven naar 3. Het heeft geen zin om het deel van
Lnaar het einde te sorteren, omdat er maar 1 element is. We sturen het onderdeel van 4 echter naar de
Rmarker om te sorteren. We kiezen a
pivoten beginnen helemaal opnieuw :) Op het eerste gezicht lijkt het misschien dat als je veel waarden optelt gelijk aan
pivot, dan breek je het algoritme. Maar dit is niet het geval. Je kunt lastige combinaties bedenken en jezelf op papier overtuigen dat alles klopt en je verbazen dat zulke simpele acties zo'n betrouwbaar sorteermechanisme implementeren. Het enige nadeel is dat dit sorteeralgoritme niet stabiel is. Omdat een verwisseling de relatieve volgorde van identieke elementen kan veranderen als een van hen eerder wordt aangetroffen
pivotvoordat het andere element in het vorige onderdeel wordt verwisseld
pivot.
het komt neer op
Hierboven hebben we gekeken naar een "gentleman's" set sorteeralgoritmen die in Java zijn geïmplementeerd. Algoritmen zijn over het algemeen nuttig, zowel vanuit een toegepast perspectief als om te leren denken. Sommige zijn eenvoudiger, sommige zijn ingewikkelder. Voor sommigen verdedigden slimme mensen hun proefschrift. Voor anderen schreven ze superdikke boeken. Ik hoop dat de aanvullende materialen je zullen helpen nog meer te leren, aangezien dit artikel slechts een overzicht is dat al zwaar is gebleken. En het doel is om een kleine introductie te geven. U kunt ook een inleiding tot algoritmen vinden als u
"Grokking Algorithms " leest. Ik hou ook van de afspeellijst van Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . Voor de lol kun je algoritmevisualisaties zien bij
sorteren.visualgo.net .
GO TO FULL VERSION