Share
I det här avsnittet ska vi titta på fem algoritmer som används för att sortera data i en array. Vi kommer att börja med en naiv algoritm, bubbla sortera och sluta med den vanligaste generella sorteringsalgoritmen, snabb sortering.
Med varje algoritm kommer jag att förklara hur sorteringen är klar och även ge information om bästa, genomsnittliga och värsta fallets komplexitet för både prestanda och minnesanvändning.
För att hålla sorteringsalgoritmkoden lite lättare att läsa, en vanlig Byta Metoden kommer att användas av någon sorteringsalgoritm som behöver byta värden i en array enligt index.
void swap (T [] objekt, int vänster, int höger) if (left! = right) T temp = objekt [vänster]; objekt [vänster] = objekt [höger]; objekt [höger] = temp;
| Beteende | Sorterar ingångsarray med hjälp av bubbelsortalgoritmen. | ||
| Komplexitet | Bästa fall | Genomsnittligt fall | Värsta fall |
| Tid | På) | På2) | På2) |
| Rymden | O (1) | O (1) | O (1) |
Bubbelsort är en naiv sorteringsalgoritm som fungerar genom att göra flera passeringar genom matrisen, varje gång det rör sig om det största osorterade värdet till höger (slutet) av matrisen.
Tänk på följande usorterade array av heltal:
Osorterad array av heltal På första passera genom matrisen jämförs värdena tre och sju. Eftersom sju är större än tre, utförs ingen växling. Därefter jämförs sju och fyra. Sju är större än fyra så värdena bytas, så att de sju, ett steg närmare slutet av arrayen flyttas. Serien ser nu ut så här:
4 och 7 har byta positioner Denna process upprepas och de sju så småningom hamnar i jämförelse med de åtta, vilket är större, så ingen byte kan utföras, och passet slutar i slutet av matrisen. I slutet av passera en ser arrayen ut så här:
Arrayen i slutet av passet 1 Eftersom minst en byte utfördes, utförs ett annat pass. Efter det andra passet har sex flyttat sig i position.
Arrayen i slutet av pass 2 Återigen, eftersom minst en byte utfördes utförs ett annat pass.
Nästa pass visar emellertid att inga bytesar var nödvändiga eftersom alla artiklar är i sorteringsordning. Eftersom inga swappar utfördes är känt att känt sorteras och sorteringsalgoritmen är fullständig.
public void Sortera (T [] items) bool swapped; gör swapped = false; för (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Byt (objekt, i - 1, i); swapped = true; medan (swapped! = false);
| Beteende | Sorterar ingångsarrayet med hjälp av inmatningssortalgoritmen. | ||
| Komplexitet | Bästa fall | Genomsnittligt fall | Värsta fall |
| Tid | På) | På2) | På2) |
| Rymden | O (1) | O (1) | O (1) |
Infognings sorter fungerar genom att göra ett enda pass genom matrisen och infoga det aktuella värdet i den redan sorterade (början) delen av matrisen. Efter varje index har bearbetats är det känt att allt hittat hittills är sorterat och allt som följer är okänt.
Vänta, va?
Det viktiga konceptet är att insats sorterar fungerar genom att sortera objekt som de stöter på. Eftersom det behandlar matrisen från vänster till höger vet vi att allt till vänster om det aktuella indexet är sorterat. Denna grafik visar hur arrayen sorteras när varje index uppstår:
En matris som behandlas genom inmatningssort När behandlingen fortsätter blir arrayen alltmer sorterad tills den är helt sorterad.
Låt oss titta på ett konkret exempel. Följande är en osorterad array som sorteras med inmatnings sortering.
Osorterad array av heltal När sorteringsprocessen börjar börjar sorteringsalgoritmen vid index noll med värdet tre. Eftersom det inte finns några värden som föregår detta, är arrayen till och med index noll känd att sorteras.
Algoritmen går sedan vidare till värdet sju. Eftersom sju är större än allt i det kända sorterade området (som för närvarande bara innehåller tre), är värdena upp till och med sju kända för att vara i sorteringsordning.
Vid denna tidpunkt är arrayindexerna 0-1 kända för sortering och 2-n är i ett okänt tillstånd.
Värdet på index två (fyra) kontrolleras nästa. Eftersom fyra är mindre än sju är det känt att fyra måste flyttas till sin ordinarie plats i det sorterade matrisområdet. Frågan är nu vilket index i den sorterade matrisen bör värdet införas. Metoden att göra detta är FindInsertionIndex visas i kodprovet. Den här metoden jämför det värde som ska infogas (fyra) mot värdena i det sorterade området, från början av nollpunkten tills den hittar den punkt där värdet ska införas.
Denna metod bestämmer att index ett (mellan tre och sju) är den lämpliga infogningspunkten. Införingsalgoritmen (the Föra in metod) utför sedan infogningen genom att ta bort det värde som ska införas från matrisen och skifta alla värden från infogningspunkten till det borttagna objektet till höger. Serien ser nu ut så här:
Array efter första inmatningsalgoritmen Arrayen från index noll till två är nu känd att sorteras och allt från index tre till slutet är okänt. Processen startar nu igen vid index tre, som har värdet fyra. När algoritmen fortsätter, inträffar följande infogningar tills arrayen är sorterad.
Array efter ytterligare införingsalgoritmer När det inte finns några ytterligare insatser som ska utföras, eller när den sorterade delen av matrisen är hela matrisen, är algoritmen klar.
Accentsconagua
public void Sortera (T [] items) int sortedRangeEndIndex = 1; medan (sortedRangeEndIndex < 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) returindex; kasta ny InvalidOperationException ("Inläggsindexet hittades inte"); privat tomt Infoga (T [] itemArray, int indexInsertingAt, int indexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // actions // 1: lagra index vid temp temp = 4 // 2: Ange index till index från -> 0 1 2 3 5 6 3 7 temp = 4 // 3: Gå bakåt från index från till index på + 1. // Skiftvärden från vänster till höger en gång. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: Skriv temp värde till index vid + 1. // 0 1 2 3 4 5 6 7 temp = 4 // Steg 1. T temp = itemArray [indexInsertingAt]; // Steg 2. itemArray [indexInsertingAt] = itemArray [indexInsertingFrom]; // Steg 3. för (int nuvarande = indexInsertingFrom; current> indexInsertingAt; current--) itemArray [current] = itemArray [current - 1]; // Steg 4. itemArray [indexInsertingAt + 1] = temp; | Beteende | Sorterar ingångsarray med hjälp av sorteringsalgoritmen. | ||
| Komplexitet | Bästa fall | Genomsnittligt fall | Värsta fall |
| Tid | På) | På2) | På2) |
| Rymden | O (1) | O (1) | O (1) |
Urval sortering är en typ av hybrid mellan bubbla sortering och insertion sortering. Liksom bubbelsort, behandlar den uppställningen genom att iterera från början till slutet om och om igen, plockar ett värde och flyttar det till rätt plats. I motsats till bubbelsort väljer den dock det minsta osorterade värdet i stället för det största. Liksom insättningssortimentet är den sorterade delen av matrisen början av matrisen, medan den sorterade delen med bubbelsortet är i slutet.
Låt oss se hur det här fungerar med samma osorterade array som vi har använt.
Osorterad array av heltal På första passet kommer algoritmen att försöka hitta det minsta värdet i arrayen och placera det i det första indexet. Detta utförs av FindIndexOfSmallestFromIndex, som finner indexet för det minsta osorterade värdet som börjar vid det angivna indexet.
Med ett så litet utbud kan vi säga att det första värdet, tre, är det minsta värdet så det är redan på rätt plats. Vid denna tidpunkt vet vi att värdet i array index noll är det minsta värdet, och är därför i rätt sorteringsordning. Så nu kan vi börja passera två - den här gången ser vi bara på matriserna en till n-1.
Det andra passet bestämmer att fyra är det minsta värdet i det osorterade intervallet och byter värdet i den andra spåret med värdet i spåret som fyra hölls i (byte av fyra och sju). Efter att ha passerat två kompletteringar kommer värdet fyra att sättas in i sitt sorterade läge.
Array efter andra pass Det sorterade intervallet är nu från index noll till index ett och det osorterade intervallet är från index två till n-1. När varje efterföljande pass färdigt växer den sorterade delen av matrisen större och den osorterade delen blir mindre. Om vid någon punkt under vägen ingen insättning utförs, är matrisen känd att sorteras. Annars fortsätter processen tills hela sortimentet är känt att sorteras.
Efter två passerar sorteras sorteringen:
Sorterad array public void Sortera (T [] items) int sortedRangeEnd = 0; medan (sortedRangeEnd < 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; returnera currentSmallestIndex;
| Beteende | Sorterar inmatningsraden med hjälp av sammanslagningsalgoritmen. | ||
| Komplexitet | Bästa fall | Genomsnittligt fall | Värsta fall |
| Tid | O (n log n) | O (n log n) | O (n log n) |
| Rymden | På) | På) | På) |
Hittills har vi sett algoritmer som fungerar genom att linjärt bearbeta matrisen. Dessa algoritmer har uppsidan att fungera med mycket litet minne, men på bekostnad av kvadratisk runtime komplexitet. Med sammanslagningssort kommer vi att se vår första delning och erövra algoritm.
Dela och erövra algoritmer fungerar genom att bryta ner stora problem i mindre, lättare lösliga problem. Vi ser dessa typer av algoritmer i vardagen. Till exempel använder vi en delning och erövra algoritm när du söker i en telefonbok.
Om du ville hitta namnet Erin Johnson i en telefonbok, skulle du inte börja vid A och bläddra framåt för sida. Snarare skulle du troligen öppna telefonboken till mitten. Om du öppnade till M: n, skulle du vända tillbaka några sidor, kanske lite för långt - H: s, kanske. Då skulle du vända framåt. Och du skulle fortsätta att bläddra fram och tillbaka i allt mindre steg tills du så småningom hittade den sida du ville ha (eller var så nära att vända framåt förnuftigt).
Hur effektivt delas och erövrar algoritmer?
Säg att telefonboken är 1000 sidor lång. När du öppnar till mitten har du klippt problemet i två problem med 500 sidor. Om du antar att du inte är på höger sida kan du nu välja den lämpliga sidan för att söka och skära problemet i hälften igen. Nu är ditt problemutrymme 250 sidor. Eftersom problemet skärs längre och längre fram ser vi att en 1000-sidig telefonbok kan sökas på endast tio sidvisningar. Detta är 1% av det totala antalet sidvisningar som kan vara nödvändiga vid en linjär sökning.
Sammanfoga sortera fungerar genom att skära matrisen i halv om och om igen tills varje bit endast är en sak lång. Därefter sätts dessa föremål samman (sammanslagna) i sorteringsordning.
Låt oss börja med följande array:
Osorterad array av heltal Och nu skär vi matrisen i halva:
Osorterad array skärs i hälften Nu skärs båda dessa arrays i halva upprepade gånger tills varje objekt är på egen hand:
Osorterad array skärs i halva tills varje index är på egen hand Med uppdelningen nu uppdelad i de minsta möjliga delarna uppstår processen för att slå samman dessa delar ihop i sorteringsordning.
Array sorterad i grupper om två De enskilda objekten blir sorterade grupper av två, de två grupperna sammanfogas i sorterade grupper om fyra och sedan sammanfogar de slutligen alla tillsammans som en slutlig sorterad array.
Array sorteras i grupper om fyra (översta) och den färdiga sorteringen (botten) Låt oss ta en stund att tänka på de enskilda operationer som vi behöver genomföra:
Sortera metod gör det här.Sammanfoga metod gör det här.En prestationsbedömning av sammanslagningssorten är att till skillnad från de linjära sorteringsalgoritmerna, kommer sammanslagning att utföra hela sin split- och fusionslogik, inklusive eventuella minnesallokeringar, även om arrayen redan är i sorterad ordning. Medan det har bättre värsta fall än de linjära sorteringsalgoritmerna, blir dess bästa fall prestanda alltid sämre. Det betyder att det inte är en idealisk kandidat när du sorterar data som är känd att vara nästan sorterad. till exempel när du sätter in data i en redan sorterad array.
public void Sortera (T [] objekt) om (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 ++]; annars om (rightIndex> = right.Length) items [targetIndex] = left [leftIndex ++]; annars om (vänster [leftIndex] .CompareTo (höger [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Beteende | Sorterar ingångsarray med hjälp av snabbsorteringsalgoritmen. | ||
| Komplexitet | Bästa fall | Genomsnittligt fall | Värsta fall |
| Tid | O (n log n) | O (n log n) | På2) |
| Rymden | O (1) | O (1) | O (1) |
Snabb sortering är en annan delning och erövra sorteringsalgoritmen. Den här fungerar genom att rekursivt utföra följande algoritm:
Låt oss göra en snabb sortering på följande array:
Osorterad array av heltal Steg 1 säger att vi väljer partitionspunkten med hjälp av ett slumpmässigt index. I provkoden görs detta på den här raden:
int pivotIndex = _pivotRng.Next (vänster, höger);
Plocka ett slumpmässigt partitionsindex Nu när vi känner till partitionsindexet (fyra) tittar vi på värdet vid den punkten (sex) och flyttar värdena i matrisen så att allt mindre än värdet är på vänster sida av matrisen och allt annat (värderar större än eller lika) flyttas till höger om matrisen. Tänk på att flytta värdena runt kan ändra indexet som partitionsvärdet lagras på (vi kommer snart att se det).
Bytet av värdena görs med partitionsmetoden i provkoden.
Flytta värden till vänster och höger om partitionsvärdet Vid den här tiden vet vi att sex är på rätt plats i matrisen. Vi vet detta eftersom varje värde till vänster är mindre än partitionsvärdet, och allt till höger är större än eller lika med partitionsvärdet. Nu upprepar vi denna process på arrayens två osorterade partitioner.
Upprepningen görs i provkoden genom att rekursivt ringa quicksort-metoden med var och en av grupppartitionerna. Observera att den här gången är den vänstra gruppen partitionerad på index ett med värdet fem. Processen att flytta värdena till sina lämpliga positioner flyttar värdet fem till ett annat index. Jag pekar på detta för att stärka poängen att du väljer ett partitionsvärde, inte ett partitionsindex.
Upprepa pivot och partition Snabb sortering igen:
Upprepa vrid och partition igen Och snabb sortering en sista gång:
Upprepa vrid och partition igen Med endast ett osorterat värde kvar, och eftersom vi vet att alla andra värden är sorterade, sorteras sorteringen helt.
Slumpmässig _pivotRng = ny slumpmässig (); public void Sortera (T [] objekt) quicksort (objekt, 0, items.Length - 1); privat tomt-kort (T [] poster, int vänster, int rätt) om (vänster < 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;
