Rekursio-ja lajittelualgoritmit

aion esittää aika lailla kaikki lajittelualgoritmit rekursiivisesti,joten pitäisi varmaan puhua rekursiosta. Rekursio on todella mielen laajentavaa tekniikkaa, kunhan siitä pääsee jyvälle. Se on myös perusta ohjelmoinnin matemaattiselle tulkinnalle, – joten jos olet CSci: n pääaine, sinun on totuttava siihen ennemmin tai myöhemmin. Joten Katsotaanpa joitakin yksinkertaisia algoritmeja, sekä iteratiivisesti (käyttäen silmukoita) ja rekursiivisesti.

Faktorin löytäminen

n faktori määritellään tuotteeksi \(n (n-1) (n-2) \ldots (2) (1)\), eli kaikkien kokonaislukujen tuotteeksi n: ään asti ja mukaan lukien.:

int factorial_iter(int n) { int r = 1; // Factorial of 0 is 1 for(int i = 1; i <= n; ++i) r *= i; return r;}

kirjoittaaksemme tämän tai minkä tahansa muun algoritmin rekursiivisesti meidän on kysyttävä kaksi kysymystä:

  • mikä on pienin tapaus, jossa voin antaa vastauksen heti? Tätä kutsutaan”perustapaukseksi”. (Joskus saattaa olla enemmän kuin yksi pienin tapaus, ja se on OK.)

  • mitä tahansa, joka ei ole pienin tapaus, miten voin murtaa sen alas tehdä pienempi? Tätä kutsutaan rekursiiviseksi tapaukseksi.

factorialissa perustapaus on se, mitä tapahtuu, kun \(N = 0\): loopdooes ei toimi lainkaan, ja 1 palautetaan. Joten voimme aloittaa rekursiivisen versiomme

int factorial_rec(int n) { if(n == 0) return 1; else ...}

rekursiivisen tapauksen konstruoimiseksi on tarkasteltava, mitä tapahtuu, kun n > 0. Erityisesti, miten voimme rikkoa \(n!\ ) alas johonkin \(n’!, n ’ < n\)?Yleisin tapaus on \(n ’ = N-1\).

yksi tapa tarkastella tätä on olettaa, että meillä on jo arvo \((n-1)!\ ), ja haluamme saada \(n!\) sieltä. Toisin sanoen oletetaan, ettäfactorial_rec(n - 1) toimii ja antaa meille oikean vastauksen; meidän tarvitsee vain konstruoida n: n faktori siitä. Miten voimme tehdä tämän?\(n! = n (n-1)!\). Joten kirjoitamme rekursiivisen tapauksemme näin:

int fact(int n) { if(n == 0) return 1; else return n * fact(n - 1);}

kävelläänpä hetki läpi laskentaprosessia factorial_rec(3):

  • fact(3) = 3 * fact(2)

  • fact(2) = 2 * fact(1)

  • fact(1) = 1 * fact(0)

  • fact(0) = 1 ja tässä vaiheessa voimme ponnistella takaisin ylöspäin, jolloin tulos 3 * 2 * 1 * 1 = 6.

Induktiivinen todistus

miten osoitamme, että funktio tekee sen, mitä sen oletetaan tekevän? Voisimme testata sitä, ajaa sitä tuhansia tai miljoonia kertoja ja varmistaa, että sen ulostulo on mitä odotamme, mutta tämä edellyttää, että keksimme riippumattoman tavan määritellä, mitä funktio tekee (esim., eri tapa computing factorial), joka voi itsessään olla virheellinen, ja lisäksi, toistuva testaus voi vain koskaan antaa tilastollinen luottamus siihen, että meidän algoritmi on oikea. Jos haluamme olla varmoja, tarvitsemme loogisen tai matemaattisen todisteen siitä, että se on oikea. Forrecursive funktiot, tämä on usein muodossa todiste induktiolla. Aninduktiivinen todistus on eräänlainen matemaattinen vastine rekursiiviselle funktiolle.Rekursiivisen funktion tavoin sillä on perustapaus(t) (yksi perustapaus, itse asiassa jokaista funktion perustapausta kohti), ja perustapaukset ovat yleensä helppoja. Se on myös induktiivinen tapaus (s) (yksi kunkin rekursiivinen tapauksessa funktio), jotka ovat hieman vaikeampaa, mutta voimme tehdä jotain rekursio.

tarkastellaan yllä olevaa esimerkkiä. Haluamme todistaa, että fact(n) = \(n!\ ), missä \(n! = n(n-1) (n-2)\ldots(2) (1), 0! = 1\).

Proof by induktio on n (whatever variable we do the rekursion on, we say weare doing ”proof by induktio” on that variable):

  • Perustapaus, \(N = 0\) sitten fact(0) = 1 =\(0!\ ) ja olemme valmiita.

  • Induktiivinen tapaus: Induktiivisessa tapauksessa pyritään todistamaan, että fact(n) = \(n!\ ) ”joillekin \(n > 0\). Voimme hajottaa vasemman ja oikean puolen ja nähdä, että meillä on todellisuudessa

    $$N \cdot \mathtt{fact}(n-1) = n! = n (n-1) (n-2) \ldots (2)(1)$$

    jakamalla \(n\) saadaan

    $$\mathtt{fact}(n-1) = (n-1)(n-2) \ldots (2)(1) = (n-1)!$$

    toisin sanoen, olemme vähentäneet ongelmaa todistaa, että fact(n) = \(n!\ ) ongelmaan todistaa, että fact(n-1) =\((n-1)!\). Se ei tunnu hyödylliseltä, mutta kuten rekursiivisessa funktiossa, jossa voimme kutsua itse funktiota pienemmällä argumentilla, induktiivisessa todistuksessa Voimme käyttää uudelleen itse todistusta oletuksena, pienemmälle \(n\). Kutsumme tätä oletusta induktiiviseksi hypoteesiksi ja se näyttää tältä:

    $$\text{oleta}\qquad\mathtt{fact} (n’) = n’! \qquad \text{for all}\; n’ < n$$

    jos annamme \(n ’ = N-1\), meillä on

    $$\text{oleta}\qquad\mathtt{fact}(N-1) = (n-1)!$$

    , joka on juuri sitä, mitä edellä tarvittiin! Korvaamalla tässä edellä mainittu saamme

    $$(n-1)! = (n-1)!$$

    ja olemme valmiita.

kuten rekursio, induktiivisen todistuksen ydin on itse todistuksen soveltaminen oletuksena ”pienemmistä” arvoista (\(n ’ < n\)). Teknisesti induktiivisia vedoksia on kahdenlaisia:

  • ”luonnollisen luvun induktio” antaa meille vain mahdollisuuden tehdä oletus \(n ’ = N-1\). Toisin sanoen voimme vain tehdä olettamuksen” syötöstä”, joka on pienempi kuin alkuperäinen.

  • ”vahva induktio” antaa meidän käyttää mitä tahansa \(n ’ < n\). Vahvaa induktiota voi käyttää missä tahansa, missä voi käyttää luonnollista lukuinduktiota, mutta sitä ei aina tarvita.

kokonaisluvun eksponenttilaskelma

Muistatko, kun selvitimme ”optimoidun” \(O(\log n)\) funktiomme ajonaikaisen monimutkaisuuden \(B^n\) – funktion löytämiseksi? Voimme kirjoittaa rekursiivinen versio, että samoin. Jälleen kerran, meidän on kysyttävä

  • mikä on perustapaus? Tässä tapauksessa se on, kun \(N = 0\). Tällöin \(B^0 = 1\), ei ole väliä mitä f on (on jonkin verran keskustelua \(0^0\)).

  • mikä on rekursiivinen tapaus? Miten hajotamme \(B^n\) \(B^{n’}\)? Tässä otetaan jono aiemmasta toteutuksesta:

    $$B^n = (B^{n/2})^2 \quad\text{jos } n \ text{ on parillinen}$$
    $$b^n = b \cdot B^{n-1} \quad\text{jos } n \text{ on pariton}$$

tämä antaa meille seuraavan määritelmän:

float powi(float b, int n) { if(n == 0) return 1; else if(n % 2 == 0) { // Even float fp = powi(b, n / 2); return fp * fp; } else if(n % 2 == 1) // Odd return f * powi(b, n - 1);}

tämä on yhtä monimutkainen kuin loop-pohjainen versio, ja on luultavasti yksinkertaisempi.

tässä tapauksessa, jos haluamme todistaa, että \(\mathtt{powi}(B, n) = B^n\), tarvitsemme vahvan induktion, koska yksi rekursiivisista tapauksista kutistaa inputbyn jollakin muulla kuin vain -1: llä.

todistaa, että \(\mathtt{powi}(B, n) = B^n\) vahvalla induktiolla \(n\):

  • perustapaus: \(n = 0\)

    sitten katsomalla ohjelmaa saamme \(\mathtt{powi} (N, 0) = 1 = b^0\) ja olemme valmiita.

  • Induktiivinen tapaus: \(n > 0\), todista \(\mathtt{powi}(B,n) = B^n\). Tässä on itse asiassa kaksi induktiivista tapausta, joista kukin on funktion kaksi rekursiivista tapausta. Induktiivinen hypoteesimme (oletus) on

    $$\mathtt{powi}(B,n’) = B^{n’}\qquad \text{for all}\; n’ < n$$
    • tapaus 1, \(n\) on parillinen. Sitten korvataan kutsu powi sen palautusarvolla olemme

      $$\mathtt{powi}(B, n / 2)^2 = B^n$$ $$\mathtt{powi}(B, n / 2)^2 = (B^{n/2})^2$$

      kun neliöjuuri molemmin puolin:

      $$\mathtt{powi}(B, n/2) = B^{n/2}$$

      jolloin voidaan soveltaa IH, jossa \(N’ = N / 2\), jolloin saadaan

      $$B^{n / 2} = B^{n/2}$$
    • Tapaus 2, \(n\) on pariton. Sitten laajennetaan powi saadaan

      $$b \cdot \mathtt{powi}(B,n-1) = b \cdot B^{n-1}$$ $\mathtt{powi}(B,n-1) = B^{n-1} (\text{ divide by } B) $$$ $B^{n-1} = B^{n-1}\qquad\text{by IH,} (n ’ = n-1)$$

    ja todiste on täydellinen

keskinäinen rekursio

keskinäinen rekursio on, kun määrittelemme useita rekursiivisia funktioita termeillä ofeach other. Tarkastellaan esimerkiksi seuraavaa parillisen ja parittoman määritelmää:

  • luonnollinen luku n on parillinen iff \(n-1\) on pariton.

  • luonnollinen luku n on pariton iff \(n-1\) on parillinen.

  • \(1\) on pariton, \(0\) on parillinen. (Nämä ovat meidän perustapauksia.)

voimme sitten määritellä kaksi funktiota (predikaatit), jotka rekursiivisesti viittaavat toisiinsa:

bool is_even(int n) { if(n == 0) return true; else if(n == 1) return false; else return is_odd(n - 1);}bool is_odd(int n) { if(n == 0) return false; else if(n == 1) return true; else return is_even(n - 1);}

jos seuraamme määrityksen is_even(4) käsittelyä, näemme, että se pomppii edestakaisin välillä is_even ja is_odd.

Binäärihaku

teimme binäärihaun iteratiivisesti, mutta voimme tehdä sen myös rekursiivisesti:

  • on kaksi perustapausta: kun löydämme kohteen, tai kun hakuavaruus pienenee arvoon 0 (mikä osoittaa, että kohdetta ei löydy).

  • rekursiivisessa tapauksessa verrataan kohteen arvoa nykyisen keskipisteen arvoon ja sitten pienennetään hakuavaruuden kokoa (etsimällä rekursiivisesti joko vasemmalta tai oikealta puolelta).

tämä näyttää

template<typename T>int binary_search(const vector<T>& data, int low = 0, int high = data.size()-1, const T& target) { if(low > high) return -1; int mid = low + (high - low) / 2; // Why did I do this? if(data.at(mid) == target) return mid; else if(data.at(mid) < target) // Search right return binary_search(data, mid+1, high, target); else if(data.at(mid) > target) // Search left return binary_search(data, low, mid-1, target);}

muita esimerkkejä: kopioiden lukumäärän laskeminen vektorissa. Kaikkien vektorityyppisten rekursioiden osalta meidän on pidettävä kirjaa ”lähtöpaikastamme” vektorilla. Tämä johtuu siitä, että emme voi tehdä itse vektoria pienemmäksi, joten meidän on laitettava siihen merkki, joka osoittaa, mistä aloitamme. Voimme tehdä tämän kahdella tavalla, parametrilla int start, tai käyttämällä iteraattoreita.

template<typename T>int count(vector<T> data, int start, T target) { if(start == data.size()) return 0; else return (data.at(start) == target) + count(data, start + 1, target);}

iteraattoreilla:

template<typename T, typename It>int count(It start, It finish, T target) { if(start == finish) return 0; else return (*start == target) + count(start + 1, finish, target);}

iteraattorit ovat vähän kuin osoittimia.

Lajittelualgoritmit

lajittelualgoritmi on funktio, joka ottaa joukon kohteita ja somehowconstructs permutaation niistä siten, että ne on järjestetty jollakin tavalla.Yleensä, haluamme asioita, velvoitetaan mukaan normaali vertailuoperaattoreita, joten jos a < b sitten tulee ennen b lopullinen permutaatio.Silti, on olemassa muutamia asioita, meidän täytyy varmistaa, että me saada oikeus:

  • Ilmeisesti emme voi menettää kaikki elementit läpi prosessin.

  • voi olla kopioita alkuperäisestä, jos niin, ei pitäisi olla yhtä monta kaksoiskappaleet lähtö.

  • mukavuussyistä Sallimme tyhjän sekvenssin lajittelun (joka lajiteltaessa johtaa jälleen uuteen tyhjään sekvenssiin)

lajitteluun liittyy joitakin termejä, joista on tärkeää olla tietoinen:

  • Stabiilisuus – kun tulojärjestyksessä on elementtiä, jotka vertautuvat yhtä suuriksi, mutta jotka ovat erillisiä (esim.työntekijät, joilla on identtiset nimet, mutta muuten eri ihmiset), Herää kysymys, esiintyykö ulostulojärjestyksessä samassa järjestyksessä kuin alkuperäisessä. Esim., jos työntekijä ”John Smith” #123 tuli ennen” John Smith ” #234 alkuperäisessä järjestyksessä, niin sanomme, että eräänlainen on vakaa, jos #123 on ennen #234 tulokseen.

    stabiilisuus on tärkeää, kun sekvenssiä lajitellaan useilla kriteereillä. Esim., jos lajittelemme etunimen perusteella, niin sukunimen perusteella epävakaa lajittelu ei anna meille haluamaamme tulosta: etunimimerkinnät ovat kaikki sekaisin.

  • sopeutumiskyky-jotkut tulosarjat ovat jo osittain (tai kokonaan) lajiteltuja; mukautuva lajittelualgoritmi toimii nopeammin (big-O-termein) osittain lajitelluilla tuloilla. Optimaalinen suoritusaika täysin lajitellulle syötölle on \(O(n)\), aika, joka kuluu sen varmistamiseen, että syöte on jo lajiteltu.

  • in-Place-in-place-lajittelualgoritmi on sellainen, joka ei tarvitse ylimääräistä tilaa (eli sen avaruuden monimutkaisuus on \(O(1)\)) lajitteluun. Joitakin algoritmeja ei voida käyttää paikallaan, ja on rakennettava erillinen lähtöjärjestys, joka on samankokoinen kuin tulo, kirjoittaa tulokset.

  • Online-jotkut tietokokonaisuudet ovat liian suuria mahtuakseen muistiin lainkaan. Online lajittelualgoritmi on sellainen, joka vaatii kaiken tietonsa olevan saatavilla (muistissa). Offline-lajittelualgoritmit voivat lajitella tietoja, jotka ovat osittain muistissa, osittain levyllä tai muussa ”hitaassa” tallennustilassa vaikuttamatta niiden ajalliseen monimutkaisuuteen.

valintojen lajittelu

katsoimme jo valintojen lajittelua, joten katsotaan uudestaan:

  • jos haluat valita Lajittele luettelo kohteista, löydämme ensin pienin kohde koko luettelosta, ja laita se alussa.

  • sitten löydämme pienimmän kohteen kaikesta ensimmäisen kohteen jälkeen ja laitamme sen toiseksi.

  • jatka, kunnes mitään ei ole jäljellä.

tehokkaasti, valinta lajittelu jakaa luettelon lajiteltuun alueeseen alussa ja lajittelemattomaan alueeseen lopussa. Lajiteltu alue kasvaa, kun taas lajittelematon alue kutistuu.

Valintalaji ei ole vakaa.

iteratiivisesti tämä näyttää tältä:

template<typename T>void selection_sort(vector<T> data) { for(auto it = begin(data); it != end(data)-1; ++it) { // Find smallest auto smallest = it; for(auto jt = it+1; jt != end(data); ++jt) if(*jt < *smallest) smallest = jt; // Swap it into place swap(it, smallest); }}

jäljitetään tämän läpi pieni esimerkki saada tuntumaa, miten se toimii.

miten voimme toteuttaa tämän rekursiivisesti? Sen sijaan, että kiertäisimme varsinaisenvector, kierrämme vain iteraattorit vektorin alku-ja loppupäähän. Miksi teemme näin, selviää pian:

template<typename Iterator>void selection_sort(Iterator first, Iterator last) { ...}

analysoidaan rekursio:

  • perustapaus on, kun last == first + 1. Se tarkoittaa, että on vain 1 elementti, ja 1-Elementti luettelo on aina lajiteltu.

  • rekursiivinen tapaus on, kun last - first > 1. Tällöin hajotamme sen rekursiivisesti siten, että

    • löytää alueen minimin ja sijoittaa sen alkuun.
    • rekursiivisesti valinta-lajittelu first+1 kautta last (koska alkio first on nyt oikeassa paikassa).
template<typename Iterator>void selection_sort(Iterator first, Iterator last) { if(last - first == 1) return; // 1 element, nothing to sort else { // Find minimum Iterator smallest = first; for(Iterator it = first; it != last; ++it) if(*it < *smallest) smallest = it; // Swap into place swap(*smallest, *first); // Recursively sort the remainder selection_sort(first + 1, last); }}

piirretään rekursiopuu tälle. Emme jäljitä silmukan läpi, me ’ ll vain olettaa (toistaiseksi), että se toimii oikein.

kaavio

Lajittelualgoritmin analyysi

sen lisäksi, että analysoidaan lajittelualgoritmin yleistä best/worst-case big-O-ajonaikaa, on tavallista analysoida myös kahta muuta ajonaikaominaisuutta:

  • elementtien välisten vertailujen määrä. Tämä laskee vain lajiteltavien kohteiden vertailuja, ei (esim.) silmukkalaskurimuuttujan vertailua.

  • erien välisten swapien lukumäärä.

vertailujen ja vaihtojen määrän analysointi on hyödyllistä, koska nämä operaatiot ovat kaikkien lajittelualgoritmien ytimessä: emme voi tietää, ovatko elementit epäkunnossa ennen kuin vertaamme niitä (ja jos elementit ovat monimutkaisia, niiden vertaaminen voi kestää Ei-triviaalin ajan), emmekä voi laittaa niitä oikeaan järjestykseen liikuttamatta niitä – ts.vaihtamalla niitä.

Bubble sort

Bubble sort on lajittelualgoritmi, joka ei varsinaisesti sovellu rekursiiviseen toteutukseen. Ideana on vertailla syötteen vierekkäisiä elementtejä (esim., a ja a) ja vaihtaa ne, jos ne ovat epäkunnossa. Aloitamme syötön alusta ja kävelemme sen läpi vaihtaen tiemme loppuun. Yhden tällaisen läpimenon jälkeen suurin elementti on ”kuplinut” joukon viimeiseen elementtiin asti. Sitten voimme tehdä toisen ohituksen, mutta ohitamme viimeisen elementin tällä kertaa. Siinä missä selction sort teki pienempiä ja pienempiä kulkee alkaen edestä, bubble sort tekee pienempiä ja pieniäpasseja päästä.

Kuplalaji on vakaa.

toteutus näyttää jokseenkin tältä:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) swap(data.at(i), data.at(i + 1));}

toteutettuna tämä funktio on järjestyksessä \(O (n^2)\) sekä parhaissa että pahimmissa tapauksissa; sisäkkäinen silmukka, jossa on sama ”kolmiomainen” rakenne, jonka näimme aiemmin.Voimme itse asiassa toteuttaa yksinkertaisen optimoinnin: jos sisäsilmukassa ei suoriteta vaihtoja, tulo lajitellaan, ja voimme lopettaa. Jos tarkistamme tämän, voimme poistua etuajassa.

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); sorted = false; } if(sorted) return; }}

mitkä ovat parhaat ja pahimmat tapaukset?

  • paras tapaus on, kun panos on jo lajiteltu. Tässä tapauksessa, teemme yhden läpi vektorin (tarkistaa, onko se lajiteltu), mutta älä vaihda mitään, ja sitten palaamme. Joten parhaassa tapauksessa ajonaikatehokkuus on \(O (n)\).

  • pahin tapaus on array, joka on lajiteltu laskevassa järjestyksessä. Jokaisen elementin on ”kuplittava” koko matka oikeaan paikkaansa, joten emme koskaan poistu ajoissa (johtuen sorted: stä) ja if: n lausuman ehto on joka kerta tosi, joten teemme niin monta swapia kuin on tarpeen. Jos selvitämme summan, saamme

    $ $ \sum_{j = 1}^n (n – j) = n – \sum_{j = 1}^n j$$

    missä toinen summa laajenee \(\frac{n (n+1)}{2}\), antaa meille järjestyksen \(O (n)\).

kuplan lajittelun oikeellisuus

jos haluamme todistaa kuplan lajittelun oikeellisuuden, kuten tavallista, se kaikki tulee alas valitsemaan oikean invariantin(t). Tässä, se on hyödyllistä, jos meillä on kaksi, yksi yksi silmukka:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); // INVARIANT: every element in data to data is *smaller* // than data. sorted = false; } // INVARIANT: every element of data to data is smaller // than data, and every element of data to // data is larger than data. (That is, // data is in the right place.) if(sorted) return; }}

Insertion sort

Oletetaan, että jaetaan tulo kahteen ”osioon”, lajiteltuun ja lajittelemattomaan. Lajiteltu osio on aluksi tyhjä. Jokaisen lajittelemattoman osan elementin osalta lisäämme sen lajiteltuun osioon, sen oikeaan, lajiteltuun, asentoon. Koska tämä on array/vektori, elementin lisääminen vaatii kaikkien alkuaineiden siirtämistä sen jälkeen yhden askeleen ylöspäin. Vaikka voimme rakentaa tämän version, joka toimii” paikallaan”, yhdellä array (koska kun lajiteltu alue kasvaa 1, theunsorted alue kutistuu 1, joten kokonaiskoko on aina n), se on helpompi ymmärtää, jos kirjoitamme sen funktiona, joka siirtää elementtejä anunsorted vektori lajiteltu vektori, joka sitten palautetaan.

Insertion sort on stabiili.

template<typename T>vector<T> insertion_sort(vector<T>& data) { vector<T> sorted; for(int i = 0; i < data.size(); ++i) { T& item = data.at(i); // Find the proper place for item in sorted int pos = sorted.size(); // Defaults to the end for(int j = 0; j < sorted.size(); ++j) if(sorted.at(j) >= item) { pos = j; break; } // Insert the item at pos, by shifting everything forward // (Increases the size of sorted by 1) sorted.insert(sorted.begin() + pos, item); }}

mitkä ovat parhaat ja huonoimmat tapaukset tälle algoritmille? Sitä on hieman vaikea selvittää, koska insert: n monimutkaisuus on verrannollinen siirrettyjen alkuaineiden määrään (eli arvoon sorted.size() - pos). Siispä vaikka kannan löytämiseen tähtäävä loop voi poistua etuajassa (jo ensimmäisessä iteraatiossa), tämä on insertin kannalta huono asia, sillä se antaa ymmärtää, että pos tulee olemaan pieni ja siten insert aika huono. Toisaalta, jos sisempi silmukka kulkee loppuun asti (pos = sorted.size()), niin insert efektikyky ei ole muuta kuin push_back.

itse asiassa sisempi silmukka ja insert tasapainottavat aina toisiaan niin, että niiden välinen yhteissumma on sorted.size(). Ja sorted.size() kasvaa kertaheitolla ulomman silmukan läpi, joten jälleen kerran meillä on ”kolmiomainen” silmukka.

voimme kirjoittaa rekursiivisen version yleishyödyllisten funktioiden avulla:

  • insert asettaa elementin oikeaan paikkaan lajiteltuun alueeseen, jälleen siirtämällä kaiken ylös.

kun nämä kaksi ovat paikoillaan, rekursiivisesta toteutuksesta tulee

template<typename Iterator>void insertion_sort(Iterator start, Iterator unsorted, Iterator finish) { if(start == finish - 1) return; // One element else { // Insert first unsorted element into sorted region insert(start, unsorted, *unsorted); // Recursively sort the remainder of the unsorted region. insertion_sort(start, unsorted+1, finish); }}

Vastaa

Sähköpostiosoitettasi ei julkaista.