Wydział Odlewnictwa	Andrzej Kwiecień	Rok I	Grupa A3
Pracownia informatyczna	Temat: Metody sortowania.
Data wykonania: 19.12.2010r.	Ocena:

Cel:

Porównanie szybkości metod sortowania dla danej liczby elementów zbioru.

Wstęp teoretyczny:
Sortowanie jest to proces ustawiania zbioru obiektów w określonym porządku.

Podział:

- sortowanie tablic (sortowanie wewnętrzne)

-sortowanie plików sekwencyjnych (sortowanie zewnętrzne)

1. Sortowanie bąbelkowe „Sortowanie przez prostą zamianę”

Jedną z popularnych metod sortowania jest sortowanie przez prostą zamianę (sortowanie bąbelkowe). W metodzie tej porównujemy sąsiednie elementy. W celu uporządkowania elementów od najmniejszego do największego, jeśli drugi element jest mniejszy od poprzedniego, to zamieniamy go miejscami. Następnie element, który stał się drugim, porównujemy z trzecim i przestawiamy, jeśli jest mniejszy itd. Przykład:

Przebieg pierwszy:

7 6 1 9 5 - porównujemy 7 i 6 ( przestawiamy, bo 6 < 7)

6 7 1 9 5 - porównujemy 7 i 1 ( przestawiamy, bo 1 < 7)

6 1 7 9 5 - porównujemy 7 i 9 ( nie przestawiamy, bo 10 > 7)

6 1 7 9 5 - porównujemy 9 i 5 ( przestawiamy, bo 5 < 10)

6 1 7 5 9 - 9 na właściwym miejscu

Przebieg drugi:

6 1 7 5 9 - porównujemy 6 i 1 ( przestawiamy, bo 1 < 6)

1 6 7 5 9 - porównujemy 6 i 7 ( nie przestawiamy, bo 7 > 6)

1 6 7 5 9 - porównujemy 7 i 5 ( przestawiamy, bo 5 < 7)

1 6 7 5 9 - porównujemy 7 i 5 ( przestawiamy, bo 5 < 7)

1 6 5 7 9 - 7 i 9 na właściwym miejscu

Przebieg trzeci:

1 6 5 7 9 - porównujemy 1 i 6 ( nie przestawiamy, bo 6 > 1)

1 6 5 7 9 - porównujemy 6 i 5 ( przestawiamy, bo 5 < 6)

1 5 6 7 9 - 6, 7, 9 na właściwym miejscu

Przebieg czwarty:

1 5 6 7 9 - porównujemy 1 i 5 nie przestawiamy, bo 5 > 1

2.Sortowanie przez proste wstawianie „Insert sort”

Sortowanie przez wstawienie (insert sort) często stosujemy podczas gry w karty. Biorąc po jednej karcie wstawiamy ją w odpowiednie miejsce tak aby były odpowiednio poukładane (posortowane).

Algorytm sortowania przez wstawianie polega na tym, że brany jest pierwszy element z części nieuporządkowanej (jeżeli ta część będzie pusta będzie to oznaczało że wszystkie elementy są już posortowane i można zakończyć działanie algorytmu). Następnie pobrany element wstawiany jest w odpowiednie miejsce w części uporządkowanej. Po takiej operacji część nieuporządkowana jest o jeden element krótsza, natomiast część posortowana zyskuje jeden element. Właściwie najważniejszym aspektem działania tego algorytmu jest to, aby w prawidłowym miejscu wstawić element do części uporządkowanej.

Najprostszy sposób polega na porównaniu pobranego elementu z kolejnymi elementami części uporządkowanej i jeżeli element na pozycji i jest większy od tego elementu to pobrany element ustawiany jest na pozycję „i”, a cała część uporządkowana od pozycji i jest przesuwana o jedno miejsce).

Mamy do posortowania następujący ciąg liczb:

8 3 7 5 9 1 6 2

Na początek dzielimy nasz ciąg na dwie części, po lewej będziemy mieli liczby już posortowane (na razie nie mamy żadnej), natomiast po prawej stronie będziemy mieli liczby nieposortowane.

Zatem zaczynamy - bierzemy pierwszą liczbę i przenosimy ją na lewą stronę. Na razie jeszcze nie musimy nic więcej robić. W ten sposób otrzymujemy:

"8" 3 7 5 9 1 6 2

Teraz bierzemy kolejną liczbę z prawej strony, czyli "3" i wstawiamy w odpowiednią pozycję po lewej stronie. Ponieważ 3 jest mniejsze od 8, więc wstawiamy ją przed ósemkę:

"3" 8 7 5 9 1 6 2

Podobnie postępujemy z liczbą "7". Ponieważ jest ona mniejsza od 8 a zarazem większa od 3, więc wstawiamy ją na pomiędzy 3 a 8:

3 "7" 8 5 9 1 6 2

Następnie wstawiamy pierwszą liczbę w ciągu po prawej, czyli "5" w odpowiednie miejsce w ciągu po lewej. Odpowiednie miejsce dla "5" to pozycja między liczbami 3 i 7:

3 "5" 7 8 9 1 6 2

Postępując podobnie jak wyżej "9" wstawiamy na koniec, ponieważ jest największe:

3 5 7 8 "9" 1 6 2

Tak samo dla liczby "1" - jest najmniejsze, więc ustawiamy ją na początek:

"1" 3 5 7 8 9 6 2

Liczbę "6" wstawiamy pomiędzy 5 a 7:

1 3 5 "6" 7 8 9 2

I na sam koniec wstawiamy ostatnią z liczb - "2" pomiędzy 1 a 3:

1 "2" 3 5 6 7 8 9

Algorytm sortowania przez wstawianie najlepiej jest zaimplementować na strukturach danych zwanych listami, są one bowiem w tym przypadku bardziej elastyczne. Implementacja na tablicach może być mało efektywna ze względu na konieczność przesuwania danych w tychże tablicach.

3.Sortowanie przez prosta wymianę

Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n²). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.

Algorytm przedstawia się następująco:

1. wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy

2. zamień wartość minimalną, z elementem na pozycji i

Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.

Posortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje sie wartość minimalną.

nr iteracji (wartość i)	tablica	minimum
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1 (element znajduje się na właściwej pozycji)
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4 (...)
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8 (...)

Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.

4.Sortowanie szybkie „Quick Sort”

Algorytm działa rekursywnie - wybierany jest pewien element tablicy, tzw. element osiowy, po czym na początek tablicy przenoszone są wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortuje się osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica nie wymaga sortowania.

Algorytm sortowania szybkiego jest bardzo wydajny: jego średnia złożoność obliczeniowa jest rzędu  . Jego szybkość i prostota implementacji powodują, że jest powszechnie używany; jego implementacje znajdują się również w standardowych bibliotekach języków programowania - na przykład w bibliotece standardowej języka C (funkcjaqsort), w implementacji klasy TList w Delphi, jako procedura standardowa w PHP itp.