Algoritmi di ordinamento

Problema dell’ordinamento

Input: Una sequenza $A = a_{1}, a_{2}, . . ., a_{n}$ di $n$ valori
Output: Una sequenza $B = b_{1}, b_{2}, . . ., b_{n}$ che sia una permutazione di $A$ e tale per cui $b_{1} \leq b_{2} \leq . . . \leq b_{n}$

Selection Sort

Cerco il minimo e lo metto in posizione corretta, riducendo il problema agli $n - 1$ restanti valori.
Esempio di esecuzione:

SelectionSortExecution.png|600

Implementazione in C++

void selectionSortvector<int>& array {
    int size = array.size();
    for(int i = 0; i < size; ++i) {
        int minIndex = getMin(array, i, size);
        std::swap(array[i], array[minIndex]);
    }
}

int getMinvector<int> array, int start, int end {
    int minIndex = start;
    for(int i = start + 1; i < end; ++i) {
        if(array[i] < array[minIndex])
            minIndex = i;
    }
    return minIndex;
}

Time complexity
- Caso migliore: $O (n^{2})$ (ad ogni iterazione dobbiamo scorrere per forza tutti gli elementi per trovare il minimo)
- Caso peggiore: $O (n^{2})$
Space complexity: $O (1)$

Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Implementazione in C++

void insertionSortvector<int>& array {
    int size = array.size();
    for(int i = 1; i < size; ++i) {
        int j = i;
        int temp = array[j];
        for(; (j > 0) && (temp < array[j - 1]); --j)
            array[j] = array[j - 1];
        array[j] = temp;
    }
}

Time complexity
- Caso migliore: $O (n)$ (se ogni subarray è ordinato non bisogna spostare niente)
- Caso peggiore: $O (n^{2})$ (nel caso in cui l'array sia in ordine decrescente)
Space complexity: $O (1)$

Merge Sort

Il merge sort è basato sulla tecnica divide-et-impera:

Divide: Spezza virtualmente il vettore di $n$ elementi in due sottovettori di $\frac{n}{2}$ elementi
Impera: Chiama Merge Sort ricorsivamente sui due sottovettori
Combina: Unisci (merge) le due sequenze ordinate

Idea: Si sfrutta il fatto che i due sottovettori sono già ordinati per ordinare più velocemente

Implementazione in C++

void mergeSortvector<int>& array {
    mergeSortHelper(array, 0, array.size() - 1);
}

void mergeSortHelpervector<int>& array, int first, int last {
    if(first >= last)
        return;
    /* mid is the last element of the first half of the array.
        mid+1 is the first element of the second half of the array. */
    int mid = (first + last) / 2;
    mergeSortHelper(array, first, mid);
    mergeSortHelper(array, mid + 1, last);
    merge(array, first, mid, last);
}

void mergevector<int>& array, int first, int mid, int last {
    std::vector<int> sortedArray;
    int leftSide = first;
    int rightSide = mid + 1;
    /* We have first to mid and mid+1 to last already sorted.
        We have to merge the two parts in sortedArray. */
    while(leftSide < mid + 1 && rightSide < last + 1) {
        if(array.at(leftSide) > array.at(rightSide)) {
            sortedArray.push_back(array.at(rightSide));
            ++rightSide;
        }
        else {
            sortedArray.push_back(array.at(leftSide));
            ++leftSide;
        }
    }
    /* Insert all the remaining values from i to mid into sortedArray */
    for(; leftSide < mid + 1; ++leftSide)
        sortedArray.push_back(array.at(leftSide));
    /* Insert all the remaining values from mid+1 to last into sortedArray */
    for(; rightSide < last + 1; ++rightSide) 
        sortedArray.push_back(array.at(rightSide));
    /* Assign sorted data stored in sortedArray to array */
    for(int i = first; first < last + 1; ++first)
        array.at(first) = sortedArray.at(first - i);
}

Time complexity
- Caso migliore: $O (n \log n)$ (il costo computazionale di merge() è $O (n)$ e l'array viene spezzato $\log n$ volte)
- Caso peggiore: $O (n \log n)$
Space complexity: $O (n)$ (nell'ultimo caso l'array di supporto è di $n$ elementi)

Come abbiamo ottenuto questo?

Costo computazionale di Merge Sort:

$T (n) = {\begin{cases} c & n = 1 \\ 2 T (\frac{n}{2}) + d n & n > 1 \end{cases}$

È possibile risolvere questa ricorrenza nel modo seguente:

\begin{aligned} T (n) & = 2 T (\frac{n}{2}) + d n \\ = 2 (2 T (\frac{n}{4}) + \frac{d}{2} n) + d n = 4 T (\frac{n}{4}) + d n + d n \\ = 8 T (\frac{n}{8}) + d n + d n + d n \\ = 2^{i} \cdot T (1) + \underset{\log n}{\underset{⏟}{d n + . . . + d n + d n}} \\ da cui \\ T (n) & = d n \cdot \log n + c = Θ (n \log n) \end{aligned}

Per maggiori informazioni leggere 1. Risolvere le ricorrenze.
Riassunto del merge sort:

E se dividessi l'array in più di 2 parti?

Si consideri una variante di MergeSort chiamata MergeSortK che, invece di suddividere l’array da ordinare in 2 parti, lo suddivide in $k$ parti, ri-ordina ognuna di esse applicando ricorsivamente MergeSortK, e le riunifica usando un’opportuna variante MergeK di Merge, che fonde $k$ sottoarray invece di 2.

Merge Sort dividendo l'array in 3 parti:

$T (n) = {\begin{cases} c & n = 1 \\ 3 T (\frac{n}{3}) + 3 n & n > 1 \end{cases}$
da cui

$T (n) = 3 n \log_{3} n + n = Θ (n \log n)$

Merge Sort dividendo l'array in $k$ parti:

$T (n) = {\begin{cases} c & n = 1 \\ k T (\frac{n}{k}) + k n & n > 1 \end{cases}$
da cui

$T (n) = k n \log_{k} n + n = Θ (n \log n)$

Sembra quindi che più sono le parti in cui dividiamo l'array e più efficiente diventa l'algoritmo.
Ma allora perchè quello più usato è il 2-way Merge sort? 🤔
In realtà, nonostante l'algoritmo sembri più efficiente, il numero di comparazioni da fare aumenta proporzionalmente al numero di parti in cui dividiamo l'array.
Infatti, se dividessi in $n$ parti un array da $n$ elementi:

$T (n) = {\begin{cases} c & n = 1 \\ n T (\frac{n}{n}) + n \cdot n & n > 1 \end{cases}$
da cui

$T (n) = n + n \cdot n \log_{n} n = n^{2} + n = Θ (n^{2})$

Il Merge Sort più efficiente quindi è quello che divide l'array in 2 parti.