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++.