Algoritmi de sortare a unui vector in C++

Ce este sortarea?

In informatica, “a sorta” inseamna a rearanja elementele dintr-o structura de date in ordine crescatoare (sau descrescatoare). De exemplu, daca avem vectorul

Dupa ce vom rearanja elementele vom obtine

Sortarea este o operatie fundamentala in informatica.

• Putem sorta datele pentru prezentarea catre utilizator (de exemplu in agenda telefonica, sau atunci cand navigam printre foldere, sau selectam o anumita melodie din telefon)
• Sortarea este o piatra fundamentala in algoritmii mai mari, pentru ca simplifica anumite cerinte (precum gasirea unei chei unice, sau detectarea elementelor duplicate)

Putem sorta orice, numere, texte, orice care are un criteriu de sortare. Dar pentru usurinta vom folosii numere in toate exemplele noastre. Aveti grija sa distingeti pozitia elementului (i) de elementul efectiv ( V[i] )

Evaluarea algoritmilor de sortare

• Cat de mult spatiu necesita algoritmul, in afara de spatiul efectiv pe care il ocupa vector? In cel mai bun caz acel spatiu este O(1), dar exista si algoritmi care au nevoie de spatiu extra pentru a sorta mai eficient (d.p.d.v. al timpului). Acest procedeu se numeste “trading space for time” – ne vom mai intalnii cu el.
• Cat de repede se executa sortarea? Ar trebuii sa numaram de cate ori se compara doua numere si sa luam in considerare atat cazul mediu (average case) cat si cazul cel mai nefavorabil (worst case)
• Ce se intampla daca exista elemente care se repeta?

1. Selection sort (sau sortarea prin interschimbare)

Ideea cu acest algoritm de sortare este sa aducem cel mai mic element mereu in fata vectorului. Pentru a gasii mereu cel mai mic element ramas, trebuie sa parcurgem vectorul de mai multe ori.

#include    <iostream>

using namespace std;

void selectionSort(int Vector[], int N)
{
    for(int i = 0; i < N - 1; i++)
    {
        for(int j = i + 1; j < N; j++)
        {
            if(Vector[i] > Vector[j])
            {
                int aux = Vector[i];
                Vector[i] = Vector[j];
                Vector[j] = aux;
            }
        }
    }
}

void afisareVector(int Vector[], int N)
{
    for(int i = 0; i < N; i++)
        cout << Vector[i] << " ";
    cout << "\n";
}

int main()
{
    int V[10];
    int N;

    cout << "Lungimea vectorului este: ";
    cin >> N;

    for(int i = 0; i < N; i++)
    {
        cout << "Elementul V[" << i << "] este: ";
        cin >> V[i];
    }

    selectionSort(V, N);
    afisareVector(V, N);
    return 0;
}

Evaluarea algoritmului selection sort:

• Algoritmul de sortare prin interschimbare foloseste O(1) spatiu extra, pentru cateva variabile temporare.
• Complexitatea timpului poate fi vazuta din structurarea celor doua for-uri. Indiferent de elementele din vector, acest algoritm executa (N – 1) + (N – 2) + … + 3 + 2 + 1 comparari. Daca adunam obtinem N * (N – 1) / 2, ceea ce prescurtat inseamna O(N²).

2.  Quicksort ( sort() din #include<algorithm> )

Acest algoritm este incorporat in functia sort() din bibleoteca #include<algorithm>. Aceasta functie este foarte folositoare atat pentru programatorii incepatori, cat si pentru cei avansati. Nu trebuie sa memoram nici o linie in plus, trebuie doar sa retinem sa adaugam tot timpul bibleoteca si sa folosim functia corespunzator. Este o adevarata mana de ajutor atunci cand ne trebuie un algoritm de sortare la indemana.

#include    <algorithm>
#include    <iostream>

using namespace std;

void afisareVector(int Vector[], int N)
{
    for(int i = 0; i < N; i++)
        cout << Vector[i] << " ";
    cout << "\n";
}

int main()
{
    int V[10];
    int N;

    cout << "Lungimea vectorului este: ";
    cin >> N;

    for(int i = 0; i < N; i++)
    {
        cout << "Elementul V[" << i << "] este: ";
        cin >> V[i];
    }

    sort(V, V + N);

    afisareVector(V, N);
    return 0;
}

Linia care executa toata sortarea este sort(V, V + N);
Primul parametru este un pointer care duce catre primul element din vector. Iar cel de-al doilea parametru este tot un pointer la randul lui, care duce catre ultimul element din vector.

Evaluarea algoritmului quicksort:

• Quicksort ruleaza O(n²) – ca si complexitate in timp, in cel mai rau caz.
• Quicksort este foarte folosit in practica deoarece in cazul mediu este foarte rapid, iar cel mai rau caz este foarte rar intalnit. Complexitatea medie este O(n log n).