Algorytm sortowania

Przedstawiony algorytm sortowania jest oparty na standardowym algorytmie quicksort. Różnica polega na tym, że w pierwszym kroku procesor główny losuje spośród danych wejściowych N-1 wartości (gdzie N to liczba procesorów wirtualnych, są umieszczane w tablicy limits), a następnie uruchamia procesory wirtualne o indeksach o 0 do N-1. Procesor o numerze k przepisuje następnie do swojej pamięci podręcznej wszystkie elementy x spełniające zależność (przy czym =MIN_VALUE, a =MAX_VALUE), obliczając jednocześnie liczbę elementów mniejszych od . W kolejnym kroku każdy z procesorów za pomocą zwykłego algorytmu quicksort sortuje swój fragment pamięci. Na koniec posortowany blok jest przepisywany z powrotem do pamięci globalnej.

shared data_size;                // ilość danych

shared N;                        // liczba procesorów wirtualnych

shared data[0..4194303];         // dane do posortowania

shared limits[0..32];            // pomocnicza tablica

 

local proc;                      // indeks procesora

local buffer[0..4194303];        // bufor w pamięci podręcznej

local first;                     // zmienne pomocnicze

local last;

local min;

local max;

 

// poniższa funkcja służy do przepisania danych spełniających

// odpowiednie warunki z pamięci podręcznej do bufora

function copy_to_buffer(data_size)

local pom_buffer[0..data_size];

local i;

begin

first:=0; last:=-1; 

blockread(data,pom_buffer,data_size); 

for i:=0 to data_size-1 do

if pom_buffer[i]<min then first:=first+1;

else if pom_buffer[i]<max then

begin

last:=last+1;

buffer[last]:=pom_buffer[i];

end;

end;

 

// funkcja służąca do posortowania elementów tablicy buffer

// poczynając od komórki o numerze first, a kończąc na last

// jest ona wywoływana rekurencyjnie (zwykły algorytm quicksort)

function quicksort(first,last)

local begin1;

local end1;

local divider;

local pom;

begin

if first>=last then return 0;

if last-first=1 then

if buffer[first]<=buffer[last] then return 0;

else

begin

pom:=buffer[first];

buffer[first]:=buffer[last];

buffer[last]:=pom;

end;

                                 

divider:=buffer[random(last-first+1)+first];

begin1:=first;

end1:=last;

while end1>begin1 do

if buffer[begin1]<=divider then begin1:=begin1+1;

else if buffer[end1]>divider then end1:=end1-1;

else

begin

pom:=buffer[begin1];

buffer[begin1]:=buffer[end1];

buffer[end1]:=pom;

end;

quicksort(first,begin1-1);

quicksort(end1,last);

end;

 

// funkcja sprawdzająca czy podany jako parametr element występuje

// w tablicy limits

function limits_contain(element,max)

local i;

begin

for i:=1 to max do

if limits[i]=element then return 1;

return 0;

end;

 

// funkcja służąca do ustalania granic dla danych, którymi będą

// się zajmować procesory wirtualne

function set_limits(proc)

local i;

local j;

local l;

begin

for i:=1 to proc-1 do

begin

l:=data[random(data_size)];

while limits_contain(l,i-1)=1 do l:=data[random(data_size)];

limits[i]:=l;

end;

 

for i:=1 to proc-2 do

for j:=i+1 to proc-1 do

if limits[i]>limits[j] then

begin

l:=limits[i];

limits[i]:=limits[j];

limits[j]:=l;

end;

   

limits[0]:=MIN_VALUE;

limits[proc]:=MAX_VALUE;

end;

 

// część główna programu

begin

if N<2 then

begin

blockread(data,buffer,data_size);

quicksort(0,data_size-1);

blockwrite(buffer,data,data_size);

end;

else

begin

set_limits(N);

 

for proc:=0 to N-1 pardo

begin

min:=limits[proc];

max:=limits[proc+1];

copy_to_buffer(data_size);

quicksort(0,last);

blockwrite(buffer,data[first],last+1);

end;

end;

end. Jeśli dysponujemy N procesorami wirtualnymi, to średni czas działania algorytmu dla losowych danych wynosi , gdzie M jest rozmiarem danych (pesymistyczny koszt algorytmu to ).