On arvioitu, että jopa neljännes keskitettyjen tietokoneiden ajasta kuluu tiedon lajitteluun. Tämä johtuu siitä, että on paljon helpompi löytää arvo taulukosta, joka on esilajiteltu. Muuten etsintä on vähän kuin neulan etsimistä heinäsuovasta.

Jotkut ohjelmoijat käyttävät kaiken työaikansa lajittelualgoritmien tutkimiseen ja toteuttamiseen. Tämä johtuu siitä, että suurin osa yritysohjelmistoista sisältää tietokannan hallinnan. Ihmiset etsivät tietoa tietokannoista koko ajan. Tämä tarkoittaa, että hakualgoritmeilla on suuri kysyntä.

Mutta on yksi "mutta". Hakualgoritmit toimivat paljon nopeammin jo lajiteltujen tietokantojen kanssa. Tässä tapauksessa tarvitaan vain lineaarinen haku.

Vaikka tietokoneet ovat jossain vaiheessa ilman käyttäjiä, lajittelualgoritmit jatkavat toimintaansa tietokannassa. Hakijoita tulee taas, ja tietokanta on jo lajiteltu yhden tai toisen hakutarkoituksen mukaan.

Tässä artikkelissa on esimerkkejä tavallisten lajittelualgoritmien toteutuksista.

Valinnan lajittelu

Jos haluat lajitella taulukon nousevaan järjestykseen, sinun on löydettävä kussakin iteraatiossa arvoltaan suurin elementti. Sen kanssa sinun on vaihdettava viimeinen elementti. Seuraava elementti, jolla on suurin arvo, sijoitetaan toiseksi viimeiseksi. Tämän pitäisi tapahtua, kunnes taulukon ensimmäisillä paikoilla olevat elementit ovat oikeassa järjestyksessä.

C++ koodi

void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i data[k])( j = k; ) ) tmp = data[i]; data[i] = data[j]; data[j] = tmp; ) )

Kuplalajittelu

Kuplalajittelu vertailee vierekkäisiä elementtejä ja vaihtaa paikkoja, jos seuraava elementti on pienempi kuin edellinen. Tietojen läpikulku vaaditaan useita. Ensimmäisen läpimenon aikana taulukon kahta ensimmäistä elementtiä verrataan. Jos ne eivät ole järjestyksessä, ne vaihdetaan ja sitten seuraavan parin elementtejä verrataan. Samalla ehdolla ne myös vaihtavat paikkaa. Siten lajittelu tapahtuu jokaisessa jaksossa, kunnes taulukon loppu saavutetaan.

C++ koodi

void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)( if (data[j]

Lisäyslajittelu

Lisäyslajittelu jakaa taulukon kahteen alueeseen: järjestettyyn ja järjestämättömään. Aluksi koko taulukko on järjestämätön alue. Ensimmäisellä ajolla ensimmäinen elementti järjestämättömältä alueelta poistetaan ja asetetaan oikeaan paikkaan järjestetylle alueelle.

Jokaisella kierrolla järjestetyn alueen koko kasvaa yhdellä ja epäjärjestyneen alueen koko pienenee yhdellä.

Pääsilmukka kulkee 1:stä N-1:een. J:nnessä iteraatiossa elementti [i] lisätään oikeaan paikkaan järjestetyllä alueella. Tämä tehdään siirtämällä kaikki järjestetyn alueen elementit, jotka ovat suurempia kuin [i] yksi paikka oikealle. [i] lisätään tilaan niiden elementtien väliin, jotka ovat pienempiä kuin [i], ja niiden, jotka ovat suurempia kuin [i].

C++ koodi

void SortAlgo::insertionSort(int data, int lenD) ( int avain = 0; int i = 0; for (int j = 1;j =0 && data[i]>avain)( data = data[i]; i = i-1; data=avain; ) ) )

Yhdistä lajittelu

C++ koodi

void SortAlgo::mergeSort(int data, 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

Nopea lajittelu

Quicksort käyttää hajota ja hallitse -algoritmia. Se alkaa jakamalla alkuperäinen matriisi kahteen alueeseen. Nämä osat ovat merkityn elementin, jota kutsutaan tueksi, vasemmalla ja oikealla puolella. Prosessin lopussa yksi osa sisältää viittausta pienempiä elementtejä ja toinen osa sisältää viittausta suurempia elementtejä.

C++ koodi

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 = uusi int ; int * R = uusi int ; pivot = data; for (i=0;i

Hei kaikki!

Tänään tarkastellaan kuplalajittelua. Tätä algoritmia opetetaan usein kouluissa ja yliopistoissa, joten käytämme Pascalia. Joten mitä on lajittelu? Lajittelu on elementtien järjestystä pienimmästä suurimpaan (nouseva lajittelu) tai suurimmasta elementistä pienimpään (laskeva lajittelu). Taulukot lajitellaan yleensä.

Lajittelualgoritmeja on erilaisia. Jotkut ovat hyviä lajittelemaan suuren määrän elementtejä, toiset ovat tehokkaampia hyvin pienellä määrällä elementtejä. Kuplamenetelmällemme on ominaista:

Plussat:

• Algoritmin toteuttamisen helppous
• Kaunis nimi

Miinukset:

• Yksi hitaimmista lajittelumenetelmistä (Suoritusaika riippuu neliöllisesti taulukon pituudesta n 2)
• Lähes ei käytetä tosielämässä (käytetään pääasiassa opetustarkoituksiin)

Otetaan tietty taulukko: 3 1 4 2

Algoritmi: Otamme taulukon elementin, vertaamme sitä seuraavaan, jos elementtimme on suurempi kuin seuraava elementti, niin vaihdamme ne. Kun olemme käyneet läpi koko taulukon, voimme olla varmoja, että maksimielementti "työnnetään ulos" - ja se on aivan viimeinen. Yksi elementti on siis jo täsmälleen paikallaan. Koska meidän on asetettava ne kaikki paikoilleen, joten tämä toimenpide on toistettava niin monta kertaa kuin meillä on taulukon elementtejä miinus 1. Viimeinen elementti pysyy automaattisesti paikallaan, jos loput ovat paikoillaan.

Palataan taulukkoomme: 3 1 4 2
Otamme ensimmäisen elementin "3" ja vertaamme sitä seuraavaan "1". Koska "3" > "1" ja vaihda sitten paikkoja:
1 3 4 2
Nyt vertaamme "3" ja "4", kolme on enintään neljä, mikä tarkoittaa, että emme tee mitään. Seuraavaksi vertaa "4" ja "2". Neljä on enemmän kuin kaksi - joten vaihdamme paikkoja: 1 3 2 4. Kierto on ohi. Tämä tarkoittaa, että suurimman elementin pitäisi olla jo paikallaan!! Näemme, että tässä on käynyt näin. Missä tahansa "4" (suurin elementtimme) sijaitsee, se on silti viimeinen sen jälkeen, kun silmukka on kulkenut koko taulukon läpi. Analogia - aivan kuten ilmakupla kelluu vedessä, niin myös elementtimme kelluu joukossa. Siksi algoritmi on nimeltään "Bubble Sort". Seuraavan elementin sijoittamiseksi on välttämätöntä aloittaa sykli alusta, mutta viimeistä elementtiä ei voida enää ottaa huomioon, koska se on paikallaan.

Vertaamme "1" ja "3" - emme muuta mitään.
Vertaamme "3" ja "2" - kolme on enemmän kuin kaksi, mikä tarkoittaa, että vaihdamme paikkoja. Osoittautuu: 1 2 3 4 . Toinen sykli on valmis. Olemme jo suorittaneet kaksi sykliä, mikä tarkoittaa, että voimme varmuudella sanoa, että kaksi viimeistä elementtiämme on jo lajiteltu. Meidän tarvitsee vain lajitella kolmas elementti, ja neljäs putoaa automaattisesti oikeaan paikkaan. Jälleen kerran vertaamme ensimmäistä elementtiä ja toista - näemme, että meillä on jo kaikki paikoillaan, mikä tarkoittaa, että taulukkoa voidaan pitää lajiteltuna elementtien nousevaan järjestykseen.

Nyt ei jää muuta kuin ohjelmoida tämä algoritmi Pascalilla. vakio n = 4; (Asetimme vakion, tämä on taulukon pituus) var i, j, k:integer; (Kaksi muuttujaa sisäkkäiselle silmukalle, yksi elementtien vaihtamiseen) m:array of integer; (Luomme taulukon) begin (Pyydämme taulukon näppäimistöltä:) Writeln("Anna taulukko:"); i:=1 - n aloita Writeln(i, " element:"); Readln(m[i]); loppu; (Ulkosilmukka on vastuussa siitä, että meidän on toistettava sisäinen silmukka niin monta kertaa kuin meillä on taulukon elementtejä miinus 1.) i:=1 - n-1 aloita (sisäinen silmukka iteroi jo elementtien läpi ja vertailee toistensa kanssa.) j :=1 - n-i aloita (Jos alkio on suurempi kuin seuraava, vaihda paikkoja.) jos m[j]>m aloita k:=m[j]; m[j]: = m; m:=k; loppu; loppu; loppu; (Tulosta tulos:) for i:=1 to n do Write(m[i], " "); loppu.
Tässä tulos:

Tässä on opetusvideo

Kaikki tietävät varsin hyvin, että vaihtolajien luokasta nopein menetelmä on ns nopea lajittelu. Siitä kirjoitetaan väitöskirjoja, sille on omistettu monia Habrén artikkeleita ja sen pohjalta keksitään monimutkaisia ​​hybridialgoritmeja. Mutta tänään emme puhu siitä nopea lajittelu, ja toisesta vaihtomenetelmästä - vanhasta hyvästä kuplalajittelu ja sen parannukset, modifikaatiot, mutaatiot ja muunnelmat.

Käytännön hyöty näistä menetelmistä ei ole niin suuri, ja monet habran käyttäjät kävivät tämän läpi jo ensimmäisellä luokalla. Siksi artikkeli on osoitettu niille, jotka ovat juuri kiinnostuneet algoritmien teoriasta ja ottavat ensimmäiset askeleensa tähän suuntaan.

kuva: kuplia

Tänään puhumme yksinkertaisimmista vaihtolajittelut.

Jos jotakuta kiinnostaa, kerron, että on muitakin kursseja - valinta lajittelu, lisäyslajittelu, Yhdistä lajittelu, jakelun lajittelu, hybridilajit Ja rinnakkaisia ​​lajikkeita. On muuten myös esoteeriset lajittelut. Nämä ovat erilaisia ​​väärennettyjä, pohjimmiltaan toteuttamattomia, sarjakuvia ja muita pseudo-algoritmeja, joista kirjoitan pari artikkelia ”IT Huumori” -keskukseen.

Mutta tällä ei ole mitään tekemistä tämän päivän luennon kanssa; olemme nyt kiinnostuneita vain yksinkertaisista vaihtolajitteluista. Myös itse vaihtolajitteluja on paljon (tiedän yli tusina), joten tarkastellaan ns. kuplalajittelu ja jotkut muut siihen läheisesti liittyvät.

Varoitan teitä etukäteen, että melkein kaikki yllä mainitut menetelmät ovat erittäin hitaita ja niiden aikamonimutkaisuutta ei analysoida syvällisesti. Jotkut ovat nopeampia, jotkut ovat hitaampia, mutta karkeasti sanottuna voimme sanoa, että keskimäärin O(n 2). En myöskään näe mitään syytä sotkea artikkelia toteutuksilla millä tahansa ohjelmointikielellä. Kiinnostuneet löytävät helposti koodiesimerkkejä Rosettasta, Wikipediasta tai muualta.

Mutta palataanpa vaihtojen lajitteluun. Järjestys tapahtuu taulukon toistuvan peräkkäisen haun ja elementtiparien vertailun seurauksena. Jos vertailtavia elementtejä ei ole lajiteltu suhteessa toisiinsa, ne vaihdetaan. Ainoa kysymys on, kuinka tarkasti taulukko ohitetaan ja millä perusteella valitaan parit vertailua varten.

Ei aloiteta tavallisesta kuplalajittelusta, vaan algoritmista nimeltä...

Tyhmä lajike

Lajittelu on todella typerää. Katsomme taulukkoa vasemmalta oikealle ja vertaamme naapureita matkan varrella. Jos kohtaamme parin keskenään lajittelemattomia elementtejä, vaihdamme ne ja palaamme ruutuun, eli aivan alkuun. Käymme läpi ja tarkistamme taulukon uudelleen, jos kohtaamme jälleen "virheellisen" parin naapurielementtejä, vaihdamme paikkoja ja aloitamme alusta. Jatketaan kunnes matriisi on pikkuhiljaa lajiteltu.

"Jokainen typerys voi lajitella noin", sanot ja olet täysin oikeassa. Tästä syystä lajittelua kutsutaan "tyhmäksi". Tällä luennolla parannamme ja muokkaamme tätä menetelmää jatkuvasti. Nyt hänellä on tilapäisiä vaikeuksia O(n 3), kun olemme tehneet yhden korjauksen, tuomme sen jo O(n 2), sitten nopeuttamme sitä vielä hieman, sitten vähän enemmän, ja lopulta saamme O(n Hirsi n) – eikä se ole ollenkaan "Pikalajittelu"!

Tehdään yksi parannus typerään lajitteluun. Kun olemme löytäneet kaksi vierekkäistä lajittelematonta elementtiä kulun aikana ja vaihtaneet ne, emme rullaa takaisin taulukon alkuun, vaan jatkamme rauhallisesti sen läpikulkua aivan loppuun asti.

Tässä tapauksessa meillä ei ole edessämme muuta kuin tunnettu...

Kuplalajittelu

Tai lajittelu yksinkertaisten vaihtojen avulla. Genren kuolematon klassikko. Toimintaperiaate on yksinkertainen: kuljemme taulukon läpi alusta loppuun vaihtaen samalla lajittelemattomia naapurielementtejä. Ensimmäisen ajon seurauksena maksimielementti "kelluu" viimeiselle paikalle. Nyt kuljemme jälleen taulukon lajittelemattoman osan läpi (ensimmäisestä elementistä toiseksi viimeiseen) ja muutamme lajittelemattomia naapureita matkan varrella. Toiseksi suurin elementti on toiseksi viimeisellä sijalla. Jatkamme samassa hengessä, kuljemme taulukon jatkuvasti pienenevän lajittelemattoman osan läpi työntäen löydetyt maksimit loppuun.

Jos emme vain työnnä maksimiarvoja loppuun, vaan työnnämme myös minimit alkuun, onnistumme...

Shaker lajittelu

Hän on sama sekoitus lajittelu, hän on sama cocktailien lajittelu. Prosessi alkaa kuin "kuplassa": puristamme maksimin taakse. Tämän jälkeen käännetään 180 0 ja mennään vastakkaiseen suuntaan, samalla kun rullataan takaisin alkuun ei maksimi, vaan minimi. Kun olet lajitellut taulukon ensimmäisen ja viimeisen elementin, teemme kuperkeikka uudelleen. Käytyään edestakaisin useita kertoja, päätämme lopulta prosessin ja päädymme luettelon keskelle.

Shaker-lajittelu toimii hieman nopeammin kuin kuplalajittelu, koska sekä maksimi- että minimiarvot liikkuvat vuorotellen taulukon läpi haluttuihin suuntiin. Parannukset, kuten he sanovat, ovat ilmeisiä.

Kuten näet, jos lähestyt luettelointiprosessia luovasti, raskaiden (kevyiden) elementtien työntäminen ulos taulukon päihin tapahtuu nopeammin. Siksi käsityöläiset ehdottivat toista epätyypillistä "tiekarttaa" kiertääkseen luetteloa.

Pariton lajittelu

Tällä kertaa emme rypistele edestakaisin taulukon poikki, vaan palaamme taas ajatukseen järjestelmällisestä kiertämisestä vasemmalta oikealle, mutta otamme vain leveämmän askeleen. Ensimmäisellä ajokerralla parittomalla avaimella varustettuja elementtejä verrataan naapureihinsa parillisten paikkojen perusteella (ykköstä verrataan toiseen, sitten 3:ta 4:een, 5:tä kuudenteen ja niin edelleen). Sitten päinvastoin vertaamme/muutamme "parillisia" elementtejä "parittomiin". Sitten taas "parillinen-parillinen", sitten taas "parillinen-parillinen". Prosessi pysähtyy, kun kahden peräkkäisen taulukon läpi ("pariton-parillinen" ja "parillinen") ei ole tapahtunut yhtään vaihtoa. Joten he järjestivät sen.

Tavallisessa "kuplassa" puristamme jokaisen läpimenon aikana järjestelmällisesti nykyisen maksimin taulukon loppuun. Jos hyppäät parillisten ja parittomien indeksien mukaan, niin kaikki taulukon enemmän tai vähemmän suuret elementit työnnetään samanaikaisesti oikeaan kohtaan yhdellä juoksulla. Se toimii nopeammin tällä tavalla.

Katsotaanpa viimeistä koristeltu uudelleen* Sillä Sortuvannya bulbashka** - Lajittelu kamman mukaan***. Tämä menetelmä organisoituu hyvin nopeasti, O(n 2) on sen pahin vaikeus. Meillä on keskimäärin ajan mittaan O(n Hirsi n), ja mikä parasta, et edes usko sitä, O(n). Eli erittäin arvokas kilpailija kaikenlaisille "pikalajeille" ja tämä, muistakaa, ilman rekursiota. Lupasin kuitenkin, että tänään emme syvenny risteilynopeuksiin, joten lopetan puhumisen ja siirryn suoraan algoritmiin.

Kaikki on kilpikonnien syytä

Vähän taustaa. Vuonna 1980 Włodzimierz Dobosiewicz selitti, miksi kuplalajittelu ja sen johdannaiset toimivat niin hitaasti. Kaikki johtuu kilpikonnista. "Kilpikonnat" ovat pieniä elementtejä, jotka sijaitsevat luettelon lopussa. Kuten olet ehkä huomannut, kuplalajittelut keskittyvät "kaneihin" (jota ei pidä sekoittaa Babushkinin "kaneihin") - suuriarvoisia elementtejä luettelon alussa. He liikkuvat erittäin reippaasti kohti maaliviivaa. Mutta hitaat matelijat ryömivät alkuun vastahakoisesti. Voit muokata tortillaa käyttämällä kammat.

kuva: syyllinen kilpikonna

Kampalajittelu

"Kuplassa", "shakerissa" ja "parittisessa paritossa" taulukon läpi iteroitaessa verrataan viereisiä elementtejä. "Kamman" pääideana on ottaa aluksi riittävän suuri etäisyys vertailtavien elementtien välillä ja kaventaa tätä etäisyyttä minimiin, kun ryhmä on tilattu. Tällä tavalla kampaamme matriisin asteittain tasoittaen sitä yhä siistimmiksi säikeiksi.

On parempi ottaa vertailtavien elementtien välinen alkurako ei mitä tahansa, vaan ottaa huomioon erityinen arvo, jota kutsutaan vähentävä tekijä, jonka optimaalinen arvo on noin 1,247. Ensinnäkin elementtien välinen etäisyys on yhtä suuri kuin taulukon koko jaettuna vähennyskerroin(tulos tietysti pyöristetään lähimpään kokonaislukuun). Sitten, kun olemme käyneet läpi taulukon tällä askeleella, jaamme askeleen jälleen vähennyskerroin ja käy listaa uudelleen läpi. Tätä jatketaan, kunnes indeksiero saavuttaa yhden. Tässä tapauksessa matriisi lajitellaan tavallisella kuplalla.

Optimaalinen arvo on määritetty kokeellisesti ja teoreettisesti vähennyskerroin:

Kun tämä menetelmä keksittiin, harvat kiinnittivät siihen huomiota 70- ja 80-luvun vaihteessa. Vuosikymmen myöhemmin, kun ohjelmointi ei enää ollut IBM:n tiedemiesten ja insinöörien maakunta, mutta se oli jo saavuttamassa nopeasti massasuosiota, Stephen Lacy ja Richard Box löysivät menetelmän uudelleen, tutkivat ja suosittelivat sitä vuonna 1991.

Siinä on oikeastaan ​​kaikki, mitä halusin kertoa kuplalajittelusta ja muista vastaavista.

- Huomautuksia

* lyhennetty ( ukrainalainen) - parannus
** Lajiteltu polttimon mukaan ( ukrainalainen) – Kuplalajittelu
*** Lajittelu kamman mukaan ( ukrainalainen) – Kampalajittelu

Järjestetään taulukko ylhäältä alas nollaelementistä viimeiseen.

Menetelmän idea: lajitteluvaihe koostuu taulukon läpi kulkemisesta alhaalta ylös. Matkan varrella tarkastellaan vierekkäisten elementtien pareja. Jos tietyn parin elementit ovat väärässä järjestyksessä, ne vaihdetaan.

Kun nolla kulkee taulukon läpi, kevyin elementti ilmestyy yläosaan - tästä johtuu analogia kuplan kanssa. Toiselle elementille siirrytään seuraavaksi ylhäältä, jolloin toiseksi suurin elementti nostetaan oikeaan asentoon...

Teemme kulkua taulukon jatkuvasti laskevaa alaosaa pitkin, kunnes siihen jää vain yksi elementti. Lajittelu päättyy tähän, koska järjestys on nousevassa järjestyksessä.

Sapluuna void bubbleSort(T a, pitkä koko) ( pitkä i, j; T x; for(i=0; i< size; i++) { // i - passin numero for(j = koko-1; j > i; j--) ( // sisäsilmukka jos (a > a[j]) (x=a; a=a[j]; a[j]=x; ) ) )

Keskimääräisellä vertailujen ja vaihtojen lukumäärällä on neliöllinen kasvujärjestys: Theta(n 2), josta voimme päätellä, että kupla-algoritmi on erittäin hidas ja tehoton.
Sillä on kuitenkin valtava etu: se on yksinkertainen ja sitä voidaan parantaa kaikin tavoin. Mitä nyt tehdään?

Tarkastellaan ensin tilannetta, jossa vaihtoja ei tapahtunut millään passilla. Mitä se tarkoittaa?

Tämä tarkoittaa, että kaikki parit ovat oikeassa järjestyksessä, joten matriisi on jo lajiteltu. Ja prosessia ei ole järkevää jatkaa (varsinkin jos matriisi lajiteltiin alusta alkaen!).

Algoritmin ensimmäinen parannus on siis muistaa, tehtiinkö vaihtoa tietyllä passilla. Jos ei, algoritmi päättyy.

Parannusprosessia voidaan jatkaa, jos muistat paitsi itse vaihdon tosiasian myös viimeisen vaihdon indeksin k. Todellakin: kaikki vierekkäisten elementtien parit, joiden indeksi on pienempi kuin k, sijaitsevat jo vaaditussa järjestyksessä. Muut siirrot voivat päättyä indeksiin k sen sijaan, että siirtyisivät ennalta määrättyyn ylärajaan i.

Laadullisesti erilainen parannus algoritmiin voidaan saada seuraavasta havainnosta. Vaikka pohjassa oleva kevyt kupla nousee ylös yhdellä kertaa, raskaat kuplat uppoavat minimaalisella nopeudella: yksi askel per iteraatio. Joten matriisi 2 3 4 5 6 1 lajitellaan yhdellä kertaa, mutta sarjan 6 1 2 3 4 5 lajittelu vaatii 5 kulkua.

Tämän vaikutuksen välttämiseksi voit muuttaa peräkkäisten syöttöjen suuntaa. Tuloksena olevaa algoritmia kutsutaan joskus " shaker lajittelu".

Sapluuna void shakerSort(T a, pitkä koko) ( pitkä j, k = koko-1; pitkä lb=1, ub = koko-1; // taulukon lajittelemattoman osan rajat Tx; tehdä ( // siirtyy alhaalta ylös for(j=ub; j>0; j--) (jos (a > a[j]) (x=a; a=a[j]; a[j]=x; k=j; ) ) lb = k+1; // siirtyy ylhäältä alas varten (j = 1; j<=ub; j++) { if (a >a[j]) (x=a; a=a[j]; a[j]=x; k=j; )) ub = k-1; ) kun (lb< ub); }

Missä määrin kuvatut muutokset ovat vaikuttaneet menetelmän tehokkuuteen? Vertailujen keskimääräinen määrä, vaikka se laski, on edelleen O(n 2), kun taas vaihtojen määrä ei ole muuttunut lainkaan. Keskimääräinen (alias pahin) operaatioiden määrä pysyy neliöllisenä.

Lisämuistia ei tietenkään tarvita. Parannetun (mutta ei alkuperäisen) menetelmän käyttäytyminen on melko luonnollista; melkein lajiteltu matriisi lajitellaan paljon nopeammin kuin satunnainen. Kuplalajittelu on vakaata, mutta ravistelijalajittelu menettää tämän laadun.

Käytännössä kuplamenetelmä toimii parannuksillakin, valitettavasti, liian hitaasti. Ja siksi sitä ei käytetä melkein koskaan.

Tietotaulukoiden kanssa työskenneltäessä tehtävä tulee usein esiin lajittelu nousevaan tai laskevaan järjestykseen, ts. tilaaminen. Tämä tarkoittaa, että saman taulukon elementit on järjestettävä tiukasti järjestykseen. Esimerkiksi nousevassa lajittelussa edeltävän elementin on oltava pienempi (tai yhtä suuri kuin) seuraava elementti.

Ratkaisu

Lajittelumenetelmiä on monia. Jotkut niistä ovat tehokkaampia, toiset on helpompi ymmärtää. Lajittelu on melko helppo ymmärtää kuplamenetelmä, jota myös kutsutaan yksinkertainen vaihtotapa. Mikä se on ja miksi sillä on niin outo nimi: "kuplamenetelmä"?

Kuten tiedät, ilma on vettä kevyempää, joten ilmakuplat kelluvat. Se on vain analogia. Nousevassa kuplalajittelussa kevyemmät (pienempiarvoiset) elementit "kelluvat" vähitellen taulukon alkuun ja raskaammat putoavat peräkkäin alas (taulukon loppuun).

Tämän lajittelun algoritmi ja ominaisuudet ovat seuraavat:

1. Ensimmäisen taulukon läpikäynnin aikana elementtejä verrataan keskenään pareittain: ensimmäinen toiseen, sitten toinen kolmanteen, sitten kolmas neljänteen jne. Jos edellinen elementti on suurempi kuin seuraava, ne vaihdetaan.
2. Ei ole vaikea arvata, että vähitellen suurin numero osoittautuu viimeiseksi. Muu osa taulukosta jää lajittelematta, vaikka pienemmän arvon elementit liikkuvat jonkin verran taulukon alkuun.
3. Toisella ajolla viimeistä elementtiä ei tarvitse verrata toiseksi viimeiseen. Viimeinen elementti on jo paikallaan. Tämä tarkoittaa, että vertailujen määrä on yksi vähemmän.
4. Kolmannella ajolla ei ole enää tarvetta verrata toiseksi viimeistä ja kolmatta elementtiä lopusta. Siksi vertailujen määrä on kaksi vähemmän kuin ensimmäisessä ajossa.
5. Loppujen lopuksi, kun iteroidaan taulukon läpi, kun vertailtavia elementtejä on jäljellä vain kaksi, suoritetaan vain yksi vertailu.
6. Tämän jälkeen ensimmäistä elementtiä ei ole mihinkään verrata, joten lopullinen läpikulku taulukon läpi on tarpeeton. Toisin sanoen taulukon läpikulkujen määrä on m-1, missä m on taulukon elementtien lukumäärä.
7. Vertailujen määrä kussakin läpikäynnissä on yhtä suuri kuin m-i, missä i on taulukon läpivientien lukumäärä (ensimmäinen, toinen, kolmas jne.).
8. Matriisielementtejä vaihdettaessa käytetään yleensä "puskuri" (kolmas) muuttujaa, johon yhden elementin arvo sijoitetaan tilapäisesti.

Pascal-ohjelma:

const m = 10; var arr: jono [ 1 .. m ] kokonaisluku ; i, j, k: kokonaisluku ; aloita satunnaisuus; kirjoittaa( "Lähdetaulukko: ") ; for i : = 1 to m do alkaa arr[ i] : = satunnainen(256 ); kirjoittaa (arr[ i] : 4 ) ; loppu; kirjoitettu; kirjoitettu; i : = 1 - m- 1 do j : = 1 - m- i do jos arr[ j] > arr[ j+ 1 ] aloita sitten k : = arr[ j] ; arr[ j] : = arr[ j+ 1 ] ; arr[ j+ 1 ] : = k end ; kirjoittaa( "Lajiteltu array:") ; for i : = 1 to m ei kirjoittaa (arr[ i] : 4 ); kirjoitettu; lue loppu.