Shear sort

Shear sort
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	$\Theta (n\log n)$

Lo Shear sort è un algoritmo di ordinamento molto semplice per ordinare vettori a due dimensioni; questo algoritmo ordina a turno le righe e le colonne del vettore. Ha una complessità in tempo di $\Theta (n\log n)$.

Implementazioni

C++

void shear_sort(int v[][], int n, int m) {
    bool scambio = true;
    while (scambio) {
        scambio = false;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                for (int j = 0; j < m - 1; j++) {
                    if (v[i][j] > v[i][j + 1]) {
                        swap(v[i][j], v[i][j + 1]);
                        scambio = true;
                    }
                }
            } else if (i % 2 != 0) {
                for (int j = m - 1; j > 0; j--) {
                    if (v[i][j] > v[i][j - 1]) {
                        swap(v[i][j], v[i][j - 1]);
                        scambio = true;
                    }
                }
            }
        }
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n - 1; i++) {
                if (v[i][j] > v[i + 1][j]) {
                    swap(v[i][j], v[i + 1][j]);
                    scambio = true;
                }
            }
        }
    }
}