Question

Sa se construiasca un algoritm care sa sorteze elementele unui vector in ordine crescatoare.
In C/C++ sau pseudocod. Multumesc anticipat!

Answer 1

┌Funcție sortare_vector(V[], întreg n)

│  ┌pentru i ← 0, n-1 execută

│  │  ┌pentru j ← i+1, n-1 execută

│  │  │  ┌dacă V[j] < V[i] atunci

│  │  │  │   aux ← V[i]

│  │  │  │   V[i] ← V[j]

│  │  │  │   V[j] ← aux

│  │  │  └■

│  │  └■

│  └■

└■

Answer 2

Răspuns:

void sort(int *v, int n){

   if(n == 1){ // Daca vectorul are un singur element este deja sortat

       return;

   }

   int np2 =  n / 2;//Impartim vectorul in 2 vectori mai mici

   sort(v, np2); // Ii sortam

   sort(v + np2, n - np2);

   //Si apoi interclasam

   {

       // Cu memorie auxiliara

       int *aux = new int[n];

       int i = 0, j = np2, k = 0;

       while(i < np2 && j < n){

           if(v[i] < v[j]){

               aux[k++] = v[i++];

           }else {

               aux[k++] = v[j++];

           }

       }

       while(i < np2)

           aux[k++] = v[i++];

       while(j < n)

           aux[k++] = v[j++];

       for(i = 0; i < k; i++)

           v[i] = aux[i];

       delete aux;

   }

}

Explicație:

Acest algoritm se numeste Merge Sort si are complexitatea $O(n log\:n)$. Poate e mai greu de inteles decat alti algoritmi ca Bubble Sort, Insertion/Selection Sort dar este mult mai eficient pe vectori foarte mari