Politechnika Zielonogórska

Instytut Robotyki i Inżynierii Oprogramowania

Laboratorium:

Algorytmy i struktury danych

ćwiczenie 4:

Wybrane metody sortowania wewnętrznego

1 Wstęp

1 Wstęp

Ćwiczenie ma na celu zapoznanie studentów z wybranymi metodami sortowania wewnętrznego. Badane w ćwiczeniu metody sortowania to: sortowanie przez proste wstawianie, sortowanie przez proste wybieranie, sortowanie bąbelkowe, sortowanie szybkie (quick sort). Zakładamy, że długość tablicy podlegającej sortowaniu jest znana i wynosi n.

2. Metody sortowania:

2.1. Sortowanie przez proste wstawianie

Sortowanie przez proste wstawianie odbywa się w następujący sposób: dla każdego i = 2, 3, ..., n trzeba powtarzać wstawianie a[i] w już uporządkowaną część tablicy a[1] ≤ ... ≤ a[i-1]. W metodzie tej obiekty podzielone są umownie na dwa ciągi: ciąg wynikowy a₁...a_i-1 oraz ciąg źródłowy a_i...a_n. W każdym kroku począwszy od i=2 i zwiększając i o jeden, i-ty element ciągu źródłowego przenosi się do ciągu wynikowego, wstawiając go w odpowiednim miejscu.

Algorytm:

1 Wykonaj co następuje począwszy od indeksu i=2 do i=n

2 Wskaż na i-ty element

3 Wstaw i-ty element w odpowiednim miejscy w a₁...a_i

2.2. Sortowanie przez proste wybieranie

Sortowanie przez proste wybieranie polega na wyznaczeniu najmniejszego elementu w ciągu; zamianie go z pierwszym elementem w ciągu, wyznaczeniu najmniejszego elementu w a[2,n] i zamianie go z drugim elementem: wyznaczeniu najmniejszego elementu w a[3,n] i zamianie go z trzecim elementem itd. aż do posortowania całkowitego ciągu.

Algorytm:

1 Wykonaj co następuje n-1 razy (i=1 do i=n-1)

2 Wskaż na najmniejszy element spośród a[i]...a[n];

3 Wymień go z a_i

2.3. Sortowanie bąbelkowe

Sortowanie bąbelkowe polega na przeglądaniu od końca sortowanej tablicy i zamianie miejscami elementów jeśli są one w kolejności odwrotnej tj. pierwszy jest mniejszy od drugiego. Po zakończeniu pierwszego przejścia element najmniejszy powinien się znajdować na odpowiednim dla niego miejscu czyli na początku tablicy.

Algorytm:

1 Wykonaj co następuje n-1 razy (i=n-1,...,1)

2 Wskaż na ostatni element;

3 Wykonaj co następuje i razy

Porównaj wskazany element z elementem poprzednim

Jeśli porównane elementy są w nie właściwej kolejności, zamień je miejscami

Wskaż na następny element;

2.4. Sortowanie szybkie (Quick Sort)

Jest to metoda, w której stosuje się zasadę zamiany. W metodzie sortowania szybkiego korzysta się z faktu, że w celu zapewnienia efektywności powinno się wymieniać obiekty położone daleko od siebie. Załóżmy że dane jest n obiektów ustawionych w odwrotnym porządku kluczy. Można posortować je wykonując tylko n/2 wymian, biorąc najpierw obiekty - skrajny z lewej strony i skrajny z prawej strony, a następnie posuwać się stopniowo do środka z obu stron. Oczywiście takie postępowanie możliwe jest tylko dlatego, że uporządkowanie było dokładnie odwrotne.

Wybierzmy losowo jakiś obiekt i nazwijmy go x; przeglądajmy tablicę od lewej strony aż znajdziemy obiekt ai > x, a następnie przeglądajmy tablicę od prawej strony aż znajdziemy aj < x. Wymieńmy teraz te dwa obiekty i kontynuujmy proces “przeglądania i zamiany”, aż nastąpi spotkanie gdzieś w środku tablicy. W rezultacie otrzymamy tablicę podzieloną na lewą część z kluczami mniejszymi od x oraz prawą część z kluczami większymi od x.

Jeżeli na przykład za x wybierzemy środkowy klucz 42, to w tablicy kluczy

44 55 12 42 94 6 18 67

trzeba dokonać dwóch wymian aby otrzymać tablicę podzieloną

18 6 12 42 94 55 44 67

Ostatnie wartości indeksów są i = 5 oraz j = 3. Klucze a1...ai-1 są mniejsze bądź równe kluczowi x=42, klucze aj+1...an są większe bądź równe temu kluczowi. Wynika stąd, że otrzymaliśmy podział na dwie części, a mianowicie

ak.klucz x.klucz dla k = 1...i-1

ak.klucz x.klucz dla k = j+1...n

oraz

ak.klucz = x.klucz dla k = j+1...i-1

Następnie powtarzamy tę operacje dla obu wcześniej utworzonych podciągów.

Algorytm

Istnieje ciąg liczb x_l, x_l+1, x_p,

Krok1. Przyjmij za element podziału element v znajdujący się w pobliżu środka ciągu, i podziel tym elementem dany ciąg.

Oznacza to, że v znajdzie się na pozycji elementu x_k, dla pewnego k spełniającego

l ≤ k ≤ p, i elementy na lewo będą od niego nie większe a elementy na prawo od niego będą nie mniejsze.

Krok 2. Zastosuj ten sam algorytm do (l, k-1, x)

Krok 2. Zastosuj ten sam algorytm do (k+1, p, x)

Algorytm ten jest bardzo prosty i efektywny, ponieważ zmienne i, j oraz x mogą być w czasie przeglądania tablicy trzymane w szybkich rejestrach maszyny cyfrowej.

Ćwiczenia do wykonania

1. Utworzyć schemat blokowy i zaimplementować program losujący n-elementową tablicę liczb typu integer (n ≤ 1000) i zapisujący wylosowaną tablicę do pliku.

1. Utworzyć schemat blokowy i zaimplementować w programy sortujące elementy losowej tablicy pobranej z pliku (z zad 1.) następującymi metodami: proste wstawianie, proste wybieranie, bąbelkowa, „quick sort”. Program powinien wyświetlać tablicę nieposortowaną, ilość porównań, ilość przestawień, czas sortowania, tablicę posortowaną oraz zapisywać posortowaną tablicę na dysk (do innego pliku niż plik źródłowy).

2. Sprawozdanie powinno zawierać porównanie badanych metod sortowania

Literatura:

1. D. Harel , Rzecz o istocie informatyki, WNT, Warszawa 1992

2. N. Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa, 1989 i późniejsze.

3. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Warszawa 1996

4. M. Sysło, Algorytmy WSIP Warszawa 1997 !!!

---