Sortowanie

Zajęcia 13

Pojęcia ogólne

Sortowanie

 – to jeden z podstawowych problemów 

informatyki. Polega na 

uporządkowaniu zbioru

 danych 

względem pewnych cech charakterystycznych dla 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żliwienia 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

.

Podamy dwa najprostsze algorytmy sortujące, tj. 

sortowanie 

bąbelkowe

 i 

sortowanie przez wybór

.

Sortowanie bąbelkowe

 (z ang. bubble sort)

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich 
kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. 
Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano 
żadnej zmiany. 

Sortowanie przez wybór

 (z ang. selection sort)

Szukamy w zbiorze elementu najmniejszego i wymieniamy go z 
elementem na pierwszej pozycji. W ten sposób element najmniejszy 
znajdzie się na swojej docelowej pozycji.
W identyczny sposób postępujemy z resztą elementów należących do 
zbioru. Znów wyszukujemy element najmniejszy i zamieniamy go z 
elementem na drugiej pozycji. Otrzymamy dwa posortowane 
elementy. Procedurę kontynuujemy dla pozostałych elementów dotąd, 
aż wszystkie będą posortowane.

Praca Domowa

Przeczytaj o jakimkolwiek innym algorytmie sortującym dla tablicy 
n-elementowej i zaimplementuj go w C++.