Share
In deze sectie gaan we kijken naar vijf algoritmen die worden gebruikt om gegevens in een array te sorteren. We zullen beginnen met een naïef algoritme, bellen sorteren en eindigen met het meest algemene sorteeralgoritme voor algemene doeleinden, snel sorteren.
Bij elk algoritme zal ik uitleggen hoe het sorteren wordt uitgevoerd en informatie verstrekken over de beste, gemiddelde en worst case complexiteit voor zowel prestaties als geheugengebruik..
Om de code voor het sorteeralgoritme wat leesbaarder te houden, is dit een veelvoorkomende reden ruil methode wordt gebruikt door elk sorteeralgoritme dat waarden in een array op index moet omwisselen.
void Swap (T [] items, int links, int rechts) if (left! = right) T temp = items [links]; items [links] = items [rechts]; items [rechts] = temp;
| Gedrag | Sorteert de invoerarray met het bellen-sorteeralgoritme. | ||
| ingewikkeldheid | Beste zaak | Gemiddeld geval | Het slechtste geval |
| Tijd | Op) | Op2) | Op2) |
| Ruimte | O (1) | O (1) | O (1) |
Belsortering is een naïef sorteeralgoritme dat werkt door meerdere passages door de array te maken, waarbij elke keer de grootste ongesorteerde waarde naar rechts (einde) van de array wordt verplaatst.
Beschouw de volgende ongesorteerde array van gehele getallen:
Ongesorteerde array van gehele getallen Bij de eerste passage door de array worden de waarden drie en zeven vergeleken. Omdat zeven groter is dan drie, wordt er niet geruild. Vervolgens worden zeven en vier vergeleken. Zeven is groter dan vier, dus de waarden worden verwisseld, waardoor de zeven worden verplaatst, een stap dichter bij het einde van de array. De array ziet er nu als volgt uit:
De 4 en 7 hebben van positie gewisseld Dit proces wordt herhaald en de zeven worden uiteindelijk vergeleken met de achtste, die groter is, dus er kan geen uitwisseling worden uitgevoerd en de pas eindigt aan het einde van de array. Aan het einde van pass 1 ziet de array er als volgt uit:
De array aan het einde van pass 1 Omdat er ten minste één swap is uitgevoerd, wordt nog een keer uitgevoerd. Na de tweede passage zijn de zes in positie geplaatst.
De array aan het einde van pass 2 Nogmaals, omdat er ten minste één swap is uitgevoerd, wordt nog een keer gepast.
De volgende passage is echter van mening dat er geen swaps nodig waren omdat alle items in sorteervolgorde waren. Omdat er geen swaps zijn uitgevoerd, is bekend dat de array is gesorteerd en het sorteeralgoritme is voltooid.
public void Sort (T [] items) bool swapped; doen swapped = false; voor (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Swap (items, i - 1, i); verwisseld = waar; while (swapped! = false);
| Gedrag | Sorteert de invoerarray met behulp van het invoegsorteeralgoritme. | ||
| ingewikkeldheid | Beste zaak | Gemiddeld geval | Het slechtste geval |
| Tijd | Op) | Op2) | Op2) |
| Ruimte | O (1) | O (1) | O (1) |
Insertion sort werkt door een enkele passage door de array te maken en de huidige waarde in het reeds gesorteerde (begin) deel van de array in te voegen. Nadat elke index is verwerkt, is bekend dat alles wat tot nu toe is tegengekomen, is gesorteerd en alles wat volgt is onbekend.
Wacht wat?
Het belangrijkste concept is dat insertion sort werkt door items te sorteren zoals ze worden aangetroffen. Omdat het de array van links naar rechts verwerkt, weten we dat alles links van de huidige index is gesorteerd. Deze afbeelding demonstreert hoe de array wordt gesorteerd zoals elke index wordt aangetroffen:
Een array die wordt verwerkt door insertion sort Naarmate de verwerking doorgaat, wordt de array meer en meer gesorteerd totdat deze volledig is gesorteerd.
Laten we naar een concreet voorbeeld kijken. Het volgende is een ongesorteerde array die wordt gesorteerd met invoegtypen.
Ongesorteerde array van gehele getallen Wanneer het sorteerproces begint, begint het sorteeralgoritme bij index nul met de waarde drie. Aangezien er geen waarden zijn die hieraan voorafgaan, is bekend dat de array tot en met index nul gesorteerd is.
Het algoritme gaat vervolgens verder met de waarde zeven. Omdat zeven groter is dan alles in het bekende gesorteerde bereik (dat momenteel slechts drie omvat), is bekend dat de waarden tot en met zeven in sorteervolgorde zijn.
Op dit moment is bekend dat de array-indices 0-1 gesorteerd zijn en 2-n in een onbekende staat.
De waarde bij index twee (vier) wordt vervolgens gecontroleerd. Aangezien vier minder dan zeven zijn, is het bekend dat er vier naar de juiste plaats in het gesorteerde arraygebied moeten worden verplaatst. De vraag is nu naar welke index in de gesorteerde array de waarde moet worden ingevoegd. De methode om dit te doen is de FindInsertionIndex getoond in het codevoorbeeld. Deze methode vergelijkt de in te voegen waarde (vier) met de waarden in het gesorteerde bereik, beginnend bij index nul, totdat het het punt vindt waarop de waarde moet worden ingevoegd.
Deze methode bepaalt dat index één (tussen drie en zeven) het juiste invoegpunt is. Het insertie-algoritme (de invoegen methode) voert vervolgens de invoeging uit door de waarde die moet worden ingevoegd uit de array te verwijderen en alle waarden van het invoegpunt naar het verwijderde item naar rechts te verplaatsen. De array ziet er nu als volgt uit:
Array na eerste insertie-algoritme Van de array van index nul naar twee is nu bekend dat deze is gesorteerd en alles van index drie tot het einde is onbekend. Het proces begint nu opnieuw bij index drie, die de waarde vier heeft. Terwijl het algoritme doorgaat, vinden de volgende invoegingen plaats totdat de array is gesorteerd.
Array na verdere invoegalgoritmen Wanneer er geen verdere invoegingen hoeven te worden uitgevoerd of wanneer het gesorteerde gedeelte van de array de volledige array is, is het algoritme voltooid.
Accentsconagua
public void Sort (T [] items) int sortedRangeEndIndex = 1; while (gesorteerdRangeEndIndex < items.Length) if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0) int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]); Insert(items, insertIndex, sortedRangeEndIndex); sortedRangeEndIndex++; private int FindInsertionIndex(T[] items, T valueToInsert) for (int index = 0; index < items.Length; index++) if (items[index].CompareTo(valueToInsert) > 0) retourindex; gooi nieuwe InvalidOperationException ("De invoegindex werd niet gevonden"); private void Insert (T [] itemArray, int indexInsertingAt, int indexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // actions // 1: Store index at in temp temp = 4 // 2: index instellen op index van -> 0 1 2 3 5 6 3 7 temp = 4 // 3: teruglopen van index van naar index op + 1. // Verschuivingswaarden van links naar rechts een keer. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: schrijf temp. Waarde in index op + 1. // 0 1 2 3 4 5 6 7 temp = 4 // Stap 1. T temp = itemArray [indexInsertingAt]; // Stap 2. itemArray [indexInsingingAt] = itemArray [indexInsingingFrom]; // Stap 3. for (int current = indexInsertingFrom; current> indexInsertingAt; current--) itemArray [current] = itemArray [current - 1]; // Stap 4. itemArray [indexInsingingAt + 1] = temp; | Gedrag | Sorteert de invoerarray met behulp van het selectie sorteeralgoritme. | ||
| ingewikkeldheid | Beste zaak | Gemiddeld geval | Het slechtste geval |
| Tijd | Op) | Op2) | Op2) |
| Ruimte | O (1) | O (1) | O (1) |
Selectiesortering is een soort hybride tussen bellen sorteren en invoegtypen. Net als bellen sorteren, verwerkt het de array door van het begin tot het eind steeds opnieuw te itereren, één waarde te selecteren en naar de juiste locatie te verplaatsen. In tegenstelling tot bellen sorteren, kiest het echter de kleinste ongesorteerde waarde in plaats van de grootste. Net als bij invoegsortering is het gesorteerde gedeelte van de array het begin van de array, terwijl bij gesorteerd bellen het gesorteerde gedeelte aan het einde is.
Laten we eens kijken hoe dit werkt met dezelfde ongesorteerde array die we hebben gebruikt.
Ongesorteerde array van gehele getallen Bij de eerste passage gaat het algoritme proberen de kleinste waarde in de array te vinden en deze in de eerste index te plaatsen. Dit wordt uitgevoerd door de FindIndexOfSmallestFromIndex, die de index van de kleinste ongesorteerde waarde vindt beginnend bij de opgegeven index.
Met zo'n klein array kunnen we zien dat de eerste waarde, drie, de kleinste waarde is, dus deze staat al op de juiste plaats. Op dit punt weten we dat de waarde in array-index nul de kleinste waarde is en daarom in de juiste sorteervolgorde staat. Dus nu kunnen we pas twee beginnen - deze keer alleen kijkend naar de array-ingangen één tot n-1.
De tweede passage zal bepalen dat vier de kleinste waarde is in het ongesorteerde bereik, en zal de waarde in het tweede slot omwisselen met de waarde in het slot waarin vier werden vastgehouden (de vier en zeven verwisselen). Nadat twee passes zijn doorgegeven, wordt de waarde vier in de gesorteerde positie ingevoegd.
Array na tweede pass Het gesorteerde bereik is nu van index nul tot index één en het ongesorteerde bereik is van index twee tot n-1. Terwijl elke volgende passage wordt voltooid, wordt het gesorteerde gedeelte van de array groter en wordt het ongesorteerde gedeelte kleiner. Als er op enig moment onderweg geen invoegingen worden uitgevoerd, is bekend dat de array is gesorteerd. Anders gaat het proces door totdat bekend is dat de volledige array is gesorteerd.
Na nog eens twee passen wordt de array gesorteerd:
Gesorteerde array public void Sort (T [] items) int sortedRangeEnd = 0; while (gesorteerdRangeEnd < items.Length) int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd) T currentSmallest = items[sortedRangeEnd]; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) if (currentSmallest.CompareTo(items[i]) > 0) currentSmallest = items [i]; currentSmallestIndex = i; return currentSmallestIndex;
| Gedrag | Sorteert de invoerarray met behulp van het samenvoeg sorteeralgoritme. | ||
| ingewikkeldheid | Beste zaak | Gemiddeld geval | Het slechtste geval |
| Tijd | O (n log n) | O (n log n) | O (n log n) |
| Ruimte | Op) | Op) | Op) |
Tot nu toe hebben we algoritmen gezien die werken door de array lineair te verwerken. Deze algoritmen hebben het voordeel dat ze werken met zeer weinig geheugenoverhead, maar ten koste van de complexiteit van de kwadratische runtime. Met merge sort, gaan we ons eerste algoritme voor delen en veroveren bekijken.
Verdeel en heers algoritmen om grote problemen op te splitsen in kleinere, gemakkelijker oplosbare problemen. We zien dit soort algoritmen in het dagelijks leven. We gebruiken bijvoorbeeld een algoritme voor delen en veroveren bij het zoeken in een telefoonboek.
Als je de naam Erin Johnson in een telefoonboek wilde vinden, zou je niet bij A beginnen en pagina voor pagina vooruitspoelen. Integendeel, u zou waarschijnlijk het telefoonboek naar het midden openen. Als je je voor de M's zou openen, zou je een paar pagina's terugdraaien, misschien een beetje te ver, misschien de H's. Dan zou je voorwaarts klappen. En je zou in steeds kleinere stappen heen en weer blijven bladeren totdat je uiteindelijk de pagina vond die je wilde (of zo dichtbij was dat naar voren spatten zinvol was).
Hoe efficiënt zijn verdeel en heers algoritmen?
Stel dat het telefoonboek 1000 pagina's lang is. Wanneer u zich naar het midden opent, hebt u het probleem opgelost in twee problemen van 500 pagina's. Ervan uitgaande dat u niet op de juiste pagina bent, kunt u nu de juiste kant kiezen om te zoeken en het probleem in tweeën te splitsen. Nu is uw probleemruimte 250 pagina's. Omdat het probleem steeds verder wordt verminderd, kunnen we zien dat een telefoonboek van 1000 pagina's in slechts tien pagina's kan worden doorzocht. Dit is 1% van het totale aantal paginaomwentelingen dat nodig zou kunnen zijn bij het uitvoeren van een lineaire zoekopdracht.
Samenvoegen sorteren werkt door de reeks steeds in tweeën te snijden tot elk stuk maar één item lang is. Vervolgens worden deze items in sorteervolgorde weer samengevoegd (samengevoegd).
Laten we beginnen met de volgende array:
Ongesorteerde array van gehele getallen En nu snijden we de array doormidden:
Ongesorteerde array gehalveerd Nu worden beide arrays herhaaldelijk in tweeën gesneden totdat elk item op zichzelf staat:
Ongesorteerde array gehalveerd tot elke index op zichzelf staat Met de array nu verdeeld in de kleinst mogelijke delen, vindt het proces van het samenvoegen van die delen weer in sorteervolgorde plaats.
Array gesorteerd in groepen van twee De afzonderlijke items worden gesorteerde groepen van twee, die groepen van twee worden samengevoegd in gesorteerde groepen van vier, waarna ze uiteindelijk allemaal weer samenkomen als een uiteindelijke gesorteerde array.
Array gesorteerd in groepen van vier (boven) en de voltooide sortering (onder) Laten we een moment nemen om na te denken over de afzonderlijke bewerkingen die we moeten uitvoeren:
Soort methode doet dit.samensmelten methode doet dit.Een prestatie-overweging van de samenvoegsortering is dat in tegenstelling tot de lineaire sorteeralgoritmen, samenvoegselectie de gehele split- en samenvoeglogica zal uitvoeren, inclusief eventuele geheugenallocaties, zelfs als de array al in gesorteerde volgorde is. Hoewel het betere prestaties in het slechtste geval heeft dan de lineaire sorteeralgoritmen, zal de prestatie ervan in het beste geval altijd slechter zijn. Dit betekent dat het geen ideale kandidaat is bij het sorteren van gegevens waarvan bekend is dat deze bijna gesorteerd zijn; bijvoorbeeld bij het invoegen van gegevens in een reeds gesorteerde array.
public void Sort (T [] items) if (items.Length <= 1) return; int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T[] left = new T[leftSize]; T[] right = new T[rightSize]; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); private void Merge(T[] items, T[] left, T[] right) int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining > 0) if (leftIndex> = left.Length) items [targetIndex] = right [rightIndex ++]; else if (rightIndex> = right.Length) items [targetIndex] = links [leftIndex ++]; else if (left [leftIndex] .CompareTo (right [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Gedrag | Sorteert de invoerarray met behulp van het snel sorteeralgoritme. | ||
| ingewikkeldheid | Beste zaak | Gemiddeld geval | Het slechtste geval |
| Tijd | O (n log n) | O (n log n) | Op2) |
| Ruimte | O (1) | O (1) | O (1) |
Snel sorteren is een ander sorteeralgoritme voor delen en veroveren. Deze werkt door het volgende algoritme recursief uit te voeren:
Laten we een snelle sortering uitvoeren op de volgende array:
Ongesorteerde array van gehele getallen Stap één zegt dat we het partitiepunt kiezen met behulp van een willekeurige index. In de voorbeeldcode gebeurt dit op deze regel:
int pivotIndex = _pivotRng.Next (links, rechts);
Een willekeurige partitie-index kiezen Nu we de partitie-index (vier) kennen, kijken we naar de waarde op dat punt (zes) en verplaatsen we de waarden in de array zodat alles kleiner dan de waarde aan de linkerkant van de array en al het andere is (waarden groter dan of gelijk aan) wordt verplaatst naar de rechterzijde van de array. Houd er rekening mee dat het verplaatsen van de waarden in de buurt de index kan veranderen waarop de partitiewaarde wordt opgeslagen (we zullen dat binnenkort zien).
Het omwisselen van de waarden gebeurt door de partitiemethode in de voorbeeldcode.
Waarde naar links en rechts van de partitiewaarde verplaatsen Op dit moment weten we dat zes op de juiste plek in de array staan. We weten dit omdat elke waarde aan de linkerkant kleiner is dan de partitiewaarde, en alles aan de rechterkant is groter dan of gelijk aan de partitiewaarde. Nu herhalen we dit proces op de twee ongesorteerde partities van de array.
De herhaling wordt gedaan in de voorbeeldcode door de quicksort-methode recursief met elk van de array-partities te gebruiken. Merk op dat deze keer de linker array is gepartitioneerd op index één met de waarde vijf. Het proces van het verplaatsen van de waarden naar hun juiste posities verplaatst de waarde vijf naar een andere index. Ik wijs dit erop om het punt te versterken dat u een partitiewaarde selecteert, geen partitie-index.
Herhalen van het draaipunt en de partitie Snel opnieuw sorteren:
Herhaal de spil en de partitie opnieuw En nog een laatste keer snel sorteren:
Herhaal de spil en de partitie opnieuw Met slechts één ongesorteerde waarde over en omdat we weten dat elke andere waarde is gesorteerd, is de array volledig gesorteerd.
Random _pivotRng = nieuw Willekeurig (); public void Sort (T [] items) quicksort (items, 0, items.Length - 1); private void quicksort (T [] items, int links, int rechts) if (left < right) int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); private int partition(T[] items, int left, int right, int pivotIndex) T pivotValue = items[pivotIndex]; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) if (items[i].CompareTo(pivotValue) < 0) Swap(items, i, storeIndex); storeIndex += 1; Swap(items, storeIndex, right); return storeIndex;
