Strona główna

Laboratoria nr 1 Sortowanie (04. 03. 2007)


Pobieranie 68.62 Kb.
Data19.06.2016
Rozmiar68.62 Kb.
Laboratoria nr 1

Sortowanie

(04.03.2007)


  1. Sortowanie bąbelkowe (BbS)

  2. Sortowanie przez wstawianie (IS)

  3. Sortowanie przez wybieranie (SS)

  4. Sortowanie przez zliczanie (CS)

  5. Sortowanie kubełkowe (BS)

  6. Sortowanie przez scalanie ciągów (MS)

  7. Sortowanie stogowe (HS)

  8. Sortowanie szybkie (QS)


Materiały

Wyróżniamy następujące sortowania:



  • Przez prostą zamianę – bąbelkowe (Bubble Sort) – BbS

Sprawdzamy całą tablicę od końca (od prawej do lewej strony). Jeżeli trafimy na parę elementów, w której większy poprzedza mniejszy to zamieniamy je miejscami i znów zaczynamy przeszukiwać tablicę od końca. Czynność powtarzamy tak długo, aż podczas sprawdzania całej tablicy, nie zajdzie ani jedna zamiana elementów. Algorytm nosi nazwę bąbelkowego, gdyż najmniejsze liczby "wypływają" z dołu tablicy na jej szczyt.

Poniżej znajduje się przykład zastosowania dla nieuporządkowanego ciągu liczb <2, 4, 1, 3>.






  • Przez proste wstawianie (Insertion Sort) – IS

Idea działania algorytmu opiera się na podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa, a liczba na prawo niemniejsza. Każdą liczbę wstawiamy w odpowiednie miejsce, tzn. po młodszej, ale przed starszą. Pierwszy element pozostaje na swoim miejscu. Następnie bierzemy drugi i sprawdzamy, w jakiej relacji jest on z pierwszym. Jeśli jest niemniejszy, to zostaje na drugim miejscu, w przeciwnym wypadku wędruje na pierwsze miejsce. Dalej sprawdzamy trzeci element (porównujemy go do dwóch pierwszych i wstawiamy w odpowiednie miejsce), czwarty (porównujemy z trzema pierwszymi), piąty, itd.

Poniżej znajduje się przykład zastosowania dla nieuporządkowanego ciągu liczb <2, 4, 1, 3>.






  • Przez proste wybieranie/wymianę (Selection Sort) – SS

Na początku szukany jest najmniejszy element. Po jego znalezieniu jest on zamieniany z pierwszym elementem tablicy. Następnie szukany jest ponownie najmniejszy element, ale począwszy od elementu drugiego (pierwszy – najmniejszy jest już wstawiony na odpowiednie miejsce). Po jego znalezieniu jest on zamieniany z drugim elementem. Czynność ta jest powtarzana kolejno na elementach od trzeciego, czwartego, itd, aż do n-tego.

Poniżej znajduje się przykład zastosowania dla nieuporządkowanego ciągu liczb <2, 4, 1, 3>.







  • Przez zliczanie (Counting Sort) – CS

Zakładamy, że każdy z n sortowanych elementów jest liczbą całkowitą z przedziału od 1 do k dla pewnego ustalonego k.

Sposób sortowania polega na liczeniu ile razy dana liczba występuje w ciągu, który mamy posortować. Następnie wystarczy utworzyć nowy ciąg, korzystając z danych zebranych wcześniej. Np. mamy posortować ciąg liczb <3, 6, 3, 2, 7, 1, 7, 1>. Po zliczeniu (w jednym kroku) operujemy danymi na temat liczności poszczególnych liczb:



  • Liczba 1 występuje 2 razy

  • Liczba 2 występuje 1 raz

  • Liczba 3 występuje 2 razy

  • Liczba 4 występuje 0 razy

  • Liczba 5 występuje 0 razy

  • Liczba 6 występuje 1 raz

  • Liczba 7 występuje 2 razy

Na podstawie tych danych tworzymy ciąg liczb <1, 1, 2, 3, 3, 6, 7, 7>. Jest to ciąg wejściowy, ale posortowany.

Inaczej mówiąc, sortowanie to polega na wyznaczeniu dla każdej liczby wejściowej x, ile elementów jest od niej mniejszych. Znając tę liczbę, znamy pozycję x w ciągu posortowanym, wystarczy ją więc bezpośrednio na tej pozycji umieścić. Sytuacja nieco się zmienia, gdy dozwolonych jest więcej elementów o tej samej wartości, ponieważ nie chcemy, aby wszystkie elementy trafiły na tę samą pozycję.

W procedurze Counting-Sort przyjmujemy, że dane wejściowe są zawarte w tablicy A[1...n], więc length[A]=n. Potrzebne są jeszcze dwie dodatkowe tablice: w B[1...n] zostaną umieszczone posortowane dane wejściowe, a w tablicy C[1...k] zapamiętywane są tymczasowe dane pomocnicze:

PSEUDOKOD

Counting-Sort (A, B, k)

1 for i 1 to k

2 do C[i]  0

3 for i 1 to length[A]

4 do C[A[i]]  C[A[i]] + 1

5 // C[i] zawiera teraz liczbę elementów równych i

6 for  2 to k

7 do C[i]  C[i] + C[i-1]

8 // C[i] zawiera liczbę elementów mniejszych lub równych i

9 for i length[A] downto 1

10 do B[C[A[i]]]  A[i]

11 C[A[i]]  C[A[i]] - 1





  • Kubełkowe (Bucket Sort) – BS

Zakładamy, że dane wejściowe są liczbami rzeczywistymi wybieranymi losowo z przedziału [0, 1), zgodnie z rozkładem jednostajnym.

Sortowanie opiera się na triku polegającym na podziale przedziału [0, 1) na n podprzedziałów jednakowych rozmiarów, tzw. kubełków, a następnie “rozrzuceniu” n liczb do kubełków, do których należą. Ponieważ liczby są jednostajnie rozłożone w przedziale [0, 1), więc oczekujemy, że w każdym z kubełków nie będzie ich zbyt wiele. W celu uzyskania ciągu wynikowego, sortujemy najpierw liczby w każdym z kubełków, a następnie łączy się je wszytkie, przeglądając po kolei kubełki.

Poniżej znajduje się przykład zastosowania dla nieuporządkowanego ciągu liczb <0.78, 0.15, 0.26, 0.02, 0.64, 0.76, 0.63, 0.59, 0.25, 0.74, 0.15, 0.18, 0.82, 0.79, 0.39>.
P
SEUDOKOD:
BUCKET-SORT(A)


  1. nlength[A]

  2. for i  1 to n

  3. do wstaw A[i] do listy B[ nA[i] ]

  4. for i  0 to n – 1

  5. do posortuj listę B[i] przez wstawianie

  6. połącz listy B[0], B[1],..., B[n – 1] dokładnie w tej kolejności


  • Przez scalanie (Merge Sort) – MS

Scalanie ciągów polega na łączeniu posortowanych ciągów w jeden ciąg posortowany. Ciągi scala się parami, poczynając od pierwszych dwóch. Ustawiamy liczniki obu ciągów na 1 (co wskazuje na pierwszy element ciągu). Sprawdzamy, który z elementów jest mniejszy i ten element przenosimy do ciągu wynikowego, a licznik ciągu, którego element był mniejszy zwiększamy o 1. Następnie sprawdzamy kolejne elementy wskazywane przez liczniki i robimy to tak długo, aż liczniki będą wskazywać na ostatnie elementy swoich ciągów. Gdy tak się stanie, w ciągu wynikowym będziemy mieli scalone dwa ciągi o liczbie wyrazów będącej sumą elementów ciągów scalanych. Po scaleniu dwóch pierwszych ciągów scalamy ciąg wynikowy i trzeci. Po tej operacji w ciągu wynikowym będziemy mieli scalone 3 pierwsze ciągi. Następnie scalamy ciąg wynikowy z ciągiem 4, itd...

Poniżej znajduje się przykład zastosowania dla nieuporządkowanych ciągów liczb <1, 5, 18, 27, 31, 95> oraz <5, 13, 21, 31, 45, 88, 95, 107>.





Poniżej znajduje się przykład zastosowania dla nieuporządkowanego ciągu liczb <2, 1, 2, 9, 5, 0>.


P
SEUDOKOD:


MERGE-SORT(A, p, r)

  1. if p r

  2. then q  (p + r)/2

  3. MERGE-SORT(A, p, q)

  4. MERGE-SORT(A, q+1, r)

  5. MERGE(A, p, q, r)

A = tablica

p,q, r = indeksy, takie, że p  q  r

Zakłada się, że podtablice A[p..q], A[q + 1.. r] są posortowane. Procedura MERGE-SORT scala te tablice w jedną posortowaną tablicę A[p..r].





Dane, które chcemy posortować są przechowywane w plikach. Nie mamy bezpośredniego dostępu do dowolnego elementu ciągu do posortowania (teoretycznie mamy, ale wyszukanie kolejnego elementu w ciągu znajdującego się przed elementem, który pobraliśmy ostatnio, wymaga przejścia pliku od początku). Wykorzystujemy dwa pliki pomocnicze. Zakładamy, że sortujemy niemalejąco.

  1. Rozdzielamy seriami plik wejściowy na dwa pliki pomocnicze. To znaczy przechodząc plik wejściowy od początku, wyszukujemy ciągi posortowane i zamiennie zapisujemy na dwa pomocnicze pliki. W praktyce wygląda to tak, że pobiera się n-ty oraz (n+1)-wszy element z pliku i sprawdza się, czy (n+1)-wszy jest większy lub równy n-temu. Jeśli tak, to należy do ciągu i zapisujemy go do tego samego pliku pomocniczego co element n-ty. Jeśli nie, to zapisujemy go na inny (drugi) plik pomocniczy i tak w kółko, aż do zakończenia pliku wejściowego.

  1. Łączymy serie z plików pomocniczych i kopiujemy do pliku wejściowego (wejściowy lub dla ochrony danych można sobie wziąć kolejny plik pomocniczy i na początku po prostu skopiować plik wejściowy do niego). Łączenie przebiega analogicznie do scalania ciągów, z tą różnicą, że tutaj oba pliki wejściowe niekoniczenie są całkowicie posortowane.

  1. Wykonujemy zamiennie kroki 1 i 2, aż do momentu, w którym otrzymamy w pliku wejściowym tylko jedną serię, która jest naszym posortowanym ciągiem.

Poniżej znajduje się przykład zastosowania dla nieuporządkowanego ciągu liczb <1, 9, 8, 7, 4, 5, 7, 6, 1, 4, 0, 9, 8, 1, 3, 4, 8, 1, 7>.

Po pierwszym kroku:


Pierwszy plik pomocniczy: 19 7 6 09 134 8 (odstępy pomiędzy seriami)
Drugi plik pomocniczy: 8 457 14 8 17
Plik wejściowy: 1894577146089113478

Po drugim kroku:


Pierwszy plik pomocniczy: 189 146 113478
Drugi plik pomocniczy: 4577 089
Plik wejściowy: 1457789014689113478

Po trzecim kroku:


Pierwszy plik pomocniczy: 1457789 113478
Drugi plik pomocniczy: 014689
Plik wejściowy: 0114456778899 113478

Po czwartym kroku:


Pierwszy plik pomocniczy: 0114456778899
Drugi plik pomocniczy: 113478
Plik wejściowy: 0111134445677788899


  • Przez kopcowanie – stogowe (Heapsort) – HS

Czas działania algorytmu wynosi O(n lg n). Algorytm heapsort sortuje w miejscu: tylko stała liczba elementów tablicy jest w czasie działania algorytmu przechowywana poza tablicą wejściową. Używa się tu struktury danych, zwanej „kopcem”, do przetwarzania danych w czasie działania algorytmu.

  • Drzewo:

Dla każdego drzewa wyróżniony jest jeden, charakterystyczny element – korzeń. Korzeń jest jedynym elementem drzewa, który nie posiada elementów poprzednich. Dla każdego innego elementu określony jest dokładnie jeden element poprzedni. Dla każdego elementu oprócz ostatnich, tzw. liści, istnieją co najmniej 2 elementy następne. Jeżeli liczba następnych elementów wynosi dokładnie 2 to drzewo nazywamy binarnym.





  • Kopiec (stóg):

Kopiec (binarny), inaczej zwany stogiem, jest to tablicowa struktura danych, którą można rozpatrywać jako pełne drzewo binarne, które spełnia tzw. warunek kopca (każdy następnik jest niewiększy od swego poprzednika). Z warunku tego wynikają szczególne własności kopca:

  • w korzeniu kopca znajduje się największy element,

  • na ścieżkach (połączeniach między węzłami), od korzenia do liścia, elementy są posorotwane nierosnąco.

Każdy węzeł drzewa odpowiada elementowi tablicy, w którym jest podana wartość węzła. Drzewo jest pełne na wszystkich poziomach z wyjątkiem być może najniższego, który jest wypełniony od strony lewej do pewnego miejsca.


Po zbudowaniu drzewa należy wykonać odpowiednie instrukcje, które zapewnią mu warunek kopca. Należy więc sprawdzać (poczynając od poprzednika ostatniego liścia schodząc w górę do korzenia), czy poprzednik jest mniejszy od następnika i jeżeli tak jest to zamienić je miejscami. Po wykonaniu tych czynności drzewo binarne zamienia się w stóg. Z jego własności wynika, że w korzeniu znajduje się największy element. Korzystając z tego faktu, możemy go pobrać na koniec tablicy wynikowej, a na jego miejsce wstawić ostatni liść. Po pobraniu korzenia tablica źródłowa zmniejsza się o 1 element, a porządek kopca zostaje zaburzony (nie wiadomo, czy ostatni liść będący teraz korzeniem jest rzeczywiście największym elementem). By przywrócić warunek stogu należy ponownie uporządkować jego elementy, tym razem jednak zaczynając od korzenia (ponieważ to on jest nowym elementem). Po przywróceniu porządku w kopcu możemy ponownie pobrać korzeń i wstawić go do tablicy wynikowej (tym razem na drugie miejsce od końca), wstawić na jego miejsce liść i zmniejszyć rozmiar tablicy źródłowej o 1. Wykonujemy te czynności aż do ostatniego korzenia. Po całkowitym wyczyszczeniu kopca w tablicy wynikowej będziemy mieli posortowane elementy z tablicy wejściowej.























  • Szybkie (Quicksort) – QS

Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego. Do utworzenia podzbioru musimy ze zbioru wybrać jeden z elementów, który nazwiemy piwotem. W lewym podzbiorze znajdą się wszystkie elementy niewiększe od piwotu, a w prawym podzbiorze znajdą się wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem mogą one występować w obu podzbiorach. Również porządek elementów w każdym z podzbiorów nie jest ustalony. Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Dla naszych potrzeb wybierzemy element środkowy.





ZMIANY!:

Sprawozdania z Ćwiczenia1 można przesyłać do dnia 08.04.2007 (włącznie). Po tym terminie zostaną wysunięte znane studentom konsekwencje. Poza tym niedostarczenie Ćwiczenia1 do dnia 20.04.2007 (włącznie) jest równoważne z otrzymaniem oceny niedostatecznej z Ćwiczenia1!

Usunięto sortowanie kubełkowe – jeśli już ktoś to wykonał, to bardzo proszę tego nie usuwać z programu.

Sprawozdania z Ćwiczenia1(również kod programu) proszę przesłać na adres:

Anna.Widelska@cs.put.poznan.pl.

Informacje odnośnie Ćwiczenia2 znajdują się w dokumencie odnośnie algorytmów grafowych.


PROJEKT


ĆWICZENIE1. SORTOWANIE.

Celem projektu jest zaimplementowanie wybranych metod sortowania oraz przeprowadzenie pomiarów mających na celu ich porównanie.

Projekt składa się z dwóch części.

W części pierwszej należy porównać szybkość działania następujących metod sortowania:



  • sortowanie kubełkowe (BS) - USUNIĘTE

  • przez zliczanie (CS),

  • przez scalanie (MS),

  • przez kopcowanie (HS).

dla liczb całkowitych generowanych losowo, zgodnie z równomiernym rozkładem prawdopodobieństwa. Wyniki należy przedstawiać na wspólnym wykresie t = f(n), gdzie t – czas sortowania (w sekundach), n – liczba elementów tablicy. Liczbę elementów należy dobrać w taki sposób, aby możliwe było wykonanie pomiarów. Dla każdej metody sortowania należy powtórzyć pomiary 10 razy. Należy sformułować wnioski odnośnie złożoności obliczeniowej badanych metod i ich związku z efektywnością sortowania oraz zajętością pamięciową każdej z nich.

W drugiej części należy porównać efektywność działania algorytmu sortowania szybkiego (QS). Należy stworzyć trzy implementacje tego algorytmu:



  • z wyborem pierwszego elementu,

  • z medianą (ze środkowym elementem wyboru),

  • z medianą z trzech elementów (pierwszy, środkowy i ostatni).

Należy zbadać działanie algorytmu dla następujących typów danych:

  • dla danych losowych.

Wyniki należy przedstawić na wykresie t = f(n), gdzie t – czas sortowania (w sekundach), n – liczba elementów tablicy. Dla każdej implementacji należy powtórzyć pomiary 10 razy. Należy sformułować wnioski odnośnie złożoności obliczeniowej i efektywności algorytmu sortowania szybkiego oraz zachowania się algorytmu w najgorszym przypadku dla poszczególnych implementacji. Należy również odpowiedzieć na następujące dwa pytania:

  • jaki wpływ ma mediana na czas sortowania?

  • w jakim celu jest ona stosowana?

W wyniku przeprowadzonych doświadczeń należy stworzyć sprawozdanie opisujące uzyskane wyniki, stworzone zgodnie z następującymi zaleceniami:

  • drukowane obustronnie,

  • brak strony tytułowej; wymagane dane osobowe + numery indeksów,

  • brak opisu ćwiczenia oraz kodu programu!,

  • przedstawione na wykresach wyniki powinny być poparte tabelami zawierającymi wyniki uzyskane podczas pomiarów dla każdego pomiaru z osobna wraz z wartością średnią dla każdej z metod,

  • dokonać analizy zachowania metody dla różnych rozkładów danych wejściowych z uwzględnieniem identyfikacji najlepszego i najgorszego przypadku,

  • sformułować wnioski dotyczące wad, zalet i ograniczeń poszczególnych algorytmów oraz złożoności obliczeniowej w przypadku średnim, najlepszym i najgorszym,

  • podać zalecane warunki stosowania metody.

Sprawozdanie musi zostać dostarczone prowadzącemu zajęcia dnia 01.04.2007 podczas oddawania i testowania programu, który powinien zawierać implementację wszystkich powyżej opisanych sortowań i operacji w środowisku programistycznym dostępnym na laboratoriach.


Literatura:

Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest



Wprowadzenie do algorytmów

Wydanie czwarte, Wydawnictwo Naukowo-Techniczne, Warszawa, 2001

N. Wirth

Algorytmy + struktury danych = programy

Wydawnictwo Naukowo-Techniczne, Warszawa, 2004


Prowadzący:

mgr Anna Widelska

anna.widelska@cs.put.poznan.pl

Instytut Informatyki PP, ul. Wieniawskiego 17/19, pokój: 227K



WWW: www.cs.put.poznan.pl/awidelska/


©snauka.pl 2016
wyślij wiadomość