Kuinka toteuttaa lajittelufunktio C ++: ssa?

Tämä artikkeli auttaa sinua tutkimaan lajittelutoimintoa c ++: ssa ja antamaan sinulle prosessissa yksityiskohtaisen esittelyn

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:



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:

Lähtö- Lajittelutoiminto C ++ - Edureka

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.