Przeczytaj
Porównanie algorytmów sortowania
Zapoznaj się z tabelą, w której skrótowo porównujemy algorytmy sortowanie, które zostały omówione w e‑materiałach.
Algorytm sortowania | StabilnośćStabilność | Sortowanie w miejscuSortowanie w miejscu | IteracjaIteracja | RekurencjaRekurencja | Dziel i zwyciężajDziel i zwyciężaj | Algorytm liniowyAlgorytm liniowy | Porównania | Zliczenia |
przez wybieranie | TAK | TAK | TAK | TAK | ||||
przez wstawianie | TAK | TAK | TAK | TAK | TAK | |||
bąbelkowe | TAK | TAK | TAK | TAK | TAK | |||
kubełkowe | TAK | TAK | TAK | |||||
przez zliczanie | TAK | TAK | TAK | TAK | ||||
przez scalanie | TAK | TAK | TAK | TAK | ||||
szybkie | TAK | TAK | TAK | TAK | ||||
sortowanie pozycyjne | TAK | TAK | TAK | TAK |
W tabeli pomijamy kwestie złożoności czasowej i obliczeniowej. Poświęcamy im czas w sekcji „Symulacja interaktywna”.
Dokładne wyjaśnienie, czym charakteryzują się kolejne kryteria podziału, znajdziesz w e‑materiale Wstęp do algorytmów sortowaniaWstęp do algorytmów sortowania.
Zastosowanie
Algorytmy sortowania mają szerokie zastosowanie w wielu dziedzinach. Przykładem może być np. statystyka. Załóżmy, że od 2000 r. przeprowadzamy codzienne pomiary warunków meteorologicznych. W celu ich uporządkowania i ułatwienia ewentualnej analizy warto posortować je np. niemalejąco według daty bądź temperatury. W ten sposób prostsze będzie dostrzeganie pewnych prawidłowości oraz trendów, a także wyciąganie z nich wniosków.
Również przy badaniach naukowych algorytmy sortowania mogą być nieocenioną pomocą. Analogicznie do prowadzonych statystyk tutaj również może zajść potrzeba uporządkowania wyników eksperymentu czy badania. Oczywiście sortowanie stosowane jest nie tylko przez specjalistów. Przypomnij sobie swoją ostatnią styczność ze sklepem internetowym. Sortowanie produktów według ceny, średnich ocen czy promocji to dzisiaj standard, ułatwiający poszukiwania upatrzonego przez konsumenta artykułu. Możemy więc stwierdzić, że obecnie każdy z nas ma do czynienia z sortowaniem.
Słownik
instrukcja opisująca ciąg działań mających na celu rozwiązanie ustalonego problemu
algorytm, który przechodzi przez dane sekwencyjnie (element po elemencie) w celu uporządkowania ich w odpowiedniej kolejności
uporządkowanie zbioru danych pod względem wybranych cech elementów tego zbioru
sortowanie, w którym elementy o takiej samej wartości nie zmienią pozycji względem siebie
inaczej in situ; sortowanie, w którym niezależnie od rozmiaru danych wejściowych potrzebna jest stała ilość pamięci komputera
(z łac. iteratio) powtarzanie w pętli tych samych instrukcji aż do spełnienia pewnego warunku
metoda polegająca na podzieleniu problemu na mniejsze, prostsze do rozwiązania podproblemy; po całkowitym rozbiciu problemu oraz rozwiązaniu podproblemów, łączymy je z powrotem w całość i rozwiązujemy cały problem
technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego