Shear sort: differenze tra le versioni

Versione delle 16:39, 22 nov 2013

Versione attuale delle 01:02, 27 gen 2025

(7 versioni intermedie di 5 utenti non mostrate)

Riga 1:

{{S|programmazione}}

{{Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

|datastruttura dati = [[Array]]

|timetempo = <math>\Theta(n\log n)</math>

}}

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 <math>\Theta(n\log n)</math>.

== Implementazioni ==

=== C++ ===

<syntaxhighlight lang="c++" line="1">

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;

}

}

}

}

}

</syntaxhighlight>

{{Portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]