Sortowanie bąbelkowe (ang. bubble sort)

Ciąg wejściowy [4,2,5,1,7].

Każdy wiersz symbolizuje wypchnięcie kolejnego największego elementu na koniec ("wypłynięcie największego bąbelka").

Algorytm wykonuje przy każdym z przejść n-1 porównań.

1
2
3
4

Niebieskim	kolorem oznaczono końcówkę ciągu już posortowanego.
Czerwonym	kolorem oznaczono porównywanie elementów jakie będą zamienione
Zielonym	kolorem oznaczono porównywanie elementów jakie będą zamienione

for i = (n-1) to 1

for j = 0 to (i-1)

if A[j]<A[j+1]

swap (A[j],A[j+1])

Łączna ilość porównań

Zadania

Zadanie 1

Jaka jest złożoność czasowa algorytmu ?

Zadanie 2

Posortuj ciąg : 3,9,7,1,4,2,8

Zadanie 3

Posortuj ciąg : 5,4,3,2,1

Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort)

Ciąg wejściowy [4,2,5,1,7].

Jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty - kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe.

Poniżej kod sortowania przez wstawianie tabel indeksowanych od zera (zero-based array)

for i = 1 to (n-1)

j = i

while j>0 and A[j] < A[j-1]

swap (A[j],A[j-1])

j=j-1

Zadania

Zadanie 1

Jaka jest złożoność czasowa algorytmu ?

Zadanie 2

Posortuj ciąg : 3,9,7,1,4,2,8

Zadanie 3

Posortuj ciąg : 5,4,3,2,1

Sortowanie Shella (ang. Shell Sort)

1959: Donald Shell

Algorytm sortowania metodą Shella jest ulepszonym algorytmem sortowania przez wstawianie.

Sortowany zbiór dzielimy na podzbiory, których elementy są odległe od siebie w sortowanym zbiorze o pewien odstęp h. Każdy z tych podzbiorów sortujemy algorytmem przez wstawianie. Następnie odstęp zmniejszamy. Powoduje to powstanie nowych podzbiorów (będzie ich już mniej). Sortowanie powtarzamy i znów zmniejszamy odstęp, aż osiągnie on wartość 1. Wtedy sortujemy już normalnie za pomocą Instertion Sort. Jednakże z uwagi na wcześniejsze obiegi sortujące mamy ułatwione zadanie, ponieważ zbiór został w dużym stopniu uporządkowany. Dzięki początkowym dużym odstępom elementy były przesuwane w zbiorze bardziej efektywnie - na duże odległości.

Pierwotnie Shell proponował pierwszy odstęp równy połowie liczby elementów w sortowanym zbiorze. Kolejne odstępy otrzymujemy dzieląc odstęp przez 2 (dzielenie całkowitoliczbowe).

Kluczowym elementem wpływającym na efektywność sortowania metodą Shella jest właściwy dobór ciągu odstępów. Okazuje się, iż ciąg zaproponowany przez twórcę algorytmu jest jednym z najgorszych, ponieważ w kolejnych podzbiorach uczestniczą wielokrotnie te same elementy.

Dotąd problem optymalnych odstępów w algorytmie sortowania metodą Shella nie został rozwiązany matematycznie, ponieważ w ogólnym przypadku jest niezwykle trudny. Wielu badaczy proponowało na wybór tych odstępów różne ciągi liczbowe otrzymując lepsze lub gorsze rezultaty.

input: an array a of length n with array elements numbered 0 to n − 1

inc ← round(n/2)

while inc > 0 do:

for i = inc .. n − 1 do:

temp ← a[i]

j ← i

while j ≥ inc and a[j − inc] > temp do:

a[j] ← a[j − inc]

j ← j − inc

a[j] ← temp

inc ← round(inc / 2.2)

Sortowanie biblioteczne (ang. Library Sort)

2006: Michael A. Bender, Martín Farach-Colton, and Miguel Mosteiro

Algorytm sortowania, który bazuje na algorytmie sortowania przez wstawianie, ale z dodawaniem pustych miejsc w tablicy w celu przyśpieszenie wstawiania elementów.

M.A. Bender, M. Farach-Colton, M. Mosteiro "Insertion Sort is O(n log n)"

Podział algorytmów sortowania:

Stabilny (Stable)	TAK	zachowuje kolejność elementów o równych wartościach. Oznacza to, że elementy o równych wartościach będą występowały w tej samej kolejności w zbiorze posortowanym, w jakiej występowały w zbiorze nieposortowanym
		NIE	kolejność wynikowa elementów o równych wartościach jest nieokreślona, czyli względne uporządkowanie elementów o równych wartościach zwykle nie zostaje zachowane
W miejscu (in place)	TAK	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 zatem klasy O(1). Sortowanie odbywa się wewnątrz zbioru. Ma to bardzo istotne znaczenie w przypadku dużych zbiorów danych, gdyż mogłoby się okazać, iż posortowanie ich nie jest możliwe z uwagi na brak pamięci w systemie
		NIE	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 okupione to jest dodatkowymi wymaganiami na pamięć. Zatem w pewnych sytuacjach 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.
Sortowanie	wewnętrzne (internal sort)	tablic, które są przechowywane w szybkiej, o dostępie swobodnym „wewnętrznej” pamięci komputerów - zwykle RAM
		zewnętrzne (external sort)	rodzaj algorytmów sortowania, które są stosowane, kiedy z pewnych względów nie jest możliwe jednoczesne umieszczenie wszystkich elementów zbioru sortowanego w pamięci operacyjnej. Na przykład plików sekwencyjnych, które są zazwyczaj przechowywane w wolniejszej pamięci „zewnętrznej” z dostępem bezpośrednim tylko do wierzchu każdej sterty danych

Efektywnośćmetod sortowania

Do najważniejszych kryteriów oceny jakości metod sortowania należą:

• Złożoność pamięciowa - ilość potrzebnej pamięci (oszczędność pamięci)

• Złożoność czasowa - ilość potrzebnych operacji (porównań czy też przesunięć/przestawień)

Ze względu na oszczędność miejsca, elementy sortuje się w tablicy, w której się aktualnie znajdują (in place).

Sortowanie składa się zasadniczo z dwóch rodzajów operacji:

• porównań elementów

• przesunięć elementów

Liczby porównań i przesunięć koniecznych do posortowania zbioru są dobrą miarą efektywności metod sortowania.

Oznaczmy liczbę:

• porównań koniecznych do posortowania zbioru oznaczmy symbolem C,

• koniecznych przesunięć symbolem S.

Dla zbioru zawierającego n, elementów:

• dobre metody sortowania mają efektywność, tj liczbę C i S rzędu
  

• proste metody sortowania mają efektywność, tj liczbę C i S rzędu
  

Porównanie wybranych algorytmów sortowania:

	Złożoność obliczeniowa			Złożoność pamięciowa
		Najlepsza	Średnia		Najgorsza
Sortowanie przez wstawianie Insertion sort				1
Sortowanie Shella Shell sort				1
Sortowanie biblioteczne Library sort	-
Sortowanie bąbelkowe Buble sort				1

---