Shear sort
Un alt exemplu de algoritm de sortare care a fost conceput pentru sisteme multi-procesor unde un procesor este conectat doar la o parte din celelalte procesoare este shear sort (cunoscut de asemenea ca row-column sort sau snake-order sort), care presupune că lucrăm pe procesoare conectate într-o formă de matrice. Astfel, un procesor poate să comunice cu vecinii din stânga, din dreapta, de sus și de jos. Dacă ne imaginăm deci că procesoarele sunt așezate într-o matrice, cele două faze ale algoritmului shear sort sunt următoarele:
- se sortează liniile matricei astfel încât randurile pare au valorile ordonate crescător, iar rândurile impare au valorile ordonate descrescător
- se sortează coloanele crescător.
Se garantează că algoritmul va sorta numerele după cel mult sup(log2N) + 1 faze, unde N este numărul de elemente ce trebuie sortate. Din acest motiv, algoritmul are complexitatea O(Nlog2N). Pseudocodul algoritmului este prezentat mai jos.
function shearSort(matrix) {
for (k = 0; k < ceil(log2(matrix.lines * matrix.columns)) + 1; k++) {
for (i = 0; i < matrix.lines; i++) {
if (i % 2 == 0)
sortAscendingLine(i);
else
sortDescendingLine(i);
}
for (i = 0; i < matrix.columns; i++) {
sortAscendingColumn(i);
}
}
}
O reprezentare grafică a funcționării shear sort este prezentată în figura de mai jos.
La finalul rulării algoritmului, lista de numere va fi sortată într-un mod "șerpuit", de unde și numele algoritmului. Acest lucru se poate observa în imaginea de mai jos.
