Share
I denne delen skal vi se på fem algoritmer som brukes til å sortere data i en matrise. Vi vil starte med en naiv algoritme, boble sorter, og slutte med den vanligste generell sorteringsalgoritmen, rask sortering.
Med hver algoritme vil jeg forklare hvordan sorteringen er gjort og også gi informasjon om beste, gjennomsnittlige og verste kompleksiteten for både ytelse og minnebruk.
For å holde sorteringsalgoritmkoden litt enklere å lese, en vanlig Bytte Metoden vil bli brukt av en hvilken som helst sorteringsalgoritme som må bytte verdier i en tabell etter indeks.
void swap (T [] elementer, int venstre, int høyre) if (left! = right) T temp = elementer [left]; elementer [venstre] = elementer [høyre]; elementer [høyre] = temp;
| Oppførsel | Sorterer inngangsarmen ved hjelp av boble sorteringsalgoritmen. | ||
| kompleksitet | Beste sak | Gjennomsnittlig sak | Verste tilfelle |
| Tid | På) | På2) | På2) |
| Rom | O (1) | O (1) | O (1) |
Bubblesort er en naiv sorteringsalgoritme som opererer ved å lage flere passeringer gjennom arrayet, hver gang du flytter den største usorterte verdien til høyre (enden) av gruppen.
Vurder følgende usorterte utvalg av heltall:
Usortert utvalg av heltall På første passering gjennom arrayet, sammenlignes verdiene tre og syv. Siden sju er større enn tre, utføres ingen bytte. Deretter sammenlignes syv og fire. Sju er større enn fire, slik at verdiene blir byttet og dermed beveger de syv, ett trinn nærmere slutten av arrayet. Arrayet ser nå ut som dette:
De 4 og 7 har bytte posisjoner Denne prosessen gjentas, og de syv til slutt blir sammenlignet med de åtte, som er større, så ingen bytte kan utføres, og passet ender på slutten av gruppen. På slutten av pass en ser arrayen slik ut:
Arrangementet på slutten av pass 1 Fordi minst en bytte ble utført, vil et annet pass utføres. Etter det andre passet har de seks beveget seg i posisjon.
Arrangementet på slutten av pass 2 Igjen, fordi minst en bytte ble utført, utføres et annet pass.
Det neste passet finner imidlertid at det ikke var behov for bytteavtaler fordi alle elementene er i sort-rekkefølge. Siden ingen swaps ble utført, er array kjent for å bli sortert og sorteringsalgoritmen er fullført.
offentlig tomrom Sorter (T [] elementer) bool byttet; gjør swapped = false; for (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Bytte (elementer, i - 1, i); byttet = true; mens (swapped! = false);
| Oppførsel | Sorter innmatingsarray ved hjelp av innføringssortalgoritmen. | ||
| kompleksitet | Beste sak | Gjennomsnittlig sak | Verste tilfelle |
| Tid | På) | På2) | På2) |
| Rom | O (1) | O (1) | O (1) |
Innsats sorterer fungerer ved å lage et enkelt pass gjennom arrayet og sette inn gjeldende verdi i den allerede sorterte (begynnende) delen av arrayet. Etter at hver indeks er behandlet, er det kjent at alt som oppstått hittil er sortert, og alt som følger er ukjent.
Vent, hva?
Det viktige konseptet er at innsetting sorterer fungerer ved å sortere elementer som de oppdages. Siden det behandler oppsettet fra venstre til høyre, vet vi at alt til venstre for gjeldende indeks er sortert. Denne grafikken viser hvordan arrayet blir sortert etter hvert som hver indeks oppstår:
En matrise som blir behandlet ved å sette inn sortering Når behandlingen fortsetter, blir arrayet mer og mer sortert til den er helt sortert.
La oss se på et konkret eksempel. Følgende er et usortert array som vil bli sortert ved hjelp av innsettings sortering.
Usortert utvalg av heltall Når sorteringsprosessen begynner, starter sorteringsalgoritmen ved indeks null med verdien tre. Siden det ikke er noen verdier som går foran dette, er det kjent at arrayet til og med indeks null er sortert.
Algoritmen beveger seg deretter til verdien sju. Siden sju er større enn alt i det kjente sorterte området (som for øyeblikket bare inneholder tre), er verdiene opp til og med syv kjent for å være i sort rekkefølge.
På dette tidspunkt er arrayindeksene 0-1 kjent for å bli sortert, og 2-n er i en ukjent tilstand.
Verdien på indeks to (fire) er merket neste. Siden fire er mindre enn syv, er det kjent at fire må flyttes til riktig sted i det sorterte arrayområdet. Spørsmålet er nå hvilken indeks i den sorterte gruppen hvis verdien skal settes inn. Metoden for å gjøre dette er FindInsertionIndex vist i kodeprøven. Denne metoden sammenligner verdien som skal settes inn (fire) mot verdiene i sortert rekkevidde, starter ved indeks null, til den finner punktet hvor verdien skal settes inn.
Denne metoden bestemmer at indeks en (mellom tre og syv) er riktig innsettingspunkt. Innføringsalgoritmen (the Sett inn metode) utfører deretter innføringen ved å fjerne verdien som skal settes inn fra matrisen og skifte alle verdiene fra innsettingspunktet til det fjernede elementet til høyre. Arrayet ser nå ut som dette:
Array etter første innføringsalgoritme Arrayet fra indeksen null til to er nå kjent for å bli sortert, og alt fra indeks tre til slutten er ukjent. Prosessen starter nå igjen på indeks tre, som har verdien fire. Som algoritmen fortsetter, skjer følgende innstillinger til arrayet er sortert.
Array etter ytterligere innsettingsalgoritmer Når det ikke er noen ytterligere innføringer som skal utføres, eller når den sorterte delen av arrayet er hele gruppen, er algoritmen ferdig.
Accentsconagua
offentlig tomrom Sorter (T [] elementer) int sortedRangeEndIndex = 1; mens (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) returindeks; kaste ny InvalidOperationException ("Innsettingsindeksen ble ikke funnet"); private void Sett inn (T [] itemArray, int indexInsertingAt, int indexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // handlinger // 1: Lagre indeks på temp temp = 4 // 2: Angi indeks til å indeksere fra -> 0 1 2 3 5 6 3 7 temp = 4 // 3: Gå bakover fra indeks fra til indeks på + 1. // Skiftverdier fra venstre til høyre en gang. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: Skriv temp verdi til indeks på + 1. // 0 1 2 3 4 5 6 7 temp = 4 // Trinn 1. T temp = itemArray [indexInsertingAt]; // Trinn 2. itemArray [indexInsertingAt] = itemArray [indexInsertingFrom]; // Trinn 3. for (int current = indexInsertingFrom; current> indexInsertingAt; nåværende--) itemArray [current] = itemArray [current - 1]; // Step 4. itemArray [indexInsertingAt + 1] = temp; | Oppførsel | Sorter innmatingsarray ved hjelp av utvalgsortalgoritmen. | ||
| kompleksitet | Beste sak | Gjennomsnittlig sak | Verste tilfelle |
| Tid | På) | På2) | På2) |
| Rom | O (1) | O (1) | O (1) |
Valg sortering er en slags hybrid mellom boble sortering og innføring sortering. Som boble sorterer, behandler den oppstillingen ved å iterere fra start til slutt om og om igjen, plukke en verdi og flytte den til riktig sted. I motsetning til boble sorter velger den den minste usorterte verdien heller enn den største. I likhet med innførings sorter, er den sorterte delen av arrayet starten av arrayet, mens med boble sorter er den sorterte delen på slutten.
La oss se hvordan dette fungerer med samme usorterte array som vi har brukt.
Usortert utvalg av heltall På første pass, vil algoritmen forsøke å finne den minste verdien i arrayet og plassere den i den første indeksen. Dette utføres av FindIndexOfSmallestFromIndex, som finner indeksen for den minste usorterte verdien som starter ved den angitte indeksen.
Med et så lite utvalg kan vi fortelle at den første verdien, tre, er den minste verdien, så den er allerede på riktig sted. På dette tidspunktet vet vi at verdien i arrayindeks null er den minste verdien, og er derfor i riktig sorteringsrekkefølge. Så nå kan vi begynne å passere to - denne gangen ser vi bare på arrayoppføringene en til n-1.
Det andre passet bestemmer at fire er den minste verdien i usortert rekkevidde, og vil bytte verdien i den andre sporet med verdien i sporet som fire ble holdt i (bytte de fire og syv). Etter å ha bestått to kompletter, vil verdien fire bli satt inn i sin sorterte posisjon.
Array etter andre pass Det sorterte området er nå fra indeks null til indeks ett, og det usorterte området er fra indeks to til n-1. Når hver etterfølgende pass er ferdig, vokser den sorterte delen av gruppen større og den usorterte delen blir mindre. Hvis noen steder underveis ingen innføringer utføres, er array kjent for å bli sortert. Ellers fortsetter prosessen til hele arrayet er kjent for å bli sortert.
Etter to passerer sorteres sorteringen:
Sortert array offentlig tomrom Sorter (T [] elementer) int sortedRangeEnd = 0; mens (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 = elementer [i]; currentSmallestIndex = i; returner currentSmallestIndex;
| Oppførsel | Sorter innmatingsarray ved hjelp av sammenslåingsalgoritmen. | ||
| kompleksitet | Beste sak | Gjennomsnittlig sak | Verste tilfelle |
| Tid | O (n log n) | O (n log n) | O (n log n) |
| Rom | På) | På) | På) |
Så langt har vi sett algoritmer som opererer ved lineær behandling av arrayet. Disse algoritmene har oppadgående drift med svært lite minneoverhead, men på bekostning av kvadratisk runtime kompleksitet. Med fusjonssvart skal vi se vår første divisjon og erobre algoritmen.
Dele og erobre algoritmer operere ved å bryte ned store problemer i mindre, lettere oppløselige problemer. Vi ser disse typer algoritmer i hverdagen. For eksempel bruker vi en deling og erobrer algoritme når du søker i en telefonbok.
Hvis du ønsket å finne navnet Erin Johnson i en telefonbok, ville du ikke starte ved A og bla fremover side for side. Snarere vil du sannsynligvis åpne telefonboken til midten. Hvis du åpnet for M, ville du vende tilbake noen få sider, kanskje litt for langt - det er kanskje H. Da vil du vende fremover. Og du ville fortsette å vende frem og tilbake i stadig mindre trinn til du til slutt fant den siden du ville ha (eller var så nær som vende frem fornuftig).
Hvor effektiv deles og erobrer algoritmer?
Si at telefonboken er 1000 sider lang. Når du åpner til midten, har du kuttet problemet i to 500-siders problemer. Forutsatt at du ikke er på høyre side, kan du nå velge riktig side for å søke og kutte problemet i halv om igjen. Nå er problemplassen din 250 sider. Siden problemet er kuttet i ytterligere halvdel, kan vi se at en 1000-siders telefonbok kan søkes på bare ti sidevisninger. Dette er 1% av det totale antall sidevisninger som kan være nødvendige når du utfører et lineært søk.
Merge sort fungerer ved å kutte gruppen i halv om og om igjen til hvert brikke er bare ett element langt. Da blir disse elementene satt sammen igjen (fusjonert) i sorteringsordre.
La oss starte med følgende rekkefølge:
Usortert utvalg av heltall Og nå kutter vi matrisen i halvparten:
Usortert array kuttet i halvparten Nå kuttes begge disse arraysene i halvt ganger til hvert element er i seg selv:
Usortert array skåret i halvt til hver indeks er på egen hånd Med arrayet som nå er delt inn i de minste mulige deler, skjer prosessen med å slå sammen disse delene sammen igjen i sorteringsorden.
Array sortert i grupper på to De enkelte elementene blir sorterte grupper på to, de gruppene av to fusjonerer sammen i sorterte grupper på fire, og så slår de endelig sammen igjen som en endelig sortert rekkefølge.
Array sortert i grupper på fire (topp) og den fullførte sorteringen (nederst) La oss ta et øyeblikk å tenke på de enkelte operasjonene som vi trenger å implementere:
Sortere metode gjør dette.Slå sammen metode gjør dette.En ytelsesvurdering av sammenslåingssorten er at i motsetning til de lineære sorteringsalgoritmene, vil sammenslåings sortering utføre hele splitt- og fusjonslogikken, inkludert eventuelle minneallokeringer, selv om arrayet allerede er i sortert rekkefølge. Selv om den har bedre verste ytelse enn de lineære sorteringsalgoritmene, vil den beste saksytelsen alltid bli verre. Dette betyr at det ikke er en ideell kandidat når du sorterer data som er kjent for å være nesten sortert; for eksempel når du setter inn data i en allerede sortert matrise.
offentlig tomrom Sorter (T [] elementer) hvis (elementer.Lengde <= 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 ++]; annet hvis (rightIndex> = right.Length) items [targetIndex] = left [leftIndex ++]; annet hvis (venstre [leftIndex] .CompareTo (høyre [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Oppførsel | Sorterer inngangsarmen ved hjelp av hurtig sorteringsalgoritmen. | ||
| kompleksitet | Beste sak | Gjennomsnittlig sak | Verste tilfelle |
| Tid | O (n log n) | O (n log n) | På2) |
| Rom | O (1) | O (1) | O (1) |
Hurtig sortering er en annen splittelse og erobre sorteringsalgoritme. Denne fungerer ved å rekursivt utføre følgende algoritme:
La oss utføre en rask sortering på følgende array:
Usortert utvalg av heltall Trinn 1 sier at vi velger partisjonspunktet ved hjelp av en tilfeldig indeks. I prøvekoden gjøres dette på denne linjen:
int pivotIndex = _pivotRng.Next (venstre, høyre);
Plukker en tilfeldig partisjonsindeks Nå som vi kjenner partisjonsindeksen (fire), ser vi på verdien på det punktet (seks) og flytter verdiene i arrayet slik at alt mindre enn verdien er på venstre side av arrayet og alt annet (verdier større enn eller lik) flyttes til høyre side av gruppen. Husk at å flytte verdiene rundt kan endre indeksen som partisjonsverdien er lagret på (vi vil se det snart).
Bytte verdiene utføres av partisjonsmetoden i prøvekoden.
Flytte verdier til venstre og høyre for partisjonsverdien På dette punktet vet vi at seks er på riktig sted i gruppen. Vi vet dette fordi hver verdi til venstre er mindre enn partisjonsverdien, og alt til høyre er større enn eller lik partisjonsverdien. Nå gjentar vi denne prosessen på de to usorterte partisjonene i gruppen.
Gjentakelsen gjøres i prøvekoden ved å rekursivt kalle quicksort-metoden med hver av arraypartisjonene. Legg merke til at denne gangen er det venstre arrayet partisjonert på indeks ett med verdien fem. Prosessen med å flytte verdiene til de aktuelle posisjonene flytter verdien fem til en annen indeks. Jeg peker på dette for å forsterke poenget at du velger en partisjonsverdi, ikke en partisjonsindeks.
Gjenta sving og partisjon Rask sortering igjen:
Gjenta pivoten og partisjonen igjen Og rask sortering en siste gang:
Gjenta pivoten og partisjonen igjen Med bare en usortert verdi igjen, og siden vi vet at hver annen verdi er sortert, er arrayet fullt sortert.
Tilfeldig _pivotRng = ny tilfeldig (); Offentlig tomrom Sorter (T [] elementer) Quicksort (elementer, 0, elementer.Lengde - 1); Private void quicksort (T [] elementer, int venstre, int høyre) 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;
