Zawartość
Zamawianie zestawu elementów na liście jest częstym zadaniem w programowaniu. Często człowiek może wykonać to zadanie intuicyjnie. Jednak program komputerowy musi wykonać dokładną sekwencję instrukcji, aby ją ukończyć, a ta sekwencja nazywana jest algorytmem. Algorytm porządkujący to metoda służąca do umieszczania listy zdezorganizowanych pozycji w określonej kolejności. Kolejność zamawiania określa klucz. Istnieje kilka algorytmów sortowania różniących się wydajnością i wydajnością. Niektóre znane i ważne tego typu to: sortowanie bąbelkowe, sortowanie przez wybieranie, sortowanie przez wstawianie i sortowanie szybkie.
Sortowanie bąbelkowe
Sortowanie bąbelkowe wielokrotnie wymienia sąsiednie elementy, które nie są uporządkowane, dopóki cała lista elementów nie jest w kolejności. W ten sposób elementy unoszą się na liście zgodnie z ich wartościami, przy czym największe (w przypadku kolejności rosnącej) kończą się po każdej iteracji.
Główną zaletą tego algorytmu jest to, że jego implementacja jest łatwa i znana. Ponadto w przypadku sortowania bąbelkowego elementy są zamieniane miejscami bez tymczasowego składowania, co sprawia, że wymagana przestrzeń jest minimalna. Główną wadą jest to, że nie daje dobrych wyników, gdy lista zawiera wiele pozycji. Dzieje się tak, ponieważ ten rodzaj sortowania wymaga n² etapów przetwarzania na każde n liczby sortowanych elementów. Dlatego sortowanie bąbelkowe nadaje się do edukacji akademickiej, ale nie do zastosowań w życiu codziennym.
Sortowanie przez wybór
Sortowanie przez wybieranie wielokrotnie przeszukuje listę pozycji, wybierając po jednym elemencie na raz i umieszczając go we właściwej pozycji w sekwencji.
Główną zaletą sortowania przez wybieranie jest to, że działa dobrze na krótkiej liście. Ponadto, ponieważ jest to algorytm porządkujący, nie wymaga tymczasowego przechowywania poza tym, co jest niezbędne do przechowywania oryginalnej listy. Główną wadą jest niska skuteczność na dużych listach. Podobnie jak sortowanie bąbelkowe, wymaga n² liczby kroków dla każdego n elementów. Dodatkowo na jego wydajność łatwo wpływa początkowa kolejność artykułów przed sortowaniem. Z tego powodu ten typ wyboru jest odpowiedni tylko dla listy, na której kilka elementów jest w losowej kolejności.
Sortowanie przez wstawianie
Sortowanie przez wstawianie wielokrotnie skanuje listę i za każdym razem wstawia element z nieuporządkowanej sekwencji we właściwe miejsce.
Główną zaletą sortowania przez wstawianie jest jego prostota, a także dobre wyniki na małych listach. Jest to algorytm składania zamówień, więc zapotrzebowanie na miejsce jest minimalne. Wadą jest to, że nie działa tak dobrze, jak inne algorytmy sortowania. Ponieważ do działania potrzeba n² kroków, sortowanie przez wstawianie nie działa również dobrze w przypadku dużych list. Jest to jednak szczególnie przydatne w przypadku list kilku elementów.
Szybkie sortowanie
Szybkie sortowanie działa na zasadzie podziału i podboju. Najpierw dzieli listę pozycji na dwie listy podrzędne w oparciu o element przestawny. Wszystkie elementy z pierwszej podlisty są ułożone tak, że są mniejsze niż oś obrotu, podczas gdy wszystkie elementy z drugiej podlisty są ustawione tak, aby były większe niż oś. Ten sam proces podziału na partycje i organizacji jest wykonywany wielokrotnie na wynikowych listach podrzędnych, aż do uporządkowania całej listy.
Szybkie sortowanie jest uważane przez niektórych za najlepszy algorytm sortowania ze względu na jego znaczną przewagę pod względem wydajności, ponieważ działa dobrze z dużą listą elementów. Zamawiając na miejscu, nie ma również potrzeby dodatkowego miejsca do przechowywania. Niewielką wadą, jaką przedstawia, jest to, że jego najgorsza wydajność jest podobna do średniej wydajności innych algorytmów opisanych powyżej. Należy jednak zauważyć, że ten najgorszy przypadek jest bardzo rzadki. Mówiąc bardziej ogólnie, szybkie sortowanie daje najbardziej wydajną i szeroko stosowaną metodę organizowania listy o dowolnej wielkości.
