Algorytmy i struktury danych - Sortowanie

1. Sortowanie -  polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru.

2. Sortowanie wewnętrzne - to sortowanie w pamięci operacyjnej. Sortowanie zewnętrzne - sortowanie w pamięci zewnętrznej.

3. Algorytm sortowania może sortować w miejscu (sortuje w tej samej tablicy), albo potrzebować dodatkowej tablicy (sortowanie poprzez scalanie).

4. Sortowanie bąbelkowe polega na porównywanie kolejnych par sąsiadujących elementów. Zmiana ich kolejności występuje w przypadku niespełnienia kryterium porządkowego zbioru.

4. Stabilne sortowanie to takie sortowanie, które w tablicy wynikowej elementy o tej samej wartości kluczy występują w tej samej kolejności jak w tablicy wyjściowej. 

5. Algorytmy sortowania mogą polegać na:

• porównywania ze sobą sortowanych elementów (np. sortowanie bąbelkowe, sortowanie przez scalanie, sortowanie szybkie)
• wykorzystaniu informacji o wartościach sortowanych elementów (np. sortowanie kubełkowe)

6. Pomysł Shella - 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ą sortowania przez wstawianie. 

7. Sortowanie przez zliczanie polega na ustawieniu licznika dla każdej wartości w tablicy, a następnie zliczaniu ile razy występuje dana wartość. Następnie sumujemy zawartość licznika oraz jego poprzednika (zaczynamy od drugiego licznika). 

8. W sortowaniu kubełkowym na początku określamy najmniejszą wartość i największą wartość jaką może przyjmować element. Dla każdej możliwej wartości przygotowujemy kubełek - licznik, który będzie zliczał ilość wystąpień tej wartości w sortowanym zbiorze. Przeglądamy kolejno elementy zbioru od pierwszego do ostatniego. Dla każdego elementu zbioru zwiększamy o jeden zawartość licznika o numerze równym wartości elementu. Przeglądamy kolejne liczniki zapisując do zbioru wynikowego ich numery tyle razy, ile wynosi ich zawartość. Zbiór wyjściowy będzie posortowany.

9. Sortowanie pozycyjne polega na sortowaniu elementów wg kolejnych (licząc od

końca) cyfr liczby.