I_P+R_W14_M10_Java Metody sortowania
Sortowanie – przypomnienie
Sortowaniem nazywamy porządkowanie elementów w pewien ustalony sposób.
Istnieje wiele metod sortowania, różniących się zarówno sposobem działania, jak i efektywnością. W związku z tym algorytmy sortujące, w zależności od swojej złożoności algorytmicznej, różnią się czasem rozwiązywania danego problemu.
Sposób sortowania elementów
Elementy sortowanego zbioru mogą być sortowane rosnąco, niemalejąco, malejąco lub nierosnąco. Domyślnym przypadkiem jest sortowanie niemalejące lub rosnące.
Chociaż terminy kolejność niemalejąca i rosnąca oraz nierosnąca i malejąca bywają używane zamiennie, ich znaczenia nie są tożsame.
O sortowaniu rosnącym mówimy wtedy, gdy każdy kolejny posortowany element jest większy od poprzedniego – nie ma równych elementów.
O sortowaniu niemalejącym mówimy wtedy, gdy każdy kolejny posortowany element jest większy lub równy poprzedniemu (w zbiorze są równe sobie elementy).
O sortowaniu malejącym mówimy wtedy, gdy każdy kolejny posortowany element jest mniejszy od poprzedniego – nie ma równych elementów.
O sortowaniu nierosnącym mówimy wtedy, gdy każdy kolejny posortowany element jest mniejszy lub równy poprzedniemu (w zbiorze są równe sobie elementy).
Do czego służy sortowanie?
Sortowanie to inaczej porządkowanie danych uwzględniające jakąś ich cechę. Jeżeli sortujemy liczby, taką cechą jest zazwyczaj ich wartość, więc sortujemy je rosnąco, nierosnąco, malejąco oraz niemalejąco. Sortować możemy nie tylko liczby, ale również litery czy ciągi znaków.
Algorytmy stabilne i niestabilne
Algorytmy stabilne to takie, w których elementy o takiej samej wartości nie zmienią pozycji względem siebie, natomiast algorytmy niestabilne mogą zmienić ich kolejność. Jeżeli algorytm niestabilny napotka dwa elementy o wartości 7, nie musi zamieniać ich miejscami, aby uzyskać posortowany zbiór. W zależności od implementacji, może to jednak zrobić.
Przykłady algorytmów sortowania, które są stabilne: sortowanie przez wstawianie, sortowanie bąbelkowe, sortowanie pozycyjne (np. sortowanie pozycyjne dat, sortowanie pozycyjne liczb, sortowanie pozycyjne słów), sortowanie przez zliczanie, sortowanie przez scalanie.
Przykłady algorytmów sortowania, które nie są stabilne: sortowanie przez wybieranie, sortowanie kubełkowe, sortowanie szybkie.
Złożoność obliczeniowa i pamięciowa
Informacje na temat złożoności obliczeniowej oraz pamięciowej znajdziesz w e‑podręczniku na poziomie rozszerzonym w modułach: Jak wybrać odpowiedni algorytm sortowania? oraz Porównanie algorytmów sortowania.
Słownik
proces polegający na porządkowaniu zbioru elementów według ich wybranych cech
inaczej in situ; sortowanie, w którym niezależnie od rozmiaru danych wejściowych potrzebna jest stała ilość pamięci komputera
sortowanie, w którym elementy o takiej samej wartości nie zmienią pozycji względem siebie
ilość zasobów komputerowych potrzebnych do wykonania zadania
ilość czasu potrzebnego do wykonania zadania, wyrażona jako funkcja ilości danych