Ma tin de ceva timp sa fac tutorialul asta si uite ca abia acum reusesc sa il postez. In ultima vreme am observat ca exista o tranzitie destul de confuza intre metoda moderna de a scrie cod (folosind librarii noi, fiecare fiind specifica unui anumit algoritm) si cea clasica. Voi incerca sa expun mai jos cateva metode de a implementa algoritmi cunoscuti si folositori folosind "Metoda moderna". Precizez ca nu am apucat sa testez complexitatea si nici timpul de executie al fiecarei instructiuni in parte, insa daca e cineva dispus sa faca un benchmarking, go for it. Sortarea prin insertie ( Insert sort ) Cum arata codul acestei functii utilizand metoda clasica: #include <iostream.h> int main() { int v[100],n,i,j,aux; cout<<"n= ";cin>>n; cout<<"v[1]= ";cin>>v[1]; for(i=2;i<=n;i++) { cout<<"v["<<i<<"]= "; cin>>v[i]; j=i; while(v[j]<v[j-1] && j>1) { aux=v[j]; v[j]=v[j-1]; v[j-1]=aux; j--; } } cout<<"Vectorul sortat este: "; for(i=1;i<=n;i++) cout<<v[i]<<" "; return 0; } Cum functioneaza algoritmul de mai sus ? Cum putem face acest algoritm mai accesibil folosind doar doua linii de cod? for (auto i = start; i != end; ++i) std::rotate(std::upper_bound(start, i, *i), i, std::next(i)); Cum functioneaza algoritmul de mai sus ? std::upper_bound(start, i, *i) returneaza pozitia primului element mai mare decat *i. Astfel, range-ul este shiftat asa incat al i-ilea termen va deveni primul. Aveti mai jos o poza care detaliaza procesul: Quick sort Cum arata codul acestei functii utilizand metoda clasica: #include <iostream.h> #include <conio.h> #include<stdlib.h> int x[2000]; int n; int poz(int p,int u) {int piv,aux,k; piv=x[p]; while (p<u) { if (x[p]>x[u]) {aux=x[p]; x[p]=x[u]; x[u]=aux; } if (x[p]==piv) u--; else p++; } k=p; return k; } void quick(int p,int u) {int k; if (p<u) {k=poz(p,u); quick(p,k-1); quick(k+1,u);} } void main() {clrscr(); cout<<"n="; cin>>n; for(int i=1;i<=n;i++) {cout<<"x["<<i<<"]="; cin>>x[i]; } quick(1,n); for(i=1;i<=n;i++) cout<<x[i]<<' '; getch(); } Cum functioneaza algoritmul de mai sus ? Cum putem face asta mai usor ? template<class FwdIt, class Compare = std::less<>> void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare{}) { auto const N = std::distance(first, last); if (N <= 1) return; auto const pivot = std::next(first, N / 2); std::nth_element(first, pivot, last, cmp); quickSort(first, pivot, cmp); quickSort(pivot, last, cmp); } In implementarea de mai sus std::nth_element face aproape toata treaba: - sorteaza partial range-ul astfel incat al n-lea element dat este plasat intr-o pozitie convenabila. - toate elementele de dinaintea celui de-al n-lea termen sunt mai mici sau egale decat elementele de dupa acesta. Slide Aici voi explica metoda care mi se pare cea mai usoara folosind una din functiile de mai sus: template <typename It> auto slide(It f, It l, randIter p) -> std::pair<It, It> { if (p < f) return { p, std::rotate(p, f, l) }; if (l < p) return { std::rotate(f, l, p), p }; return { f, l }; } Cum functioneaza ? Ca exemplu, va puteti imagina o lista de itemi intr-un dialog UI. Userul selecteaza un range continuu, iar apoi algoritmul ia acest range si il muta intr-un alt loc din lista: Functia de mai sus: - foloseste std::rotate ( pe care sper ca ati inteles-o deja ) -> muta elementele in fata si in spate - returneaza doi iteratori - inceputul si sfarsitul noii secvente. Sper sa va ajute cele de mai sus si sper sa intelegeti macar o parte din ce am incercat sa expun mai sus. Cheers
Nu mai venea o data si partea asta... Saru'mana