Există un număr destul de mare de algoritmi de sortare, mulți dintre ei sunt foarte specifici și au fost dezvoltați pentru a rezolva o gamă restrânsă de probleme și pentru a lucra cu tipuri specifice de date. Dar, printre toată această diversitate, cel mai simplu algoritm este sortarea cu bule, care poate fi implementat în orice limbaj de programare. În ciuda simplității sale, stă la baza multor algoritmi destul de complexi. Un alt avantaj la fel de important este simplitatea sa și, prin urmare, poate fi reținut și implementat imediat, fără a avea în față vreo literatură suplimentară.
Introducere
Întregul Internet modern constă dintr-un număr mare de tipuri diferite de structuri de date colectate în baze de date. Acestea stochează tot felul de informații, de la datele personale ale utilizatorilor până la nucleul semantic al sistemelor automate extrem de inteligente. Inutil să spun că sortarea datelor joacă un rol extrem de important în această cantitate imensă de informații structurate. Sortarea poate fi un pas obligatoriu înainte de a căuta orice informație în baza de date, iar cunoașterea algoritmilor de sortare joacă un rol foarte important în programare. Există un număr destul de mare de algoritmi de sortare, mulți dintre ei sunt foarte specifici și au fost dezvoltați pentru a rezolva o gamă restrânsă de probleme și pentru a lucra cu tipuri specifice de date. Dar printre toată această varietate, cel mai simplu algoritm este pe merit sortare cu bule, care poate fi implementat în orice limbaj de programare. În ciuda simplității sale, stă la baza multor algoritmi destul de complexi. Un alt avantaj la fel de important este simplitatea sa și, prin urmare, poate fi reținut și implementat imediat, fără a avea în față vreo literatură suplimentară.Sortare prin ochi de mașină și ochi umani
Să ne imaginăm că trebuie să sortați 5 coloane de înălțimi diferite în ordine crescătoare. Aceste coloane pot însemna orice fel de informații (prețurile bursiere, lățimea de bandă a canalului de comunicare etc.); puteți prezenta unele dintre propriile versiuni ale acestei sarcini pentru a o face mai clară. Ei bine, ca exemplu, vom sorta Răzbunătorii după înălțime:Spre deosebire de un program de calculator, sortarea nu va fi dificilă pentru dvs., deoarece puteți vedea întreaga imagine și vă puteți da seama imediat ce erou trebuie mutat acolo unde sortarea după înălțime să fie finalizată cu succes. Probabil ați ghicit deja că pentru a sorta această structură de date în ordine crescătoare, trebuie doar să schimbați locurile lui Hulk și Iron Man:
Terminat!
Și aceasta va finaliza sortarea cu succes. Totuși, computerul, spre deosebire de tine, este oarecum prost și nu vede întreaga structură de date ca un întreg. Programul său de control poate compara doar două valori în același timp. Pentru a rezolva această problemă, ea trebuie să pună în memorie două numere și să efectueze o operație de comparare asupra lor, apoi să treacă la o altă pereche de numere și așa mai departe până când toate datele au fost analizate. Prin urmare, orice algoritm de sortare poate fi foarte simplificat sub forma a trei pași:- Comparați două elemente;
- Schimbați sau copiați unul dintre ele;
- Treceți la elementul următor;
Algoritmul de sortare cu bule
Sortarea cu bule este considerată cea mai simplă, dar înainte de a descrie acest algoritm, să ne imaginăm cum ai sorta Răzbunătorii după înălțime dacă ai putea, ca o mașină, să compari doar doi eroi între ei într-o perioadă de timp. Cel mai probabil, ați face următoarele (cel mai optim):- Treci la elementul zero al matricei noastre (Văduva Neagră);
- Comparați elementul zero (Văduva Neagră) cu primul (Hulk);
- Dacă elementul din poziția zero este mai mare, le schimbați;
- În caz contrar, dacă elementul din poziţia zero este mai mic, le lăsaţi la locul lor;
- Mutați-vă într-o poziție din dreapta și repetați comparația (comparați Hulk cu Căpitanul)
După ce parcurgeți întreaga listă într-o singură trecere cu un astfel de algoritm, sortarea nu va fi finalizată complet. Dar, pe de altă parte, cel mai mare element din listă va fi mutat în poziția extremă din dreapta. Acest lucru se va întâmpla întotdeauna, deoarece de îndată ce vei găsi cel mai mare element, vei schimba constant locurile până când îl vei muta până la capăt. Adică, de îndată ce programul „găsește” Hulk în matrice, îl va muta mai departe până la sfârșitul listei:
Acesta este motivul pentru care acest algoritm se numește sortare cu bule, deoarece, ca urmare a funcționării sale, cel mai mare element din listă va fi chiar în partea de sus a matricei, iar toate elementele mai mici vor fi deplasate cu o poziție spre stânga:
Pentru a finaliza sortarea, va trebui să reveniți la începutul matricei și să repetați din nou cei cinci pași descriși mai sus, deplasându-vă din nou de la stânga la dreapta, comparând și mutând elementele după cum este necesar. Dar de data aceasta trebuie să opriți algoritmul cu un element înainte de sfârșitul matricei, deoarece știm deja că cel mai mare element (Hulk) este absolut în poziția cea mai dreaptă:
Deci programul trebuie să aibă două bucle. Pentru o mai mare claritate, înainte de a trece la revizuirea codului programului, puteți vedea o vizualizare a modului în care funcționează sortarea cu bule la acest link: Vizualizarea modului în care funcționează sortarea cu bule.
Implementarea sortării cu bule în Java
Pentru a demonstra cum funcționează sortarea în Java, iată codul programului:- creează o matrice de 5 elemente;
- încarcă în ea ascensiunea răzbunătorilor;
- afișează conținutul matricei;
- implementează sortarea cu bule;
- re-afișează matricea sortată.
- into – metodă de inserare a elementelor într-o matrice;
- imprimantă – imprimă conținutul matricei linie cu linie;
bubbleSorter – care face activitatea principală și sortează datele stocate în matrice; încă o dată le prezentăm separat:
public void bubbleSorter() ( //METODA DE SORTARE BUBLE for (int out = elems - 1 ; out >= 1 ; out-- ) ( //Bucla exterioară for (int in = 0 ; in< out; in++ ) { //Bucla interioară dacă (a[in] > a[in + 1] ) //Dacă ordinea elementelor este ruptă toSwap (în, în + 1); //apelează o metodă care schimbă locuri } } }
toSwap – schimbă elemente dacă este necesar. Pentru a face acest lucru, se folosește o variabilă temporară dummy, în care este scrisă valoarea primului număr, iar valoarea de la al doilea număr este scrisă în locul primului. Conținutul din variabila temporară este apoi scris în al doilea număr. Aceasta este o tehnică standard pentru schimbarea a două elemente;
și în sfârșit metoda principală:
Concluzie
Algoritmul de sortare cu bule este unul dintre cele mai lente. Dacă tabloul este format din N elemente, atunci se vor efectua N-1 comparații la prima trecere, N-2 la a doua, apoi N-3 etc. Adică se va face numărul total de treceri: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Astfel, la sortare, algoritmul realizează aproximativ 0,5x(N^2) comparații. Pentru N = 5, numărul de comparații va fi de aproximativ 10, pentru N = 10 numărul de comparații va crește la 45. Astfel, pe măsură ce numărul de elemente crește, complexitatea sortării crește semnificativ:Viteza algoritmului este afectată nu numai de numărul de treceri, ci și de numărul de permutări care trebuie făcute. Pentru date aleatorii, numărul de permutări este în medie (N^2) / 4, care este aproximativ jumătate din numărul de treceri. Cu toate acestea, în cel mai rău caz, numărul de permutări poate fi și N^2 / 2 - acesta este cazul dacă datele sunt inițial sortate în ordine inversă. În ciuda faptului că acesta este un algoritm de sortare destul de lent, este destul de important să cunoaștem și să înțelegem cum funcționează și, așa cum am menționat mai devreme, este baza pentru algoritmi mai complexi. Jgd!
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
Când lucrați cu matrice de date, sarcina apare adesea sortarea în ordine crescătoare sau descrescătoare, adică comanda. Aceasta înseamnă că elementele aceleiași matrice trebuie aranjate strict în ordine. De exemplu, în cazul sortării crescătoare, elementul precedent trebuie să fie mai mic decât (sau egal) cu cel următor.
Soluţie
Există multe metode de sortare. Unele dintre ele sunt mai eficiente, altele sunt mai ușor de înțeles. Sortarea este destul de ușor de înțeles metoda bulelor, care se mai numește metoda simplă de schimb. Ce este și de ce are un nume atât de ciudat: „metoda cu bule”?
După cum știți, aerul este mai ușor decât apa, așa că bulele de aer plutesc. Este doar o analogie. În sortarea ascendentă cu bule, elementele mai ușoare (valoare mai mică) „plutesc” treptat până la începutul matricei, iar cele mai grele, unul după altul, cad în partea de jos (până la sfârșitul matricei).
Algoritmul și caracteristicile acestei sortări sunt următoarele:
- În timpul primei treceri prin matrice, elementele sunt comparate între ele în perechi: primul cu al doilea, apoi al doilea cu al treilea, apoi al treilea cu al patrulea etc. Dacă elementul anterior este mai mare decât cel următor, atunci ele sunt schimbate.
- Nu este greu de ghicit că, treptat, cel mai mare număr se dovedește a fi ultimul. Restul matricei rămâne nesortat, deși există o anumită mișcare a elementelor cu valoare mai mică la începutul matricei.
- La a doua trecere, nu este nevoie să compari ultimul element cu penultimul. Ultimul element este deja la locul lui. Aceasta înseamnă că numărul de comparații va fi cu unul mai puțin.
- La a treia trecere, nu mai este nevoie să comparăm penultimul și al treilea element de la final. Prin urmare, numărul de comparații va fi cu două mai puțin decât în timpul primei treceri.
- La urma urmei, atunci când iterați printr-o matrice, când mai sunt doar două elemente de comparat, se efectuează o singură comparație.
- După aceasta, nu mai există nimic cu care să comparați primul element și, prin urmare, o trecere finală prin matrice nu este necesară. Cu alte cuvinte, numărul de treceri prin matrice este m-1, unde m este numărul de elemente din matrice.
- Numărul de comparații din fiecare trecere este egal cu m-i, unde i este numărul de treceri prin matrice (primul, al doilea, al treilea etc.).
- La schimbul de elemente de matrice, se folosește de obicei o variabilă „buffer” (a treia), unde valoarea unuia dintre elemente este plasată temporar.
Programul Pascal:
const m = 10 ; var arr: matrice [ 1 .. m ] de întreg ; i, j, k: întreg ; începe randomizarea; scrie( "Matrice sursă: "); for i : = 1 to m do begin arr[ i] : = random(256 ) ; scrie (arr[ i] : 4 ) ; Sfârşit ; scrie ; scrie ; for i : = 1 to m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] then begin k : = arr[ j] ; arr[ j] : = arr[ j+ 1 ] ; arr[ j+ 1 ] : = k sfârşit ; scrie( "Matrice sortată: "); pentru i : = 1 la m scrieți (arr[ i] : 4 ) ; scrie ; readln sfârşitul .
Nu numai că nu este considerată cea mai rapidă metodă, în plus, închide lista celor mai lente metode de comandă. Cu toate acestea, are și avantajele sale. Deci, sortarea cu bule este cea mai logică și naturală soluție la problemă dacă trebuie să aranjați elementele într-o anumită ordine. O persoană obișnuită, de exemplu, îl va folosi manual - pur și simplu prin intuiție.
De unde a venit un nume atât de neobișnuit?
Numele metodei a fost inventat folosind o analogie cu bulele de aer din apă. Aceasta este o metaforă. Așa cum bulele de aer mici se ridică în vârf - la urma urmei, densitatea lor este mai mare decât cea a oricărui lichid (în acest caz, apă), astfel încât fiecare element al matricei, cu cât este mai mic în valoare, cu atât își face treptat mai mult. drum spre începutul listei de numere.
Descrierea algoritmului
Sortarea cu bule funcționează astfel:
- prima trecere: elementele matricei de numere sunt luate câte două și, de asemenea, comparate în perechi. Dacă într-o pereche de elemente prima valoare este mai mare decât a doua, programul le schimbă;
- prin urmare, ajunge la sfârșitul matricei. În timp ce toate celelalte elemente rămân așa cum au fost, într-o ordine haotică și necesită o sortare ulterioară;
- de aceea este necesară o a doua trecere: se efectuează prin analogie cu cea anterioară (deja descrisă) și are numărul de comparații - minus unu;
- Pasajul numărul trei are cu o comparație mai puțin decât al doilea și cu două mai puțin decât primul. Și așa mai departe;
- Să rezumam că fiecare trecere are (valori totale în matrice, un anumit număr) minus (numărul de trecere) comparații.
Și mai pe scurt, algoritmul viitorului program poate fi scris după cum urmează:
- matricea de numere este verificată până când sunt găsite două numere, iar al doilea dintre ele trebuie să fie mai mare decât primul;
- Programul schimbă elementele de matrice care sunt poziționate incorect unele în raport cu altele.
Pseudocod bazat pe algoritmul descris
Cea mai simplă implementare este așa:
Procedură Sortirovka_Puzirkom;
start
bucla pentru j din index_inițial inainte de konechii_index;
bucla pentru i din index_inițial inainte de konechii_index-1;
Dacă masiv[i]>masiv
(schimbați valorile);
Sfârşit
Desigur, aici simplitatea nu face decât să agraveze situația: cu cât algoritmul este mai simplu, cu atât mai multe neajunsurile apar în el. Consumul de timp este prea mare chiar și pentru o matrice mică (relativitatea intră în joc aici: pentru o persoană obișnuită, cantitatea de timp poate părea mică, dar în afacerea unui programator, fiecare secundă sau chiar milisecundă contează).
Era nevoie de o implementare mai bună. De exemplu, ținând cont de schimbarea valorilor într-o matrice:
Procedură Sortirovka_Puzirkom;
start
sortirovka = adevărat;
ciclu până acum sortirovka = adevărat;
sortirovka = fals;
bucla pentru i din index_inițial inainte de konechii_index-1;
Dacă masiv[i]>masiv(primul element este mai mare decât al doilea), atunci:
(schimbarea elementelor);
sortirovka = adevărat; (a indicat că schimbul a fost făcut).
Sfârşit.
Dezavantajele metodei
Principalul dezavantaj este durata procesului. Cât durează să faci o bula?
Timpul de execuție este calculat din pătratul numărului de numere din matrice - rezultatul final este proporțional cu acesta.
În cel mai rău caz, matricea va fi parcursă de același număr de ori cât există elemente în ea minus o valoare. Acest lucru se întâmplă pentru că în cele din urmă rămâne doar un element cu nimic cu care să se compare, iar ultima trecere prin matrice devine o acțiune inutilă.
În plus, metoda simplă de sortare prin schimb, așa cum este numită și, este eficientă numai pentru matrice mici. Nu va fi posibil să procesați cantități mari de date cu ajutorul acestuia: rezultatul va fi fie erori, fie eșecul programului.
Avantaje
Sortarea cu bule este destul de simplu de înțeles. În programele de studii ale universităților tehnice, atunci când se studiază ordonarea elementelor de matrice, aceasta este acoperită mai întâi. Metoda este ușor de implementat atât în limbajul de programare Delphi (D), cât și în C/C++ (C/C plus plus), un algoritm incredibil de simplu pentru aranjarea valorilor în ordinea corectă, iar Bubble Sort este ideal pentru începători.
Din cauza deficiențelor sale, algoritmul nu este utilizat în scopuri extracurriculare.
Principiul de sortare vizuală
Vedere inițială a matricei 8 22 4 74 44 37 1 7
Pasul 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Pasul 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Pasul 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Pasul 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Pasul 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Pasul 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Pasul 7 1 4 7 8 22 37 44 74
Exemplu de sortare cu bule în Pascal
Exemplu:
const kol_mas=10;
var array:matrice de întreg;
a, b, k: întreg;
writeln("input", kol_mas, "elementele matricei");
for a:=1 to kol_mas do readln(array[a]);
pentru a:=1 la kol_mas-1 începe
pentru b:=a+1 la kol_mas începe
dacă massiv[a]>massiv[b] atunci începe
k:=matrice[a]; masiv[a]:=massiv[b]; matrice[b]:=k;
Sfârşit;
writeln("după sortare");
for a:=1 to kol_mas do writeln(massiv[a]);
Exemplu de sortare cu bule în limbajul C
#include
#include
int main(int argc, char* argv)
int massiv = (36, 697, 73, 82, 68, 12, 183, 88),i, ff;
pentru (; ;)(
ff = 0;
pentru (i = 7; i>0; i--)(
dacă (matrice[i]< massiv) {
swap(array[i],massiv);
dacă (ff == 0) rupere;
getch(); // întârziere ecran
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).
