POLITECHNIKA OPOLSKA

LABORATORIUM

Przedmiot: Programowanie współbieżne i rozproszone
		Kierunek studiów: INFORMATYKA	Rok studiów: I
			Rok akademicki: 2010/2011
Temat: Sortowanie
		Wykonał: inż. Kajetan Dutkiewicz

1. Sortowanie bąbelkowe (ang. bubble sort) - prosta metoda sortowania o złożoności czasowej O(n²) i pamięciowej O(1). Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.

Sortowanie QuickSort - wynalezione przez Hoare'a. Jeden z najpopularniejszych algorytmów sortowania. Wpłynęły na to dwie rzeczy. Po pierwsze jest ono bardzo szybkie (jak sama nazwa wskazuje), a po drugie - proste do wytłumaczenia i implementacji. Pesymistyczny czas jego działania wynosi O(n²), a średni O(n*lg(n)). Mimo tego w praktyce jest to najszybszy algorytm sortowania dużych tablic danych. Sortowanie szybkie opiera się na technice "dziel i zwyciężaj". Wejściowa tablica jest dzielona (po przestawieniu niektórych z jej elementów) na dwie mniejsze. Każdy element pierwszej tablicy nie jest większy niż każdy element drugiej tablicy. Liczbę, według której wykonuje się podziału to najczęściej pierwszy element tablicy. Następnie dla tych dwóch podtablic wywoływany jest rekurencyjnie ten sam algorytm. Wywołania rekurencyjne kończą się aż któraś z kolejnych podtablic będzie zawierała tylko jeden element. QuickSort działa w miejscu.

Sortowanie przez scalanie (ang. merge sort) - rekurencyjny algorytm sortowania danych, mający zastosowanie przy danych dostępnych sekwencyjnie (po kolei, jeden element na raz), na przykład w postaci listy jednokierunkowej (tj. łączonej jednostronnie) albo pliku sekwencyjnego. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi.

2. Kod programu (fragmenty)

…

start = times(&t_start);

for (i=0;i<N;i++)

for (j=0;j<N-1;j++)

if (A[j]>A[j+1])

{

tmp = A[j];

A[j] = A[j+1];

A[j+1] = tmp;

}

end = times(&t_end);

doit("\nCzas wykonania algorytmu sortowania babelkowego sekwencyjnie:", end - start);

start = times(&t_start);

#pragma omp parallel for shared(N,A) private(i, j,tmp)num_threads(1)

for (i=0;i<N;i++)

for (j=0;j<N-1;j++)

if (A[j]>A[j+1])

{

tmp = A[j];

A[j] = A[j+1];

A[j+1] = tmp;

}

end = times(&t_end);

doit("\nCzas wykonania algorytmu sortowania babelkowego rownolegle: -1 watek", end - start);

…

…

start = times(&t_start);

quickSort(A, 0, N-1);

end = times(&t_end);

doit("\nCzas wykonania algorytmu sortowania quicksort sekwencyjnie:", end - start);

start = times(&t_start);

#pragma omp parallel num_threads(1)

quickSort(A, 0, N-1);

end = times(&t_end);

doit("\nCzas wykonania algorytmu sortowania quicksort rownolegle - 1 watek:", end - start);

…

…

start = times(&t_start);

MergeSort(0,N-1,A,C);

end = times(&t_end);

doit("\nCzas wykonania algorytmu sortowania mergersort sekwencyjnie:", end - start);

start = times(&t_start);

#pragma omp parallel num_threads(1)

MergeSort(0,N-1,A,C);

end = times(&t_end);

doit("\nCzas wykonania algorytmu sortowania mergersort rownolegle - 1 watek", end - start);

…

…

MergeSort(int i_p, int i_k,double A[], double C[])

{

int i_s,i1,i2,i;

i_s = (i_p + i_k + 1) / 2;

if(i_s - i_p > 1) MergeSort(i_p, i_s - 1,A,C);

if(i_k - i_s > 0) MergeSort(i_s, i_k,A,C);

i1 = i_p; i2 = i_s;

for(i = i_p; i <= i_k; i++)

C[i] = ((i1 == i_s) || ((i2 <= i_k) && (A[i1] > A[i2]))) ? A[i2++] : A[i1++];

for(i = i_p; i <= i_k; i++) A[i] = C[i];

}

…

…

quickSort1(double arr[], int left, int right)

{

int i = left, j = right, tmp;

int pivot = arr[(left + right) / 2];

while (i <= j) {

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};

#pragma omp parallel num_threads(1)

if (left < j)

quickSort1(arr, left, j);

#pragma omp parallel num_threads(1)

if (i < right)

quickSort1(arr, i, right);

}

…

3. Zrzut ekranowy

4. Wykresy

1) Zależność czasu obliczania od ilości wątków:

Sortowanie bąbelkowe

Sortowanie QuickSort

Sortowanie przez scalanie

2) Wzrost przyspieszenia wykonywania programu na wątkach.

Sortowanie bąbelkowe

Sortowanie QuickSort

Sortowanie przez scalanie

5. Podsumowanie

Obliczenia wykonane zostały na komputerze wyposażonym w procesor: i5 520M 2,40Ghz. Jak można było zaobserwować zastosowanie wielowątkowości przyspieszyło działanie programu w przypadku sortowania bąbelkowego. W sortowaniu QuickSort oraz MergeSort, które są najszybszymi i najbardziej wydajnymi sortowniami czasy wynosiły poniżej 1/10 sekundy, lecz przyspieszenie również było zauważalne.

---