Recursie – en sorteeralgoritmen

ik ga vrijwel alle sorteeralgoritmen recursief presenteren, dus we moeten het waarschijnlijk over recursie hebben. Recursie is echt een geestverruimende techniek, als je het eenmaal onder de knie hebt. Het is ook de basis voor wat de “wiskundige interpretatie” van computerprogrammering zou kunnen worden genoemd, dus als je CSci major bent, zul je er vroeg of laat mee vertrouwd moeten raken. Dus laten we eens kijken naar een aantal eenvoudige algoritmen, zowel de iteratief (met behulp van lussen) en recursief.

het vinden van de faculteit

de faculteit van n wordt gedefinieerd als het product \(n (N-1) (n-2) \ldots (2) (1)\),dat wil zeggen het product van alle gehele getallen tot en met n. :

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

om dit of een ander algoritme recursief te schrijven, moeten we twee vragen stellen:

  • Wat is de kleinste zaak, de zaak waarin ik meteen het antwoord kan geven? Dit wordt de “base case”genoemd. (Soms kan er meer dan een kleinste geval, en dat is OK.)

  • voor alles wat niet het kleinste geval is, hoe kan ik het opsplitsen om het kleiner te maken? Dit wordt de recursieve case genoemd.

voor de faculteit is het basisscenario wat er gebeurt als \(n = 0\): de loop draait helemaal niet, en 1 wordt teruggegeven. Zodat we onze recursieve versie kunnen beginnen met

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

om de recursieve case te construeren, moeten we kijken naar wat er gebeurt als n > 0. In het bijzonder, hoe kunnen we \(n!\ ) naar beneden in sommige \(n’!, n ‘ < n\)?Het meest voorkomende geval is \(n ‘ = n-1\).

een manier om dit te bekijken is om aan te nemen dat we al de waarde \((n-1)!\ ), en we willen \(n!\) daaruit. Dat wil zeggen, neem aan datfactorial_rec(n - 1) werkt en ons het juiste antwoord geeft; We hoeven alleen maar de faculteit van n daaruit te construeren. Hoe kunnen we dit doen?\(n! = n (n-1)!\). Dus schrijven we onze recursieve case als volgt:

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

laten we even de tijd nemen om het computerproces te doorlopen factorial_rec(3):

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

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

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

  • fact(0) = 1 en op dit punt kunnen we een back-up maken met het resultaat 3 * 2 * 1 * 1 = 6.

inductief bewijs

Hoe laten we zien dat een functie doet wat hij zou moeten doen? We kunnen het testen,het duizenden of miljoenen keren draaien en controleren of de output is wat we verwachten, maar dit vereist dat we een onafhankelijke manier bedenken om te bepalen wat de functie doet (bijv., een andere manier van berekenen van de faculteit), die zelf onjuist zou kunnen zijn, en bovendien, herhaalde testen kan alleen maar geven ons een statistisch vertrouwen dat ons algoritme correct is. Als we willen besure, dan hebben we een logisch, of mathematisch bewijs dat het correct is nodig. Voor wisselende functies neemt dit vaak de vorm aan van bewijs door inductie. Een inductief bewijs is het wiskundige equivalent van een recursieve functie.Net als een recursieve functie heeft het base case(s) (een base case, in feite, voor elk base case in de functie), en de base cases zijn meestal eenvoudig. Het heeft ook inductieve case (s) (één voor elke recursieve case in de functie), die wat lastiger zijn, maar ons in staat stellen om iets als recursie te doen.

Bekijk het voorbeeld hierboven. We willen bewijzen dat fact(n) =\(n!\ ), waarbij de definitie van \(n! = n(n-1) (n-2)\ldots (2) (1), 0! = 1\).

bewijs door inductie op n (op welke variabele we de recursie ook doen, we zeggen dat we “bewijs door inductie” doen op die variabele):

  • basisgeval, \(n = 0\) dan fact(0) = 1 =\(0!\) en we zijn klaar.

  • inductief geval: In het inductieve geval proberen we te bewijzen dat fact(n) =\(n!\ ) ‘voor sommige \(n > 0\). We kunnen de linker-en rechterkant opsplitsen en zien dat we eigenlijk

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

    delen door \(n\) krijgen we

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

    met andere woorden, we hebben het probleem van het bewijzen dat fact(n) =\(n!\ ) om het probleem aan te tonen dat fact(n-1) =\((n-1)!\). Dat lijkt niet nuttig, maar zoals in een recursieve functie, waar we de functie zelf kunnen noemen met een kleiner argument, kunnen we in een inductief bewijs het bewijs zelf hergebruiken als aanname, voor een kleinere \(n\). We noemen deze aanname de inductieve hypothese en het ziet er zo uit:

    $$\tekst{veronderstel}\qquad \ mathtt{feit} (n’) = n’! \qquad \text{for all}\; n ‘< n$$

    als we \(n’ = N-1\) Laten dan hebben we

    $$\text{veronderstel}\qquad\mathtt{feit}(N-1) = (n-1)!$$

    dat is precies wat we hierboven nodig hadden! Door het bovenstaande te vervangen krijgen we

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

    en we zijn klaar.

net als recursie is het hart van een inductief bewijs de handeling van het toepassen van het bewijs zelf als een aanname over “kleinere” waarden (\(n’ < n\)). Technisch gezien zijn er twee soorten inductieve bewijzen:

  • “natuurlijk getal inductie” laat ons alleen de veronderstelling maken over \(n’ = n-1\). Dat wil zeggen, we kunnen alleen de veronderstelling maken over een “input” die kleiner is dan het origineel.

  • “sterke inductie” laat ons elke \(n’ < n\) gebruiken. U kunt gebruik maken van sterke inductie overal waar u natuurlijke nummer inductie kunt gebruiken, maar het is niet altijd vereist.

de integer exponent berekening

Weet je nog toen we de runtime complexiteit van onze “geoptimaliseerde” \(o(\log n)\) functie voor het vinden van een \(b^n\) hebben uitgewerkt? Daar kunnen we ook een recursieve versie van schrijven. Nogmaals, we moeten vragen

  • Wat is het basisgeval? In dit geval is het wanneer \(n = 0\). In dat geval, \(b^0 = 1\), maakt niet uit wat f is (er is enige discussie over \(0^0\)).

  • Wat is het recursieve geval? Hoe splitsen we \(b^n\) op in \(b^{n’}\)? Hier nemen we onze wachtrij van onze eerdere implementatie:

    $$b^n =(b^{n/2})^2 \quad\text{als } N \ text{ even is}$$
    $$b^n = b \cdot b^{n-1} \ quad \ text{als } n \ text{ oneven is}$$

dit geeft ons de volgende definitie:

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);}

dit heeft dezelfde complexiteit als de lus-gebaseerde versie, en is misschien eenvoudiger.

in dit geval, als we willen bewijzen dat \(\mathtt{powi}(b,n) = b^n\) we een sterke inductie nodig hebben, omdat een van de recursieve gevallen de input krimpt door iets anders dan alleen -1.

bewijs dat \(\mathtt{powi} (b, n) = b^n\) door sterke inductie op \(n\):

  • basisgeval: \(n = 0\)

    door dan naar het programma te kijken krijgen we \(\mathtt{powi} (n, 0) = 1 = b^0\) en zijn we klaar.

  • inductief geval: \(n > 0\), bewijs \(\mathtt{powi}(b, n) = b^n\). Hier zijn er eigenlijk twee inductieve gevallen, een elk voor de twee recursieve gevallen in de functie. Onze inductieve hypothese (aanname) is

    $$ \ mathtt{powi} (b,n’) = b^{n’}\qquad \ text{for all}\; n ‘ < n$$
    • geval 1, \(n\) is even. Dan vervangen van de aanroep naar powi door zijn retourwaarde hebben we

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

      het nemen van de vierkantswortel van beide zijden:

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

      op dat moment kunnen we de IH toepassen, met \(n ‘ = n / 2\), Wat

      $$b^{n / 2} = b^{n/2}$$
    • geval 2, \(n\) is oneven. Daarna uit te breiden powi we krijgen

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

    En het bewijs is voltooid

Wederzijdse recursie

Wederzijdse recursie als we definiëren een aantal recursieve functies in termen ofeach andere. Denk bijvoorbeeld aan de volgende definitie van even en oneven:

  • een natuurlijk getal n is even iff \(n-1\) is oneven.

  • een natuurlijk getal n is oneven iff \(n-1\) is even.

  • \(1\) is oneven, \(0\) is even. (Dit zijn onze basisgevallen.)

we kunnen dan twee functies (predicaten) definiëren die recursief naar elkaar verwijzen:

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);}

als we de verwerking van het bepalen van is_even(4) volgen, zullen we zien dat het heen en weer stuitert tussen is_even en is_odd.

binair zoeken

we deden een binair zoeken iteratief, maar we kunnen het ook recursief doen:

  • er zijn twee basisgevallen: wanneer we het item vinden, of wanneer de zoekruimte is gereduceerd tot 0 (wat aangeeft dat het item niet is gevonden).

  • de recursieve case vergelijkt de waarde van het doel met de waarde op het huidige middelpunt en vermindert vervolgens de grootte van de zoekruimte (door recursief te zoeken naar de linker-of rechterkant).

dit ziet eruit als

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);}

andere voorbeelden: Het tellen van het aantal kopieën in een vector. Voor elke vector-stijl recursie, moeten we bijhouden van onze “startplaats” binnen de vector. Dit komt omdat we de vector zelf niet kleiner kunnen maken, dus moeten we er een markering in zetten die aangeeft waar we beginnen. We kunnen dit op twee manieren doen, met een int start parameter, of met behulp van iterators.

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);}

met iterators:

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);}

Iterators zijn een soort van aanwijzers.

sorteeralgoritmen

een sorteeralgoritme is een functie die een opeenvolging van items neemt en waarvan sommigen een permutatie construeren, zodat ze op een of andere manier geordend zijn.Meestal willen we dat dingen geordend worden volgens de normale vergelijkingsoperatoren, zodat als a < b a Voor b komt in de uiteindelijke permutatie.Toch zijn er een paar dingen die we moeten doen.:

  • natuurlijk kunnen we geen elementen verliezen door het proces.

  • er kunnen duplicaten in het origineel zijn, als dat zo is, moet er een gelijk aantal duplicaten in de uitvoer zijn.

  • Voor uw gemak, we laten het sorteren van een lege reeks (die, wanneer gesorteerd, resulteert in nog een andere lege reeks)

Er zijn een aantal termen die te maken hebben met het sorteren van dat het belangrijk is om bewust te zijn van:

  • Stabiliteit – als de input sequentie element vergelijken gelijk, maar die zijn te onderscheiden (bijvoorbeeld, werknemers met identieke namen, maar anders andere mensen) de vraag of, in de output reeks, ze komen in dezelfde volgorde als in het origineel. Bijv., als werknemer “John Smith” # 123 voor “John Smith” #234 in de oorspronkelijke volgorde kwam, dan zeggen we dat een soort stabiel is als #123 voor #234 in het resultaat staat.

    stabiliteit is belangrijk bij het sorteren van een reeks op meerdere criteria. Bijvoorbeeld, als we Sorteren op basis van voornaam, dan op basis van achternaam, een onstabiele soort geeft ons niet het resultaat dat we willen: de voornaam items worden allemaal door elkaar gehaald.

  • aanpassingsvermogen-sommige invoerreeksen zijn al gedeeltelijk (of volledig) gesorteerd; een aanpasbaar sorteeralgoritme zal sneller draaien (in big – O termen) op gedeeltelijk gesorteerde ingangen. De optimale runtime voor een volledig gesorteerde invoer is \(O (n)\), de tijd die nodig is om te controleren of de invoer al gesorteerd is.

  • In-Place-een in-place sorteeralgoritme is een algoritme dat geen extra ruimte nodig heeft(dat wil zeggen, de complexiteit van de ruimte is \(O(1)\)) om te sorteren. Sommige algoritmen kunnen niet op hun plaats worden gebruikt, en moeten een aparte Uitvoerreeks van dezelfde grootte als de invoer construeren, om de resultaten in te schrijven.

  • Online-sommige datasets zijn te groot om in het geheugen te passen. Een online sorteeralgoritme is een algoritme dat vereist dat alle gegevens toegankelijk zijn (in het geheugen). Offline sorteeralgoritmen kunnen gegevens sorteren die gedeeltelijk in het geheugen, gedeeltelijk op schijf of andere “langzame” opslag zijn, zonder hun tijdscomplexiteit te beïnvloeden.

selectie Sorteren

we hebben al gekeken naar selectie Sorteren, dus laten we er nog eens naar kijken:

  • om een lijst met items te selecteren, zoeken we eerst het kleinste item in de hele lijst en zetten we het aan het begin.

  • dan vinden we het kleinste item in alles na het eerste item, en zetten het tweede.

  • Ga door tot er niets ongesorteerd is.

effectief, selection sort splitst de lijst in de gesorteerde regio aan het begin en de ongesorteerde regio aan het einde. De gesorteerde regio groeit, terwijl de ongesorteerde regio krimpt.

selectie sorteren is niet stabiel.

iteratief ziet dit er zo uit:

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); }}

laten we dit traceren op een klein voorbeeld om een gevoel te krijgen voor hoe het werkt.

Hoe kunnen we dit recursief implementeren? In plaats van de werkelijkevector door te geven, gaan we gewoon de iteratoren doorgeven aan het begin en einde van de vector. Waarom we dit doen zal binnenkort duidelijk worden:

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

laten we de recursie analyseren:

  • het basisscenario is wanneer last == first + 1. Dat betekent dat er maar 1 element is, en een 1-element lijst is altijd gesorteerd.

  • het recursieve geval is wanneer last - first > 1. In dat geval splitsen we het recursief op met

    • om het minimum van de regio te vinden en het aan het begin te plaatsen.
    • recursief selectie-Sorteren first+1 tot last (omdat het element op first nu op de juiste plaats staat).
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); }}

laten we hier de recursieboom voor tekenen. We zullen niet traceren door de lus, we ‘ ll gewoon aannemen (voor nu) dat het correct werkt.

DIAGRAM

sorteeralgoritme-analyse

naast het analyseren van de Algemene best/worst-case big-O runtime van een sorteeralgoritme, is het gebruikelijk om ook twee andere runtime-functies te analyseren:

  • het aantal vergelijkingen tussen elementen. Dit telt alleen vergelijkingen tussen de objecten die gesorteerd worden, niet de vergelijking van (bijvoorbeeld) een lus teller variabele.

  • het aantal swaps tussen elementen.

het analyseren van het aantal vergelijkingen en swaps is nuttig omdat deze bewerkingen de kern vormen van elk sorteeralgoritme: we kunnen niet weten of de elementen niet in orde zijn totdat we ze vergelijken (en als de elementen complex zijn, kan het vergelijken ervan een niet-triviale hoeveelheid tijd in beslag nemen), en we kunnen ze niet in de juiste volgorde zetten zonder ze te verplaatsen – dat wil zeggen, ze ruilen.

Bubble sort

Bubble sort is een sorteeralgoritme dat niet echt geschikt is voor recursieve implementatie. Het idee is om aangrenzende elementen in de invoer te vergelijken (bijv., a en a) en deze omwisselen als ze niet in orde zijn. We beginnen bij het begin van de input en lopen er doorheen, en wisselen onze weg naar het einde. Na een dergelijke pas, zal het grootste element hebben “borrelde” tot het laatste element van de array. Dus dan kunnen we nog een keer, maar we slaan het laatste element deze keer over. Terwijl selction sort kleinere en kleinere passes vanaf de voorkant gemaakt, bubble sort maakt kleinere en smallerpasses vanaf het einde.

Bubble-sortering is stabiel.

een implementatie ziet er ongeveer zo uit:

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));}

zoals geïmplementeerd, is deze functie van orde \(O(n^2)\) in zowel de beste als slechtste gevallen; geneste lus, met dezelfde “driehoekige” structuur die we eerder zagen.We kunnen eigenlijk een eenvoudige optimalisatie implementeren: in de binnenste lus, als we geen swaps uitvoeren, dan wordt de invoer gesorteerd, en kunnen we stoppen. Als we dit controleren, kunnen we misschien eerder vertrekken.

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; }}

Wat zijn de beste en slechtste gevallen?

  • het beste geval is wanneer de invoer al gesorteerd is. In dit geval laten we er één door de vector gaan (om te controleren of het gesorteerd is) maar wisselen niets, en dan keren we terug. Dus het beste geval runtime efficiency is \(O (n)\).

  • het slechtste geval is een array die gesorteerd is in aflopende volgorde. Elk element moet de volledige Afstand tot zijn juiste plaats” bubbelen”, dus we zullen nooit eerder stoppen (vanwege sorted) en de conditie in het if statement zal elke keer waar zijn, dus we zullen zoveel swaps uitvoeren als nodig is. Als we de som berekenen, krijgen we

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

    waar de tweede Som expandeert naar \(\frac{n(n+1)}{2}\), geeft ons een volgorde van \(O (n)\).

correctheid van bubble sort

als we de juistheid van bubble sort willen bewijzen, zoals gewoonlijk, komt het allemaal neer op het kiezen van de juiste invariant(s). Hier is het handig als we er twee hebben, één van elke lus:

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

stel dat we de invoer splitsen in twee “secties”, gesorteerd en ongesorteerd. Het gesorteerde gedeelte is in eerste instantie leeg. Voor elk element in de ongesorteerde sectie, voegen we het in de gesorteerde sectie, in de juiste, gesorteerde, positie. Omdat dit een array/vector is, vereist het invoegen van een element het verschuiven van alle elementen nadat het één stap hoger is. Hoewel we een versie hiervan kunnen bouwen die”op zijn plaats” werkt, op een enkele array (want als het gesorteerde gebied met 1 groeit, krimpt het niet-gesorteerde gebied met 1, zodat de totale grootte altijd n is), zal het makkelijker zijn om het te begrijpen als we het schrijven als een functie die elementen verplaatst van een niet-gesorteerde vector naar een gesorteerde vector, die dan wordt geretourneerd.

invoegtoepassing is stabiel.

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); }}

Wat zijn de beste en slechtste gevallen voor dit algoritme? Het is een beetje lastig om dit uit te zoeken omdat de complexiteit van de insert evenredig is met het aantal verplaatste elementen (dat wil zeggen tot sorted.size() - pos). Dus hoewel de zoektocht naar de positie vroeg kan stoppen (zelfs in de eerste iteratie), is dit slecht voor de insert, omdat het impliceert dat pos klein zal zijn en dus de tijd van insert vrij slecht. Aan de andere kant, als de binnenste lus helemaal tot het einde loopt (pos = sorted.size()) dan is de insert effectief niet meer dan een push_back.

in feite zijn de binnenste lus en de insert altijd met elkaar in evenwicht, zodat het totaal ertussen sorted.size()is. En sorted.size() neemt elke keer met één toe door de buitenste lus, dus hebben we weer onze “driehoekige” lus.

we kunnen een recursieve versie schrijven met behulp van een hulpprogramma functies:

  • insert plaatst een element op de juiste plaats in de gesorteerde Regio, opnieuw door alles omhoog te schuiven.

met deze twee in plaats, de recursieve implementatie wordt

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); }}

Geef een antwoord

Het e-mailadres wordt niet gepubliceerd.