Share
În această secțiune, vom analiza cinci algoritmi folosiți pentru a sorta datele într-o matrice. Vom începe cu un algoritm naiv, cu sortarea bulelor și se va termina cu cel mai comun algoritm de sortare generală, sortare rapidă.
Cu fiecare algoritm voi explica felul în care se face sortarea și oferă, de asemenea, informații despre complexitatea cea mai bună, medie și cea mai proastă, atât pentru performanță, cât și pentru utilizarea memoriei.
Pentru a păstra codul de algoritm de sortare un pic mai ușor de citit, o comună schimb metoda va fi folosită de orice algoritm de sortare care trebuie să facă schimb de valori într-o matrice după index.
void Swap (T [] elemente, int stânga, int dreapta) if (stânga! = dreapta) T temp = elemente [stânga]; elemente [stânga] = elemente [dreapta]; elemente [dreapta] = temp;
| Comportament | Sortează matricea de intrare folosind algoritmul de sortare a bulelor. | ||
| Complexitate | Cel mai bun caz | Cazul mediu | Cel mai rău caz |
| Timp | Pe) | Pe2) | Pe2) |
| Spaţiu | O (1) | O (1) | O (1) |
Tipul de tip bubble este un algoritm de sortare naiv care funcționează prin efectuarea mai multor treceri prin matrice, de fiecare dată când se deplasează cea mai mare valoare nesortată la dreapta (sfârșitul) matricei.
Luați în considerare următoarea matrice nesaturată de numere întregi:
Gama nesimetată de numere întregi La prima trecere prin matrice, valorile trei și șapte sunt comparate. Din moment ce șapte sunt mai mari decât trei, nu se efectuează nicio schimbare. Apoi, șapte și patru sunt comparate. Șapte sunt mai mari decât patru, astfel încât valorile sunt schimbate, deplasându-se astfel șapte, cu un pas mai aproape de sfârșitul matricei. Acum, matricea arată astfel:
Cele 4 și 7 au schimbat pozițiile Acest proces este repetat, iar cele șapte în cele din urmă se termină cu compararea cu cele opt, ceea ce este mai mare, astfel încât nu se poate efectua o schimbare, iar pasul se termină la sfârșitul matricei. La sfârșitul primului pas, matricea arată astfel:
Matricea de la sfârșitul trecerii 1 Deoarece a fost efectuată cel puțin o operațiune de swap, va fi efectuată o altă trecere. După a doua trecere, cei șase s-au mutat în poziție.
Matricea de la sfârșitul trecerii 2 Din nou, pentru că a fost efectuată cel puțin o operațiune de swap, este efectuată o altă trecere.
Următoarea trecere, totuși, constată că nu au fost necesare schimburi de swap, deoarece toate elementele sunt în ordinea sortimentului. Deoarece nu s-au efectuat schimburi de swapuri, matricea este cunoscută a fi sortată și algoritmul de sortare este complet.
public void Sortare (T [] elemente) bool swapped; swapped = false; pentru (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Swap (elemente, i - 1, i); schimbat = adevărat; în timp ce (schimbat! = fals);
| Comportament | Sortează matricea de intrare utilizând algoritmul de sortare a inserției. | ||
| Complexitate | Cel mai bun caz | Cazul mediu | Cel mai rău caz |
| Timp | Pe) | Pe2) | Pe2) |
| Spaţiu | O (1) | O (1) | O (1) |
Inserția de sortare funcționează făcând o singură trecere prin matrice și inserând valoarea curentă în porțiunea deja ordonată (început) a matricei. După ce fiecare index este procesat, se știe că tot ceea ce sa întâmplat până acum este sortat și tot ceea ce urmează nu este cunoscut.
Stai ce?
Conceptul important este că sortarea inserției funcționează prin sortarea elementelor așa cum sunt întâlnite. Deoarece procesează matricele de la stânga la dreapta, știm că totul la stânga indicelui curent este sortat. Această diagramă demonstrează modul în care matricea este sortată pe măsură ce se întâlnește fiecare index:
O matrice fiind procesată prin sortarea introducerii Pe măsură ce procesarea continuă, matricea devine din ce în ce mai mult sortată până când este complet sortită.
Să examinăm un exemplu concret. Următoarea este o matrice nesortată care va fi sortată prin sortarea inserției.
Gama nesimetată de numere întregi Când începe procesul de sortare, algoritmul de sortare începe la index zero cu valoarea trei. Deoarece nu există valori care preced acest lucru, se știe că seria până la și inclusiv indexul zero este sortată.
Algoritmul se deplasează apoi la valoarea șapte. Din moment ce șapte este mai mare decât tot în intervalul de sortare cunoscut (care în prezent include doar trei), valorile până la șapte inclusiv sunt cunoscute ca fiind în ordine de sortare.
În acest moment, indiciile matricei 0-1 sunt cunoscute a fi sortate, iar 2-n sunt într-o stare necunoscută.
Valoarea la indexul doi (patru) este bifată în continuare. Din moment ce patru sunt mai puțin de șapte, se știe că patru trebuie să fie mutate în locul potrivit în zona sortată a matricei. Întrebarea este acum la ce index din matricea sortată ar trebui introdusă valoarea. Metoda de a face acest lucru este FindInsertionIndex afișate în eșantionul de cod. Această metodă compară valoarea introdusă (patru) cu valorile din intervalul sortat, începând cu indicele zero, până când găsește punctul în care ar trebui inserată valoarea.
Această metodă determină faptul că indexul unu (între trei și șapte) reprezintă punctul de inserție corespunzător. Algoritmul de inserție ( Introduce ) efectuează apoi inserarea prin eliminarea valorii care urmează să fie inserată din matrice și deplasarea tuturor valorilor de la punctul de inserție la elementul eliminat spre dreapta. Acum, matricea arată astfel:
Array după primul algoritm de inserare Matricea de la indexul zero la doi este acum cunoscută a fi sortată și totul de la indexul trei până la final nu este cunoscut. Procesul începe acum din nou la indexul trei, care are valoarea de patru. Pe măsură ce algoritmul continuă, se introduc următoarele inserări până când seria este sortată.
Array după algoritmi de inserție ulteriori Atunci când nu există alte inserări care trebuie efectuate sau când porțiunea triunghiată a matricei este întreaga matrice, algoritmul este terminat.
Accentsconagua
public void Sortare (T [] elemente) int sortedRangeEndIndex = 1; în timp ce (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) return index; arunca noua InvalidOperationException ("Indicele de inserție nu a fost găsit"); void privat Introduceți (T [] itemArray, int indexInsertingAt, int indexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // acțiuni // 1: Indexul magazinului la Temp temp = 4 // 2: Setați indexul la index la -> 0 1 2 3 5 6 3 7 temp = 4 // 3: Deplasare înapoi de la index la index la + 1. // Valori schimbare de la stânga la dreapta o singura data. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: Introduceți valoarea temp la index la + 1. // 0 1 2 3 4 5 6 7 temp = 4 // Pasul 1. T temp = itemArray [indexInsertingAt]; // Pasul 2. itemArray [indexInsertingAt] = itemArray [indexInsertingFrom]; // Pasul 3. pentru (int curent = indexInsertingFrom; current> indexInsertingAt; curent--) itemArray [curent] = itemArray [curent - 1]; // Pasul 4. itemArray [indexInsertingAt + 1] = temp; | Comportament | Sortează matricea de intrare utilizând algoritmul de sortare a selecției. | ||
| Complexitate | Cel mai bun caz | Cazul mediu | Cel mai rău caz |
| Timp | Pe) | Pe2) | Pe2) |
| Spaţiu | O (1) | O (1) | O (1) |
Selecția sortimentului este un tip de hibrid între sortarea bulei și sortarea inserției. Ca un fel de balon, procesează matricele prin iterarea de la început până la final, din nou și din nou, cu alegerea unei valori și deplasarea acesteia în poziția corectă. Cu toate acestea, spre deosebire de sortarea bulelor, aceasta preia cea mai mică valoare nesortată decât cea mai mare. Ca și tipul de inserție, porțiunea triunghiată a matricei este începutul matricei, în timp ce cu sortarea bulelor, porțiunea sortată este la sfârșit.
Să vedem cum funcționează acest lucru folosind aceeași matrice nesortată pe care am folosit-o.
Gama nesimetată de numere întregi Pe prima trecere, algoritmul va încerca să găsească cea mai mică valoare din matrice și să o plaseze în primul index. Acest lucru este efectuat de către FindIndexOfSmallestFromIndex, care găsește indicele celei mai mici valori nesortate începând de la indicele furnizat.
Cu o astfel de matrice mică, putem spune că prima valoare, trei, este cea mai mică valoare, deci este deja în locul corect. În acest moment, știm că valoarea din indicele matrice zero este cea mai mică valoare și, prin urmare, este în ordinea corectă de sortare. Deci, acum putem începe să trecem două - de data aceasta doar uitându-ne la intrările de matrice unul la n-1.
A doua trecere va determina că patru este cea mai mică valoare din intervalul nesortat și va schimba valoarea în cel de-al doilea slot cu valoarea în slotul pe care au avut loc patru (schimbând cele patru și șapte). După trecerea a două finalizări, valoarea patru va fi introdusă în poziția sa ordonată.
Arra după a doua trecere Intervalul sortat este acum de la indexul zero la indexul unu, iar intervalul nesortat este de la indexul doi la n-1. Pe măsură ce fiecare trecere ulterioară se termină, porțiunea sortită a matricei crește și porțiunea nesortată devine mai mică. Dacă în orice moment de-a lungul drumului nu se efectuează inserții, se știe că matricea este sortată. În caz contrar, procesul continuă până când se știe că întreaga matrice este sortată.
După încă două treceri, matricea este sortată:
Sortați matrice public void Sortare (T [] elemente) int sortedRangeEnd = 0; în timp ce (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 = elemente [i]; currentSmallestIndex = i; returnează curentSmallestIndex;
| Comportament | Sortează matricea de intrare utilizând algoritmul de sortare a îmbinării. | ||
| Complexitate | Cel mai bun caz | Cazul mediu | Cel mai rău caz |
| Timp | O (n log n) | O (n log n) | O (n log n) |
| Spaţiu | Pe) | Pe) | Pe) |
Până acum am văzut algoritmi care funcționează prin procesarea liniară a matricei. Acești algoritmi au avantajul de a opera cu foarte puțină memorie deasupra capului, dar cu costul de complexitate a runtime-ului. Cu un fel de îmbinare, vom vedea primul nostru algoritm de divizare și cucerire.
Împărțirea și cucerirea algoritmilor funcționează prin ruperea problemelor mari în probleme mai mici, mai ușor de rezolvat. Vedem aceste tipuri de algoritmi în viața de zi cu zi. De exemplu, folosim algoritmul de divizare și cucerire atunci când căutăm o agendă telefonică.
Dacă ați fi dorit să găsiți numele Erin Johnson într-o carte de telefon, nu ați porni de la A și faceți o pagină flip-pe pagină. Mai degrabă, probabil că veți deschide agenda telefonică la mijloc. Dacă te-ai deschis la M, ai întoarce câteva pagini, poate puțin prea departe - probabil H. Atunci te-ai întoarce. Și veți continua să vă răsturnați înainte și înapoi cu creșteri tot mai mici până când veți găsi în cele din urmă pagina pe care ați dorit-o (sau ați fi fost atât de aproape încât flipping-ul a făcut sens).
Cât de eficiente sunt algoritmii de divizare și cucerire?
Spuneți că agenda telefonică are o lungime de 1000 de pagini. Când deschideți la mijloc, ați tăiat problema în două probleme de 500 de pagini. Presupunând că nu sunteți pe pagina potrivită, acum puteți alege partea potrivită pentru a căuta și a reduce problema din nou pe jumătate. Acum, spațiul dvs. de problemă este de 250 de pagini. Deoarece problema este redusă la o jumătate mai mult și mai mult, putem vedea că o carte de telefon de 1000 de pagini poate fi căutată doar în zece pagini. Acesta este 1% din numărul total de pagini care ar putea fi necesare atunci când efectuați o căutare liniară.
Merge sortarea funcționează prin tăierea matricei în repetate părți, până când fiecare piesă este lungă. Apoi, aceste elemente sunt reunite împreună (îmbinate) în ordine de sortare.
Să începem cu următoarea matrice:
Gama nesimetată de numere întregi Și acum am tăiat matricea în jumătate:
Șirul neimpozitat tăiat în jumătate Acum, ambele tablouri sunt tăiate în repetate rânduri, până când fiecare element este singur:
Gama nesimetrică tăiată în jumătate până când fiecare index este pe cont propriu Cu matricea acum împărțită în cele mai mici părți posibile, procesul de fuziune a acestor părți înapoi în ordine de sortare are loc.
Array sortat în grupuri de câte două Elementele individuale devin grupe de grupuri de câte două, aceste grupuri de câte două se îmbină împreună în grupuri sortate de patru și apoi în cele din urmă toate se reunesc împreună ca o matrice finală sortată.
Array sortat în grupuri de patru (top) și sortare completat (partea de jos) Să facem un moment să ne gândim la operațiile individuale pe care trebuie să le implementăm:
Fel metoda face acest lucru.contopi metoda face acest lucru.O analiză de performanță a sortimentului de îmbinare este că, spre deosebire de algoritmii de sortare liniară, sortarea îmbinării va efectua întreaga logică de divizare și îmbinare, inclusiv orice alocare a memoriei, chiar dacă matricea este deja în ordine ordonată. În timp ce are o performanță mai slabă decât algoritmii de sortare liniară, performanța sa de cel mai bun caz va fi întotdeauna mai gravă. Aceasta înseamnă că nu este un candidat ideal atunci când sortați date care sunt cunoscute a fi aproape sortate; de exemplu, atunci când inserați date într-o matrice deja sortată.
public void Sortare (T [] elemente) 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) elemente [targetIndex] = dreapta [rightIndex ++]; altfel dacă (rightIndex> = dreapta.Lungime) items [targetIndex] = left [leftIndex ++]; altceva dacă (stânga [leftIndex] .CompareTo (dreapta [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Comportament | Sortează matricea de intrare utilizând algoritmul de sortare rapidă. | ||
| Complexitate | Cel mai bun caz | Cazul mediu | Cel mai rău caz |
| Timp | O (n log n) | O (n log n) | Pe2) |
| Spaţiu | O (1) | O (1) | O (1) |
Tipul rapid este un alt algoritm de divizare și cucerire. Aceasta funcționează prin efectuarea recursivă a următorului algoritm:
Să efectuăm o sortare rapidă pe următoarea matrice:
Gama nesimetată de numere întregi Pasul unu spune că alegem punctul de partiție folosind un index aleatoriu. În exemplul de cod, acest lucru se face la această linie:
int pivotIndex = _pivotRng.Next (stânga, dreapta);
Alegerea unui indice de partiție aleatoriu Acum, când cunoaștem indicele de partiție (patru), ne uităm la valoarea din acel punct (șase) și mutăm valorile din matrice astfel încât totul mai mic decât valoarea se află pe partea stângă a matricei și orice altceva (valori mai mari decât sau egal) este mutat în partea dreaptă a matricei. Rețineți că mișcarea valorilor în jurul valorii poate modifica indexul în care este stocată valoarea partiției (vom vedea că în curând).
Schimbarea valorilor se face prin metoda partiției din exemplul de cod.
Se deplasează valori la stânga și la dreapta valorii partiției În acest moment știm că șase sunt în locul corect din matrice. Știm acest lucru deoarece fiecare valoare din stânga este mai mică decât valoarea partiției, iar totul la dreapta este mai mare sau egal cu valoarea partiției. Acum repetăm acest proces pe cele două partiții nesortate ale matricei.
Repetarea se face în codul eșantion prin apelarea recursivă a metodei quicksort cu fiecare dintre partițiile matrice. Observați că de această dată matricea stângă este partiționată la indexul 1 cu valoarea cinci. Procesul de deplasare a valorilor la pozițiile lor adecvate mută valoarea 5 la un alt index. Subliniez acest lucru pentru a consolida punctul în care selectați o valoare de partiție, nu un index de partiție.
Repetați pivotul și partiția Sortarea rapidă din nou:
Repetați pivotul și partiția din nou Și sortarea rapidă pentru ultima oară:
Repetați pivotul și partiția din nou Cu o singură valoare nesortată rămasă, și din moment ce știm că fiecare altă valoare este sortată, matricea este complet sortită.
Random _pivotRng = nou Random (); public void Sortare (T [] elemente) quicksort (articole, 0, items.Length - 1); privat void quicksort (T [] elemente, int stânga, int dreapta) if (stânga < 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;
