Struktury danych i algorytmy
(Część druga — Sortowanie)
„W pierwszej części” naszej eksploracji struktur danych i algorytmów dowiedzieliśmy się, że użycie posortowanej tablicy zapewnia nam większą elastyczność w przypadku zadań takich jak wyszukiwanie, zmienianie lub usuwanie elementów. Staje się to cenne, gdy mamy do czynienia z wieloma elementami, które są powszechne w naszych codziennych działaniach. Ponieważ te akcje są często używane, istotne jest, aby poświęcić trochę czasu na omówienie algorytmów sortowania, szczególnie w przypadku tablic nieuporządkowanych.
Artykuł będzie miał następującą strukturę:
Jak byś to zrobił?
Sortowanie bąbelkowe
Sortowanie przez wybór
Sortowanie przez wstawianie
Jak byś to zrobił?
Jako osoba masz przewagę nad programem komputerowym. Możesz obejrzeć wszystkie dzieci na raz i szybko wybrać najwyższe, bez konieczności mierzenia i porównywania każdego z nich.
Po nieformalnej zmianie położenia możesz z łatwością ustawić wszystkie dzieci w linii, jak pokazano na ilustracji.
Jednak program komputerowy nie może przetwarzać danych w ten sam sposób. Ze względu na sposób działania operatorów porównania może porównywać tylko dwoje dzieci na raz. Ta ograniczona perspektywa jest częstym tematem algorytmów. Chociaż dla ludzi wszystko może wydawać się proste, algorytmy nie są w stanie zobaczyć ogólnego obrazu sytuacji. Zamiast tego skupiają się na konkretnych szczegółach i przestrzegają prostych zasad.
Trzy algorytmy opisane w tym rozdziale wykonują wielokrotnie dwa kroki, aż dane zostaną posortowane
Sortowanie bąbelkowe
Sortowanie bąbelkowe to prosty algorytm sortowania, który wielokrotnie przegląda listę elementów i porównuje sąsiednie elementy, zamieniając je, jeśli są w niewłaściwej kolejności. Nazywa się to „sortowaniem bąbelkowym”, ponieważ mniejsze elementy „bąbelkują” na górze listy, podczas gdy większe elementy „opadają” na dół.
Oto jak działa sortowanie bąbelkowe:
- Zacznij od porównania dwóch pierwszych elementów listy. Jeśli pierwszy element jest większy niż drugi, zamień je.
- Przejdź do kolejnej pary elementów i porównaj je. Ponownie zamień, jeśli to konieczne.
- Kontynuuj ten proces dla całej listy, wielokrotnie porównując i zamieniając sąsiednie elementy, aż nie będą już potrzebne żadne zamiany.
- Po jednokrotnym przejrzeniu listy największy element „wypłynie” na ostatnią pozycję. Powtórz proces dla pozostałych nieposortowanych elementów.
- Powtarzaj kroki 1–4, aż cała lista zostanie posortowana.
Sortowanie bąbelkowe jest łatwe do zrozumienia i wdrożenia, ale nie jest zbyt wydajne w przypadku dużych list. Jego średnia i najgorsza złożoność czasowa wynosi O(n²), gdzie „n” to liczba elementów na liście. To sprawia, że sortowanie dużych zbiorów danych jest niepraktyczne. Może to być jednak doskonały wybór w przypadku małych list lub jako ćwiczenie uczące zrozumienia algorytmów sortowania.
Sortowanie przez wybór
Sortowanie przez wybór to prosty algorytm sortowania, który polega na wielokrotnym wybieraniu minimalnego (lub maksymalnego) elementu z nieposortowanej części tablicy i umieszczaniu go na początku (lub końcu) posortowanej części. Ma złożoność czasową O(n²) dla średnich i najgorszych scenariuszy, co czyni go nieefektywnym w przypadku dużych list.
Oto jak działa algorytm sortowania przez wybór:
- Znajdź minimalny (lub maksymalny) element w nieposortowanej części tablicy.
- Zamień go z pierwszym elementem nieposortowanej części.
- Powtórz powyższe kroki dla pozostałej nieposortowanej części tablicy, wyłączając element, który właśnie został umieszczony w posortowanej części.
Sortowanie przez wybór nazywa się tak, ponieważ „wybiera” najmniejszy (lub największy) element i „przewija” go do właściwej pozycji w posortowanej części tablicy. Pomimo swojej prostoty, sortowanie przez wybór nie jest efektywne w przypadku dużych tablic ze względu na jego kwadratową złożoność czasową.
W przeciwieństwie do niektórych innych algorytmów sortowania, takich jak sortowanie bąbelkowe, sortowanie przez wybór nie wymienia w sposób ciągły elementów podczas skanowania tablicy. Ta cecha może być korzystna w sytuacjach, gdy wymiana elementów jest kosztowna.
Sortowanie przez wstawianie
Sortowanie przez wstawianie to prosty algorytm sortowania, który tworzy ostateczną posortowaną tablicę po jednym elemencie na raz. Jest to algorytm sortowania oparty na porównaniach, w którym tablica jest dzielona na część posortowaną i nieposortowaną. W każdej iteracji algorytm pobiera element z nieposortowanej części i wstawia go we właściwe miejsce w posortowanej części.
Oto jak działa sortowanie przez wstawianie:
- Zacznij od drugiego elementu (indeks 1) i porównaj go z pierwszym elementem (indeks 0).
- Jeśli drugi element jest mniejszy (lub większy, w zależności od kolejności sortowania) niż pierwszy element, zamień je.
- Przejdź do trzeciego elementu (indeks 2) i porównaj go z poprzednimi elementami w posortowanej części. Wstaw go w odpowiednim miejscu w posortowanej części, przesuwając większe elementy w prawo.
- Powtórz proces dla pozostałych nieposortowanych elementów, za każdym razem wstawiając bieżący element na właściwe miejsce w posortowanej części.
Sortowanie przez wstawianie jest efektywne w przypadku małych zbiorów danych lub częściowo posortowanych tablic. Ma liniową złożoność czasową O (n) dla posortowanych tablic. Jednak jego złożoność czasowa w najgorszym przypadku jest kwadratowa, co czyni go mniej odpowiednim dla dużych tablic.
Podsumowując, sortowanie przez wstawianie to prosty algorytm sortowania, który jest łatwy do zrozumienia i wdrożenia. Chociaż może to nie być najskuteczniejszy wybór w przypadku dużych zbiorów danych, może być praktyczną opcją w przypadku małych lub posortowanych tablic.
