Lajittelu on yksi tietoihin käytetyistä perustavimmista ja hyödyllisimmistä toiminnoista. Sen tarkoituksena on järjestää tietoja tietyllä tavalla, joka voi olla kasvava tai laskeva vaatimusten mukaisesti. C ++ STL: ssä on sisäänrakennettu funktio nimellä 'sort ()', jonka avulla voimme suorittaa lajittelualgoritmin helposti. Tässä artikkelissa tutkitaan lajittelutoimintoa C ++: ssa,
Seuraavat osoittimet käsitellään tässä artikkelissa:
- Lajittelu () -toiminto
- Esimerkki - tietojen lajittelu nousevassa järjestyksessä
- Esimerkki - tietojen lajittelu laskevassa järjestyksessä
- Osittainen lajittelu
Siirrytään tähän artikkeliin Lajittelu-toiminnosta C ++: ssa
Järjestellä ( ) -toiminto
Se on algoritmin otsikkotiedoston sisäänrakennettu toiminto, jota käytetään lajittelemaan säiliöt kuten matriisi, vektorit tietyssä järjestyksessä. Sisäisesti tämä toiminto toteutetaan pikalajitteluna
Quicksort on jakamisen ja valloittamisen algoritmi. Quicksort jakaa ensin suuren luettelon elementeistä kahteen pienempään alaluetteloon: alempiin ja ylempiin elementteihin. Sitten Quicksort lajittelee aliluettelot rekursiivisesti.
Vaiheet ovat seuraavat:
1. Valitse luettelosta satunnaiselementti (yleensä viimeinen elementti), jota kutsutaan pivotiksi.
2. Järjestä luettelo uudelleen siten, että kaikki elementit, joiden arvot ovat pienempiä kuin kääntö, tulevat ennen kääntöä, kun taas kaikki elementit, joiden arvot ovat suurempia kuin kääntö, tulevat sen jälkeen ja yhtäläiset arvot voivat mennä jompaankumpaan suuntaan, tätä prosessia kutsutaan osioinniksi.
3. Lajittele pienempien elementtien alaluettelo ja suurempien elementtien alaluettelo rekursiivisesti, valitse pivot uudelleen alaluettelosta ja jaa ne.
Rekursioon perustapauksena on luettelot, joiden koko on nolla tai yksi, joita ei koskaan tarvitse lajitella, ja siten yhdistämällä ne lajittelemme luettelomme.
Quicksort on käytännössä nopeampi kuin muut O (n log n) -algoritmit, kuten Insertion Sort tai Bubble sort. Quicksort voidaan toteuttaa paikallisen osioinnin algoritmilla, mikä tarkoittaa, että koko lajittelu voidaan tehdä vain O (log n) -lisätilalla. Quicksort ei ole vakaa lajittelu.
Sen monimutkaisuus on seuraava:
Paras tapaus - O (n log n)
Pahin tapaus - O (n ^ 2)
Keskimääräinen tapaus - O (n log n)
Syntaksi:
lajittelu (ensimmäinen, viimeinen)
Tässä,
ensimmäinen - on lajiteltavan alueen ensimmäisen elementin indeksi (osoitin).
last - on lajiteltavan alueen viimeisen elementin indeksi (osoitin).
Haluamme esimerkiksi lajitella matriisin ‘arr’ elementit yhdestä kymmeneen asentoon, käytämme lajittelua (arr, arr + 10) ja se lajittelee 10 elementtiä nousevassa järjestyksessä.
Palautusarvo
Ei mitään
Monimutkaisuus
Lajittelukompleksisuuden keskiarvo on N * log2 (N), missä N = viimeinen - ensin.
Dataväli
Alueen [ensimmäinen, viimeinen] kohdetta muokataan.
Poikkeukset
Ylikuormitukset malliparametrilla, joka on nimetty ExecutionPolicy-raporttivirheiksi seuraavasti:
Jos algoritmi ei pysty varaamaan muistia, std :: bad_alloc heitetään poikkeuksena.
Jos algoritmin osana kutsutun funktion toteutus heittää poikkeuksen std :: terminate.
Siirrytään tähän artikkeliin Lajittelu-toiminnosta C ++: ssa
Esimerkki - tietojen lajittelu nousevassa järjestyksessä:
#include käyttämällä nimitilaa std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = size (matriisi) / sizeof (matriisi [0] ) // 'sizeof' ilmoittaa koko matriisin koon eli kunkin merkin koon * ei. merkkiä // joten ei. merkkiä // jaamme sizeof (matriisi) minkä tahansa taulukon yhden merkin kokoon // tässä se on matriisi [0] sort (matriisi, matriisi + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Tuotos:
ohittaa vs ylikuormitus c ++
Selitys
Yllä olevasta esimerkistä näemme, että lajittelutoiminto () oletusarvoisesti lajittelee taulukon nousevassa järjestyksessä.
Siirrytään tähän artikkeliin Lajittelu-toiminnosta C ++: ssa
Esimerkki - tietojen lajittelu laskevassa järjestyksessä:
Jos haluat lajitella matriisin tiedot laskevassa järjestyksessä, on otettava käyttöön kolmas parametri, jota käytetään järjestykseen, jossa elementit lajitellaan. Voimme käyttää ”suurempi ()” -toimintoa tietojen lajittelemiseen laskevassa järjestyksessä.
#include käyttämällä nimitilaa std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = size (matriisi) / sizeof (matriisi [0] ) sort (taulukko, taulukko + n, suurempi ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Tuotos:
Exp l kansakunta
Here sort () -funktio tekee vertailun tavalla, joka asettaa suuremman elementin ennen.
Siirrytään tähän artikkeliin Lajittelu-toiminnosta C ++: ssa
Osittainen lajittelu
C ++ STL tarjoaa meille osittaisen lajittelutoiminnon, funktio on samanlainen kuin lajittelu () -toiminto, mutta toisin kuin lajittelu () -toimintoa, sitä ei käytetä koko alueen lajitteluun, vaan sitä käytetään vain sen osan lajitteluun. Se lajittelee elementit alueelle [ensimmäinen, viimeinen] siten, että keskimmäistä elementtiä edeltävät elementit lajitellaan nousevassa järjestyksessä, kun taas keskimmäisen jälkeen olevat elementit jätetään sellaisenaan.
Sitä voidaan käyttää suurimman elementin löytämiseen, jos käytämme funktio-objektia ensimmäisen sijainnin lajittelussa
Esimerkki
yksinkertainen yhdistämisen lajitteluohjelma c ++: ssa
#include #include #include käyttämällä nimitilaa std int main () {vektori vec = {10, 45, 60, 78, 23, 21, 30} vektori :: iteraattori iptr partial_sort (vec.begin (), vec.begin () + 1, vec.end (), suurempi ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } Tuotos:
Selitys:
Yllä olevaa koodia voidaan käyttää löytämään suurin numero sarjassa, jotta löydettäisiin sarjan pienin numero, meidän on vain poistettava suurempi komento.
Siksi olemme päässeet tämän artikkelin 'Lajittelutoiminto C ++' -kohtaan. Jos haluat oppia lisää, tutustu luotettavan verkkokoulutusyrityksen Edurekan Java-koulutukseen. Edurekan kurssi on suunniteltu kouluttamaan sinua sekä ydin- että edistyneille Java-konsepteille sekä erilaisille Java-kehyksille, kuten Hibernate & Spring.
Onko sinulla kysymys meille? Mainitse se tämän blogin kommenttiosassa ja otamme sinuun yhteyttä mahdollisimman pian.