Sortare cu bule și atât
Toată lumea știe foarte bine că din clasa de sortare de schimb cea mai rapidă metodă este așa-numita sortare rapida. Despre ea sunt scrise disertații, multe articole despre Habré îi sunt dedicate și pe baza ei sunt inventați algoritmi hibridi complecși. Dar astăzi nu vom vorbi despre sortare rapida, și despre o altă metodă de schimb - vechiul bun sortare cu buleși îmbunătățirile, modificările, mutațiile și variațiile acestuia.
Beneficiile practice ale acestor metode nu sunt atât de mari, iar mulți utilizatori habra au trecut prin toate acestea în clasa întâi. Prin urmare, articolul se adresează celor care tocmai s-au interesat de teoria algoritmilor și fac primii pași în această direcție.
imagine: bule
Astăzi vom vorbi despre cele mai simple schimb de sortare.
Dacă cineva este interesat, voi spune că există și alte clase - sortare de selecție, sortare de inserare, sortare îmbinare, sortarea distributiei, soiuri hibrideȘi sortări paralele. Apropo, există și sortări ezoterice. Acestea sunt diverse false, fundamental irealizabile, comice și alte pseudo-algoritmi, despre care voi scrie câteva articole în hub-ul „IT Humor”.
Dar acest lucru nu are nimic de-a face cu prelegerea de astăzi; acum suntem interesați doar de simple sortări de schimb. Există, de asemenea, o mulțime de sortări de schimb în sine (știu mai mult de o duzină), așa că ne vom uita la așa-numitele sortare cu bule iar unele altele strâns legate de acesta.
Vă voi avertiza în avans că aproape toate metodele de mai sus sunt foarte lente și nu va exista o analiză aprofundată a complexității lor în timp. Unele sunt mai rapide, altele mai lente, dar în general, putem spune că în medie O(n 2). De asemenea, nu văd niciun motiv pentru a aglomera articolul cu implementări în orice limbaj de programare. Cei interesați pot găsi cu ușurință exemple de cod pe Rosetta, Wikipedia sau în altă parte.
Dar să revenim la sortarea schimburilor. Ordonarea are loc ca urmare a căutării succesive repetate a matricei și a comparării perechilor de elemente între ele. Dacă elementele comparate nu sunt sortate unul față de celălalt, atunci le schimbăm. Singura întrebare este cum exact să ocoliți matricea și pe ce bază să selectați perechile pentru comparație.
Să începem nu cu sortarea cu bule standard, ci cu un algoritm numit...
Sort stupid
Sortarea este cu adevărat stupidă. Ne uităm prin matrice de la stânga la dreapta și comparăm vecinii de-a lungul drumului. Dacă întâlnim o pereche de elemente nesortate reciproc, le schimbăm și ne întoarcem la punctul unu, adică la început. Trecem și verificăm din nou matricea, dacă întâlnim din nou o pereche „incorectă” de elemente învecinate, atunci schimbăm locurile și începem de la capăt. Continuăm până când matricea este sortată încetul cu încetul.„Orice prost poate sorta așa”, vei spune și vei avea perfectă dreptate. Acesta este motivul pentru care sortarea este numită „prost”. În această prelegere vom îmbunătăți și modifica constant această metodă. Acum are dificultăți temporare O(n 3), după ce am făcut o corectare, o vom aduce deja la O(n 2), apoi o vom accelera puțin, apoi puțin mai mult și, în final, vom obține O(n Buturuga n) – și nu va fi deloc „Quick Sort”!
Să aducem o singură îmbunătățire la sortarea stupidă. După ce am descoperit două elemente nesortate adiacente în timpul trecerii și le-am schimbat, nu vom reveni la începutul matricei, ci vom continua să o traversăm cu calm până la sfârșit.
În acest caz, nu avem în față nimic mai mult decât binecunoscutul...
Sortare cu bule
Sau sortarea prin schimburi simple. Un clasic nemuritor al genului. Principiul de funcționare este simplu: parcurgem tabloul de la început până la sfârșit, schimbând simultan elementele învecinate nesortate. Ca urmare a primei treceri, elementul maxim va „pluti” până la ultimul loc. Acum traversăm din nou partea nesortată a matricei (de la primul element la penultimul) și schimbăm vecinii nesortați pe parcurs. Al doilea ca mărime va fi pe penultimul loc. Continuând în același spirit, vom străbate partea nesortată în continuă scădere a matricei, împingând maximele găsite până la capăt.Dacă nu doar împingem maximele până la capăt, ci și minimele până la început, atunci reușim...
Sortare agitator
Ea este la fel sortare amestecată, ea este la fel sortarea cocktailurilor. Procesul începe ca într-o „bulă”: stoarcem maximum până în spate. După aceasta, ne întoarcem în jurul valorii de 180 0 și mergem în direcția opusă, în timp ce revenim la început nu la maxim, ci la minim. După ce am sortat primul și ultimul element din matrice, facem din nou o capotaie. După ce mergem înainte și înapoi de mai multe ori, în cele din urmă încheiem procesul, ajungând la mijlocul listei.Sortarea cu agitator funcționează puțin mai rapid decât sortarea cu bule, deoarece atât maximele, cât și minimele migrează alternativ prin matrice în direcțiile necesare. Îmbunătățirile, după cum se spune, sunt evidente.
După cum puteți vedea, dacă abordați procesul de enumerare în mod creativ, atunci împingerea elementelor grele (ușoare) la capetele matricei se întâmplă mai rapid. Prin urmare, meșterii au propus o altă „foaie de parcurs” non-standard pentru a ocoli lista.
Sortare par-impar
De data aceasta nu ne vom grăbi înainte și înapoi prin matrice, ci vom reveni din nou la ideea unei plimbări sistematice de la stânga la dreapta, dar vom face doar un pas mai larg. La prima trecere, elementele cu o cheie impară sunt comparate cu vecinii lor în locuri pare (prima este comparată cu a 2-a, apoi a 3-a cu a 4-a, a 5-a cu a 6-a și așa mai departe). Apoi, dimpotrivă, comparăm/schimbăm elementele „pare” cu cele „impare”. Apoi din nou „impar-par”, apoi din nou „par-impar”. Procesul se oprește atunci când, după două treceri consecutive prin matrice („impar-par” și „par-impar”), nu a avut loc nici un singur schimb. Deci, au rezolvat-o.Într-o „bulă” obișnuită, în timpul fiecărei treceri, strângem sistematic maximul curent până la sfârșitul matricei. Dacă săriți de-a lungul indicilor pari și impari, atunci toate elementele mai mult sau mai puțin mari ale matricei sunt împinse simultan în poziția corectă într-o singură cursă. Funcționează mai repede în acest fel.
Să ne uităm la ultimul redecorată* Pentru Sortuvannya bulbashka** - Sortare după pieptene***. Această metodă se organizează foarte repede, O(n 2) este cea mai mare dificultate. În medie de-a lungul timpului avem O(n Buturuga n), și cel mai bun, nici nu-ți vine să crezi, O(n). Adică, un concurent foarte demn la tot felul de „sortări rapide” și asta, ține cont, fără recursiunea. Cu toate acestea, am promis că astăzi nu ne vom aprofunda în vitezele de croazieră, așa că mă voi opri din vorbit și voi merge direct la algoritm.
Toată vina e a țestoaselor
Un mic fundal. În 1980, Włodzimierz Dobosiewicz a explicat de ce sortarea cu bule și derivații săi funcționează atât de lent. Totul din cauza țestoaselor. „Testoasele” sunt elemente mici care se află la sfârșitul listei. După cum probabil ați observat, sortările cu bule se concentrează pe „iepuri” (a nu se confunda cu „iepurii” lui Babushkin) – elemente cu valoare mare la începutul listei. Se îndreaptă foarte repede spre linia de sosire. Dar reptilele lente se târăsc până la început fără tragere de inimă. Puteți personaliza tortilla folosind piepteni.imagine: broasca testoasa vinovata
Sortare pieptene
În „bubble”, „shaker” și „impar-par”, când se repetă printr-o matrice, elementele învecinate sunt comparate. Ideea principală a „pieptenului” este de a lua inițial o distanță suficient de mare între elementele comparate și, pe măsură ce matricea este ordonată, să restrângem această distanță la minim. În acest fel, pieptănăm matricea, netezind-o treptat în fire din ce în ce mai îngrijite.Este mai bine să luați decalajul inițial dintre elementele comparate nu oricare, ci ținând cont de o valoare specială numită factor reducător, a cărui valoare optimă este de aproximativ 1,247. În primul rând, distanța dintre elemente este egală cu dimensiunea matricei împărțită la factor de reducere(rezultatul, desigur, este rotunjit la cel mai apropiat număr întreg). Apoi, după ce parcurgem matricea cu acest pas, împărțim din nou pasul factor de reducereși parcurgeți din nou lista. Aceasta continuă până când diferența de indice ajunge la unu. În acest caz, matricea este sortată cu un balon obișnuit.
Valoarea optimă a fost stabilită experimental și teoretic factor de reducere:
Când a fost inventată această metodă, puțini oameni i-au acordat atenție la începutul anilor 70-80. Un deceniu mai târziu, când programarea nu mai era de competența oamenilor de știință și inginerilor IBM, ci câștiga deja rapid popularitate în masă, metoda a fost redescoperită, cercetată și popularizată în 1991 de Stephen Lacy și Richard Box.
De fapt, asta este tot ce am vrut să vă spun despre sortarea cu bule și altele asemenea.
- Note
* scurtat ( ucrainean) - îmbunătățire
** Sortate după bec ( ucrainean) – Sortare cu bule
*** Sortare după pieptene ( ucrainean) – Sortare pieptene
Astăzi vom atinge subiectul sortării în Pascal. Există destul de multe metode diferite, cele mai multe dintre ele nu sunt cunoscute pe scară largă, iar cunoașterea lor, în principiu, nu este necesară. Este suficient să cunoașteți setul de bază și câteva suplimentare. În acest articol vă voi spune despre cel mai faimos sort - sortare cu bule, care se mai numește și sortare cu schimb simplu.
În primul rând, ce este sortarea în Pascal și de ce este necesară? Sortarea este o metodă de ordonare a unui tablou (de obicei în ordine crescătoare sau descrescătoare). În probleme există linii precum „aranjați elementele matricei, începând de la minim (maximum)”. Rețineți că acesta este același lucru.
Să revenim la sortarea cu bule. De ce a fost numită așa? Ideea este că aceasta este o analogie. Imaginați-vă o matrice obișnuită aranjată vertical. Ca rezultat al sortării, elementele mai mici se deplasează în sus. Adică, aici matricea poate fi reprezentată sub formă de apă, iar elementele mai mici sub formă de bule care plutesc spre vârf.
Acum să vorbim mai multe despre algoritmul în sine. Este destul de simplu:
1. Pentru sortare se folosesc 2 cicluri, unul imbricat în celălalt. Unul este folosit pentru pași, celălalt pentru sub-pași.
2. Esența algoritmului este o comparație a două elemente. Exact doi. Permiteți-mi să explic, de exemplu, avem o matrice cu 10 elemente. Elementele vor fi comparate în perechi: 1 și 2, 2 și 3, 3 și 4, 4 și 5, 6 și 7 etc. La compararea perechilor, dacă elementul anterior este mai mare decât următorul, atunci acestea sunt schimbate. De exemplu, dacă al doilea element este 5 și al treilea este 2, atunci le vor schimba.
3. Sortarea cu bule este împărțită în pași. În fiecare pas, se efectuează o comparație în perechi. Ca rezultat al fiecărui pas, cele mai mari elemente încep să se alinieze de la sfârșitul matricei. Adică, după primul pas, cel mai mare element al matricei va fi pe ultimul loc. În a doua etapă, se lucrează cu toate elementele, cu excepția ultimului. Din nou, cel mai mare element este găsit și plasat la sfârșitul matricei cu care se lucrează. Al treilea pas îl repetă pe al doilea și așa mai departe până când matricea este sortată. Pentru o înțelegere mai convenabilă, voi da un exemplu clar. Să luăm o matrice formată din 7 elemente: 2,5,11,1,7,8,3. Să aruncăm o privire. (Faceți clic pe imagine pentru a mări imaginea)
Să trecem direct la cod. După cum am menționat deja, avem nevoie de două cicluri. Asa va arata
const
m = 7; (numărul de elemente din matrice)
var
msort: matrice de întregi; (de fapt, matricea noastră)
i, j, k: întreg; (i este un pas, j este un sub-pas)
ÎNCEPE
writeln("Introduceți elementele matricei");
pentru i:= 1 la m do
citește(msort[i]);
Pentru i:= 1 la m - 1 do
pentru j:= 1 la m - i do
dacă msort[j] > msort atunci începe
k:= msort[j];
msort[j] := msort;
msort := k;
Sfârşit;
Write("Matrice sortată: ");
pentru i:= 1 la m do
scrie(msort[i]:4);
Sfârşit.
Observați elementul k. Este necesar doar pentru un singur scop: pentru a schimba două elemente ale unei matrice. Cert este că în Pascal nu există nicio funcție specială care să realizeze o astfel de acțiune. Prin urmare, trebuie să-l pictezi singur, adăugând un element suplimentar pentru schimb. Acest articol este terminat cu metoda de sortare cu bule, următoarele articole vor fi publicate în săptămâna viitoare (sau poate mai devreme).
S-a estimat că până la un sfert din timpul computerelor centralizate este cheltuit pentru sortarea datelor. Acest lucru se datorează faptului că este mult mai ușor să găsiți o valoare într-o matrice care a fost pre-sortată. Altfel, căutarea este un pic ca a căuta un ac într-un car de fân.
Există programatori care își petrec tot timpul de lucru studiind și implementând algoritmi de sortare. Acest lucru se datorează faptului că marea majoritate a software-ului de afaceri implică gestionarea bazelor de date. Oamenii caută informații în bazele de date tot timpul. Aceasta înseamnă că algoritmii de căutare sunt la mare căutare.
Dar există un „dar”. Algoritmii de căutare funcționează mult mai rapid cu bazele de date care sunt deja sortate. În acest caz, este necesară doar o căutare liniară.
În timp ce computerele sunt fără utilizatori în anumite momente, algoritmii de sortare continuă să funcționeze pe bazele de date. Căutătorii vin din nou, iar baza de date este deja sortată în funcție de unul sau altul scop de căutare.
Acest articol oferă exemple de implementări ale algoritmilor standard de sortare.
Sortare selecție
Pentru a sorta o matrice în ordine crescătoare, trebuie să găsiți elementul cu cea mai mare valoare la fiecare iterație. Cu el trebuie să schimbați ultimul element. Următorul element cu cea mai mare valoare este plasat pe penultimul loc. Acest lucru ar trebui să se întâmple până când elementele din primele locuri din matrice sunt în ordinea corectă.
cod C++
void SortAlgo::selectionSort(int date, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i
Sortare cu bule
Sortare cu bule compară elementele adiacente și schimbă locuri dacă următorul element este mai mic decât cel anterior. Sunt necesare mai multe treceri prin date. În timpul primei treceri, primele două elemente din matrice sunt comparate. Dacă nu sunt în ordine, sunt schimbate și apoi sunt comparate elementele din perechea următoare. În aceeași condiție, își schimbă și ei locul. Astfel, sortarea are loc în fiecare ciclu până când se ajunge la sfârșitul matricei.
cod C++
void SortAlgo::bubbleSort(int date, int lenD) ( int tmp = 0; for (int i = 0;i) Sortarea prin inserare împarte matricea în două regiuni: ordonată și neordonată. Inițial, întreaga matrice este o regiune neordonată. La prima trecere, primul element din regiunea neordonată este îndepărtat și plasat în poziția corectă în regiunea ordonată. La fiecare trecere, dimensiunea regiunii ordonate crește cu 1, iar dimensiunea regiunii dezordonate scade cu 1. Bucla principală merge de la 1 la N-1. La a j-a iterație, elementul [i] este introdus în poziția corectă în regiunea ordonată. Acest lucru se face prin deplasarea tuturor elementelor din regiunea ordonată care sunt mai mari decât [i] cu o poziție la dreapta. [i] este introdus în spațiul dintre acele elemente care sunt mai mici decât [i] și cele care sunt mai mari decât [i]. cod C++
void SortAlgo::insertionSort(int date, int lenD) ( int key = 0; int i = 0; for (int j = 1;j) cod C++
void SortAlgo::mergeSort(int date, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int i=0;i Quicksort folosește un algoritm de împărțire și cucerire. Începe prin împărțirea matricei originale în două regiuni. Aceste părți sunt în stânga și în dreapta elementului marcat, numit suport. La sfârșitul procesului, o parte va conține elemente mai mici decât referința, iar cealaltă parte va conține elemente mai mari decât referința. cod C++
void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = int nou ; int * R = int nou ; pivot = date ; pentru (i = 0; i Sortare prin inserare
Sortare îmbinare
Sortare rapida
