Algorytmy sortujące

Август 1, 2022

Содержание

2. ALGORYTMY SORTUJĄCE Sortowanie przez wstawianie Sortowanie przez wybór
3. Wstęp Sortowanie – jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech
4. Zbiór posortowany to taki zbiór, w którym kolejne elementy są poukładane w pewnym porządku (kolejności). Porządek
5. Czasowa złożoność obliczeniowa (ang. computational complexity) algorytmu sortującego (istnieje również złożoność pamięciowa) – określa statystycznie czas
6. W poniższej tabeli przedstawiono przykładowe zapisy klas złożoności obliczeniowej algorytmów.
7. Ze względu na złożoność pamięciową algorytmy sortujące dzielimy na dwie podstawowe grupy: Algorytmy sortujące w miejscu
8. Algorytmy sortujące dzieli się również na dwie grupy: Algorytmy stabilne - zachowują kolejność elementów równych. Oznacza
9. Algorytmy niestabilne - kolejność wynikowa elementów równych jest nieokreślona (zwykle nie zostaje zachowana). sortowanie przez wybór
10. Jest to jedna z prostszych metod sortowania posiadająca klasę czasowej złożoności obliczeniowej równą O(n2). Polega na
11. Posortujmy dany zbiór (5 8 2 9 4). Kolorem niebieskim oznaczone zostały elementy zbioru, które zostały
12. Dane wejściowe n - liczba elementów w sortowanym zbiorze, n ∈ N d[ ] - zbiór
13. Schemat blokowy Pętla zewnętrzna sterowana zmienną j wyznacza kolejne elementy zbioru o indeksach od 1 do
14. Sortowanie przez wstawianie - Insertion Sort Jest to prosty algorytm sortowania, o złożoności O(n2), sortowanie odbywa
15. Schemat działania algorytmu: Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni element zbioru. Jednoelementowa lista
16. Przykład Dla przykładu wstawmy według opisanej metody pierwszy element zbioru listę uporządkowaną utworzoną z pozostałych elementów
17. Ciąg dalszy przykładu:
18. Dane wejściowe n - liczba elementów w sortowanym zbiorze, n Î N d[ ] - zbiór
19. Schemat blokowy Pętlę główną rozpoczynamy od przedostatniej pozycji w zbiorze. Element na ostatniej pozycji jest zalążkiem
20. W obu przypadkach na puste miejsce ma trafić zawartość zmiennej x i pętla zewnętrzna jest kontynuowana.
21. Algorytm sortowania przez wstawianie nie uwzględnia faktu posortowania zbioru. Jednakże również nie wyróżnia on przypadku posortowania
23. Скачать презентацию

Слайд 2

ALGORYTMY SORTUJĄCE
Sortowanie przez wstawianie Sortowanie przez wybór

Слайд 3

Wstęp
Sortowanie – jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru

danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.
Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwieniu stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.
Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego.

Слайд 4

Zbiór posortowany to taki zbiór, w którym kolejne elementy są poukładane

w pewnym porządku (kolejności). Porządek ten możemy określić za pomocą relacji ≥ lub ≤ (albo dowolnej innej relacji porządkowej, która jednoznacznie wyznacza kolejność elementów w zbiorze). Równość jest konieczna w przypadku, gdy elementy zbioru mogą przyjmować takie same wartości. Na przykład zbiór liczb:
Z = { 1, 4, 4, 5, 6, 8, 8, 9 }
jest posortowany rosnąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja, w której element poprzedni jest mniejszy lub równy od elementu następnego
Odwrotnie, zbiór:
Z = { 9, 8, 7, 6, 4, 4, 2, 1, 0 }
jest posortowany malejąco, ponieważ pomiędzy każdymi dwoma kolejnymi elementami zachodzi relacja, w której element poprzedni jest większy lub równy od elementu następnego.
W przypadku, kiedy zbiór nie składa się z liczb, należy określić dla każdego elementu tzw. klucz (ang. key), wedłóg którego dokonywane jest sortowanie.
Klucz jest liczbą, dlatego obowiązują dla niego podane wcześniej zasady kolejności elementów.

Слайд 5

Czasowa złożoność obliczeniowa (ang. computational complexity) algorytmu sortującego (istnieje również złożoność

pamięciowa) – określa statystycznie czas wykonywania algorytmu w zależności od liczby danych wejściowych.
Czasowa złożoność obliczeniowa wyrażana jest liczbą tzw. operacji dominujących, czyli takich, które mają bezpośredni wpływ na czas wykonywania algorytmu. Dzięki takiemu podejściu uniezależnia się czasową złożoność obliczeniową od szybkości komputera, na którym dany algorytm jest realizowany.
Złożoność obliczeniowa charakteryzowana jest przy pomocy tzw. notacji O (omikron). Zapis O( ) określamy mianem klasy złożoności obliczeniowej algorytmu.
Klasa czasowej złożoności obliczeniowej umożliwia porównywanie wydajności różnych algorytmów sortujących. Z reguły proste algorytmy posiadają wysoką złożoność obliczeniową - długo dochodzą do wyniku końcowego.
Algorytmy bardziej skomplikowane posiadają mniejszą złożoność obliczeniową - szybko dochodzą do rozwiązania.

Czasowa złożoność obliczeniowa

Слайд 6

W poniższej tabeli przedstawiono przykładowe zapisy klas złożoności obliczeniowej algorytmów.

Слайд 7

Ze względu na złożoność pamięciową algorytmy sortujące dzielimy na dwie podstawowe

grupy:
Algorytmy sortujące w miejscu (ang. in place) - wymagają stałej liczby dodatkowych struktur danych, która nie zależy od liczby elementów sortowanego zbioru danych (ani od ich wartości). Dodatkowa złożoność pamięciowa jest klasy O(1). Sortowanie odbywa się wewnątrz zbioru. Ma to bardzo istotne znaczenie w przypadku dużych zbiorów danych, ponieważ mogłoby się okazać, iż posortowanie ich nie jest możliwe z uwagi na brak pamięci w systemie. Sortowanie w miejscu, jest bardzo dużą zaletą.
Algorytmy nie sortujące w miejscu - wymagają zarezerwowania w pamięci dodatkowych obszarów, których wielkość jest uzależniona od liczby sortowanych elementów lub od ich wartości. Tego typu algorytmy są zwykle bardzo szybkie w działaniu, jednakże wymagają dodatkowej pamięci. Dlatego może się okazać, iż taki algorytm nie będzie w stanie posortować dużego zbioru danych, ponieważ system komputerowy nie posiada wystarczającej ilości pamięci RAM.

Oprócz złożoności czasowej definiuje się również złożoność pamięciową. Określa ona ilość zasobów komputera, których wymaga dany algorytm w zależności od liczby danych wejściowych. Tutaj także ma zastosowanie notacja omikron. Podczas określania złożoności algorytmu należy wziąć pod uwagę oba typy złożoności obliczeniowej.

Pamięciowa złożoność obliczeniowa

Слайд 8

Algorytmy sortujące dzieli się również na dwie grupy:
Algorytmy stabilne - zachowują

kolejność elementów równych. Oznacza to, iż elementy o tych samych wartościach będą występowały w tej samej kolejności w zbiorze posortowanym, co w zbiorze nieposortowanym. Czasami ma to znaczenie, gdy sortujemy rekordy bazy danych i nie chcemy, aby rekordy o tym samym kluczu zmieniały względem siebie położenie.
sortowanie bąbelkowe (ang. bubblesort) – O(n2)
sortowanie przez wstawianie (ang. insertion sort) – O(n2)
sortowanie przez scalanie (ang. merge sort) – O(nlogn), wymaga O(n) dodatkowej pamięci
sortowanie przez zliczanie (ang. counting sort lub count sort) – O(n + k), wymaga O(n + k) dodatkowej pamięci
sortowanie kubełkowe (ang. bucket sort) – O(n), wymaga O(k) dodatkowej pamięci
sortowanie pozycyjne (ang. radix sort) – O(d(n + k)), gdzie k to wielkość domeny cyfr, a d szerokość kluczy w cyfrach. Wymaga O(n + k) dodatkowej pamięci
sortowanie biblioteczne (ang. library sort) – O(nlogn), pesymistyczny O(n2)

Слайд 9

Algorytmy niestabilne - kolejność wynikowa elementów
równych jest nieokreślona (zwykle nie

zostaje zachowana).
sortowanie przez wybór (ang. selection sort) O(n2) – może być stabilne po odpowiednich zmianach
sortowanie Shella – (ang. shellsort) złożoność nieznana
sortowanie grzebieniowe – (ang. combsort) złożoność nieznana
sortowanie szybkie – (ang. quicksort) Θ(nlogn), pesymistyczny O(n2); z wykorzystaniem algorytmu selekcji "mediana median" ("magicznych piątek") do wyszukiwania mediany, pesymistyczna złożoność to O(nlogn)
sortowanie introspektywne – (ang. introspective sort lub introsort) O(nlogn)
sortowanie przez kopcowanie – (ang. heapsort) O(nlogn)

Слайд 10

Jest to jedna z prostszych metod sortowania posiadająca klasę czasowej złożoności

obliczeniowej równą O(n2).
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:
wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy
zamień wartość minimalną, z elementem na pierwszej pozycji (i)
Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.
Algorytm jest niestabilny. Sortowanie odbywa się w miejscu.

Sortowanie przez wybór - Selection Sort

Слайд 11

Posortujmy dany zbiór (5 8 2 9 4). Kolorem niebieskim oznaczone

zostały elementy zbioru, które zostały już posortowane.

Przykład

Слайд 12

Dane wejściowe
n - liczba elementów w sortowanym zbiorze, n ∈ N

d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.
Dane wyjściowe
d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.
Zmienne pomocnicze
i, j - zmienne sterujące pętli, i, j ∈ N pmin - pozycja elementu minimalnego w zbiorze d[ ], pmin ∈ N
Lista kroków
K01: Dla j = 1, 2, ..., n - 1: wykonuj K02...K04
K02: pmin ← j
K03: Dla i = j + 1, j + 2, ..., n: jeśli d[i] < d[pmin], to pmin ← i
K04: d[j] ↔ d[pmin]
K05: Zakończ

Specyfikacja problemu

Слайд 13

Schemat blokowy
Pętla zewnętrzna sterowana zmienną j wyznacza kolejne elementy zbioru o

indeksach od 1 do n - 1, w których zostaną umieszczone elementy minimalne. Na początku tej pętli zakładamy, iż elementem minimalnym jest element d[j] i zapamiętujemy jego indeks w zmiennej pmin.
W pętli numer 2 sterowanej zmienną i porównujemy pozostałe elementy zbioru z elementem d[pmin]. Jeśli element zbioru d[i] jest mniejszy od elementu d[pmin], to znaleźliśmy nowy element minimalny. W takim przypadku zapamiętujemy jego pozycję w pmin i kontynuujemy pętlę wewnętrzną.
Po zakończeniu pętli wewnętrznej pmin zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[pmin]. Dzięki tej operacji element minimalny znajduje się na swojej docelowej pozycji. Zwiększamy j przechodząc do kolejnego elementu zbioru i kontynuujemy pętlę zewnętrzną.

Слайд 14

Sortowanie przez wstawianie - Insertion Sort
Jest to prosty algorytm sortowania, o

złożoności O(n2), sortowanie odbywa się w miejscu . Mimo że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort posiada pewne zalety:
wydajny dla danych wstępnie posortowanych
wydajny dla zbiorów o niewielkiej liczebności
stabilny
Algorytm polega na usuwaniu pewnego elementu z danych wejściowych i wstawianiu go na odpowiednie miejsce w wynikach. Wybór następnego elementu z danych jest dowolny.

Слайд 15

Schemat działania algorytmu:
Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni

element zbioru. Jednoelementowa lista jest zawsze uporządkowana.
Ze zbioru zawsze wybieramy element leżący tuż przed listą uporządkowaną. Element ten zapamiętujemy w zewnętrznej zmiennej. Miejsce, które zajmował, możemy potraktować jak puste.
Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej.
Jeśli natrafimy na koniec listy, element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy jest większy od wybranego, to element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.
Jeśli element listy nie jest większy od wybranego, to element listy przesuwamy na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Kontynuujemy porównywanie, aż wystąpi sytuacja z punktu 4 lub 5.

Najważniejszą operacją w opisywanym algorytmie sortowania jest wstawianie wybranego elementu na listę uporządkowaną. Zasady są następujące:

Слайд 16

Przykład
Dla przykładu wstawmy według opisanej metody pierwszy element zbioru listę uporządkowaną

utworzoną z pozostałych elementów [7 3 4 5 8]. Elementy listy uporządkowanej zaznaczyliśmy kolorem niebieskim. Puste miejsce zaznaczyliśmy kolorem żółtym:

Слайд 17

Ciąg dalszy przykładu:

Слайд 18

Dane wejściowe
n - liczba elementów w sortowanym zbiorze, n Î N

d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.
Dane wyjściowe
d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.
Zmienne pomocnicze
i, j - zmienne sterujące pętli, i, j Î N x - zawiera wybrany ze zbioru element.
Lista kroków
K01: Dla j = n - 1, n - 2, ..., 1: wykonuj K02...K04
K02: x ← d[j]; i ← j + 1
K03: Dopóki ( i ≤ n ) ∧ ( x > d[i] ): wykonuj d[i - 1] ← d[i]; i ← i + 1
K04: d[i - 1] ← x
K05: Zakończ

Specyfikacja problemu

Слайд 19

Schemat blokowy
Pętlę główną rozpoczynamy od przedostatniej pozycji w zbiorze. Element na

ostatniej pozycji jest zalążkiem listy uporządkowanej. Dlatego licznik pętli nr 1 przyjmuje wartość początkową j = n - 1.
Ze zbioru wybieramy element d[j] i umieszczamy go w zmiennej pomocniczej x. Miejsce zajmowane przez ten element staje się puste.
Pętlę wewnętrzną rozpoczynamy od pozycji następnej w stosunku do j. Pozycja ta zawiera pierwszy element listy uporządkowanej, która tworzona jest na końcu sortowanego zbioru. Pętlę wewnętrzną przerywamy w dwóch przypadkach - gdy licznik pętli wyjdzie poza indeks ostatniego elementu w zbiorze lub gdy element wybrany, przechowywany w zmiennej pomocniczej x, jest mniejszy lub równy bieżąco testowanemu elementowi listy uporządkowanej (dla sortowania malejącego należy zastosować w tym miejscu relację większy lub równy).

Слайд 20

W obu przypadkach na puste miejsce ma trafić zawartość zmiennej x

i pętla zewnętrzna jest kontynuowana. Zauważ, iż pozycja tego miejsca w zbiorze jest równa i - 1.
Jeśli żaden z warunków przerwania pętli wewnętrznej nr 2 nie wystąpi, to przesuwamy bieżący element listy na puste miejsce i kontynuujemy pętlę wewnętrzną.
Podsumowując: pętla zewnętrzna wybiera ze zbioru kolejne elementy o indeksach od n - 1 do 1, pętla wewnętrzna szuka dla wybranych elementów miejsca wstawienia na liście uporządkowanej, po znalezieniu którego pętla zewnętrzna wstawia wybrany element na listę. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od n - 1 do 1, zbiór będzie posortowany.

Schemat blokowy c.d.

Слайд 21

Algorytm sortowania przez wstawianie nie uwzględnia faktu posortowania zbioru. Jednakże również

nie wyróżnia on przypadku posortowania zbioru w kierunku odwrotnym. Dla tego algorytmu złożoność czasowa nie zależy od rozkładu elementów w sortowanym zbiorze.
Przy sortowaniu przez wybór algorytm wykorzystuje fakt posortowania zbioru. Dla zbiorów w znacznym stopniu uporządkowanych klasa czasowej złożoności obliczeniowej algorytmu jest prawie liniowa. Czas sortowania takich zbiorów jest bardzo krótki.
Najbardziej niekorzystnym przypadkiem jest sortowanie zbioru posortowanego odwrotnie - czas sortowania jest najdłuższy. Czas sortowania zbioru o losowym rozkładzie elementów jest o połowę krótszy.
Algorytm sortowania przez wybór jest dużo lepszy od sortowania przez wstawianie w przypadku zbiorów w znacznym stopniu uporządkowanych. Również zbiory o losowym rozkładzie elementów będą posortowane szybciej. Jedynie w przypadku pesymistycznym, gdy zbiór jest posortowany odwrotnie, algorytm jest wolniejszy od algorytmu sortowania przez wybór. Te cechy czynią algorytm sortowania przez wstawianie zalecanym, prostym algorytmem sortującym klasy O(n2).

Podsumowanie

W prezentacji przedstawiono dwa rodzaje algorytmów: algorytm stabilny – na przykładzie sortowania przez wstawianie i algorytm niestabilny - na przykładzie sortowania przez wybór.

Algorytmy sortujące

Содержание

ALGORYTMY SORTUJĄCESortowanie przez wstawianie Sortowanie przez wybór

WstępSortowanie – jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru

Zbiór posortowany to taki zbiór, w którym kolejne elementy są poukładane

Czasowa złożoność obliczeniowa (ang. computational complexity) algorytmu sortującego (istnieje również złożoność

W poniższej tabeli przedstawiono przykładowe zapisy klas złożoności obliczeniowej algorytmów.

Ze względu na złożoność pamięciową algorytmy sortujące dzielimy na dwie podstawowe

Algorytmy sortujące dzieli się również na dwie grupy:Algorytmy stabilne - zachowują

Algorytmy niestabilne - kolejność wynikowa elementów równych jest nieokreślona (zwykle nie

Jest to jedna z prostszych metod sortowania posiadająca klasę czasowej złożoności

Posortujmy dany zbiór (5 8 2 9 4). Kolorem niebieskim oznaczone

Dane wejściowen - liczba elementów w sortowanym zbiorze, n ∈ N

Schemat blokowyPętla zewnętrzna sterowana zmienną j wyznacza kolejne elementy zbioru o

Sortowanie przez wstawianie - Insertion SortJest to prosty algorytm sortowania, o

Schemat działania algorytmu:Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni

PrzykładDla przykładu wstawmy według opisanej metody pierwszy element zbioru listę uporządkowaną