POLITECHNIKA OPOLSKA

Programowanie współbieżne i rozproszone

Kierunek studiów:	Informatyka studia II-go stopnia	Rok studiów:	I
Rok akademicki:	2014 / 2015	Semestr:	I

Temat:
Ćwiczenie 1: Sortowanie bąbelkowe

Lp.	Imię	Nazwisko	Sprawozdanie oddano dnia:	Ocena:
1.	Adam	Czech	09.06.2015

Termin zajęć:		Prowadzący:
dzień:	Wtorek	^dr hab. inż. J. Sadecki Prof. PO
godzina:	17:50
grupa:	L1

1. Cel ćwiczenia

Ćwiczenie ma na celu przedstawienie przyśpieszenia sortowania przy użyciu wielowątkowości, czyli zwiększenia szybkości sortowania w przypadku tego ćwiczenia będzie to sortowanie bąbelkowe.

2. Wstęp teoretyczny

Sortowanie bąbelkowe (ang. bubble sort) - jest to prosta metoda sortowania. Złożoność czasowa sortowania bąbelkowego to 0(n²), zaś złożoność pamięciowa to 0(1). Polega ono na porównywaniu dwóch kolejnych elementów i zamianie ich miejscami, jeżeli zaburzają one porządek w jakim jest sortowana tablica. Sortowanie kończy zadanie jeżeli po przejściu kolejny raz przez tablicę nie dokonana zostanie żadna zmiana.

Rysunek 1 Schemat działania sortowania bąbelkowego.

3. Fragment kodu programu

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);

4. Tablica wynikowa

Liczba wątków	Czas [s]
Sekwencyjnie	105,55
1	58,72
2	31,25
3	20,38
4	17,12

5. Wykresy

1. Zależność czasu od ilości wątków

2. Wzrost przyśpieszenia dzięki dodaniu kolejnych wątków (wartość przedstawiona procentowo).

6. Wnioski

Program został wykonany poprawnie czego dowodem jest tablica wynikowa. Jak można się było tego spodziewać wzrost liczby wątków przyśpieszyło działanie sortowania bąbelkowego. Podsumowując można z całą pewnością stwierdzić, iż wielowątkowość podczas pracy z programem sortującym bąbelkowa znacznie przyśpiesza jego pracę i skraca nasz czas do potrzebnego minimum. Sądzę, że cel ćwiczenia został osiągnięty.

WYDZIAŁ ELEKTROTECHNIKI, AUTOMATYKI I INFORMATYKI

1

Opole 2015

---