POLITECHNIKA OPOLSKA
Programowanie współbieżne i rozproszone
Kierunek
Informatyka studia II-go stopnia Rok studiów: I
studiów:
Rok
2014 / 2015 Semestr: I
akademicki:
Temat:
Ćwiczenie 1: Sortowanie bąbelkowe
Lp. Imię Nazwisko Sprawozdanie oddano dnia: Ocena:
1. 09.06.2015
Adam Czech
Termin zajęć: Prowadzący:
dzień: Wtorek
dr hab. inż. J. Sadecki Prof. PO
godzina: 17:50
grupa: L1
WYDZIAA
ELEKTROTECHNIKI, AUTOMATYKI I INFORMATYKI
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(n2), 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.
1
Opole 2015
WYDZIAA
ELEKTROTECHNIKI, AUTOMATYKI I INFORMATYKI
3. Fragment kodu programu
start = times(&t_start);
for (i=0;ifor (j=0;jif (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;ifor (j=0;jif (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
2
Opole 2015
WYDZIAA
ELEKTROTECHNIKI, AUTOMATYKI I INFORMATYKI
5. Wykresy
a) Zależność czasu od ilości wątków
b) 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.
3
Opole 2015