[TUTORIAL] C++ Generatia 2015

[MrGrj]

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 ?

Se citeste primul element

De la al doilea pana la ultimul element se executa*

Se citeste un nou element

Cat timp valoarea este mai mica decat cea din fata si n-am ajuns la primul element se executa

Se interschimba elementul cu cel precedent

Se deplseaza cu o pozitie spre stanga

Se reia de la * pana se termina de citit vectorul

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 ?

Rotate(first, middle, last) - aceasta functia ia un range: [first,last) si il roteste astfel incat elementul din mijloc devine primul in acel range.

upper_bound - returneaza un iterator care pointeaza catre primul element din range-ul [first, last). In momentul de fata tande-ul nostru este teoretic sortat (sau cel putin partitionat)

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 ?

Functia poz rezolva o portiune din vector cuprinsa intre indicii p si u.

piv=v[p] este un reper.

La sfarsitul executiei acestei functii, piv se va gasi pe o pozitie k cuprinsa intre p si u astfel incat toate componentele vectorului cuprinse intre p si k-1 vor fi mai mici decat piv, iar componentele cuprinse

intre k+1 si u vor fi mai mari decat piv.

Deci piv se va gasi pe pozitia k corespunzatoare ordinii in vector.

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

[Ganav]

Interesant. Ai putea explora si alte implementari:

"C" Source Code for Sort Algorithms