Rank sort

Rank Sort este un algoritm de sortare a unui vector folosindu-se de rangul fiecărui element din vector. Rangul unui element presupune câte numere sunt mai mici decât el în vector.

Pași:

• Se calculează rangul fiecărui element: pentru fiecare element din vector v[i], unde 0 ⇐ i < N (N - dimensiunea vectorului), se numără câte elemente din vector v[j], j != i sunt mai mici: v[j] < v[i], 0 ⇐ i, j < N, i != j.

• Elementul de pe poziția "i" va fi pe poziția "rang" în noul vector sortat: q[rank] = v[i].

Pseudocod serial:

for i = 0 to N
    for j = 0 to N
	if v[i] > v[j]
		rank[i]++

for i = 0 to N
    results[rank[i]] = v[i]

Algoritmul "Parallel rank sort" are ca scop paralelizarea pasului 1. Rangul fiecărui element poate fi căutat în paralel, adică fiecare proces sau fir de execuție va realiza căutarea rangurilor pentru elementele din intervalul său: [start, end).

Complexitatea temporală a algoritmului este O(n²), ceea ce face complexitatea în cazul paralelizării pasului 1 a lui să devină O(n² / p), p - numărul de procesoare / fire de execuție.

Aici aveți atașate slide-uri, care ilustrează pas cu pas: slides