Dokumentacja, która została przedstawiona, dotyczy algorytmu sortowania
| To prosta metoda sortowania opierająca się na cyklicznym porównywaniu par sąsiadujących ze sobą elementów i zamianie ich miejscami w przypadku, kiedy kryterium porządkowe zbioru nie zostanie spełnione. Operacje te wykonywane są dopóki występują zmiany, czyli tak długo, aż cały zbiór zostanie posortowany. |
Opisany w pytaniu algorytm to właśnie sortowanie bąbelkowe (ang. bubble sort). Polega ono na wielokrotnym przechodzeniu przez zbiór danych i zamienianiu miejscami sąsiadujących elementów, jeśli są w złej kolejności. Czynność ta powtarzana jest do momentu, gdy cały zbiór zostanie uporządkowany i żadne zamiany nie będą już potrzebne. Moim zdaniem, to chyba jeden z najbardziej intuicyjnych algorytmów sortowania, jakie się poznaje na początku nauki programowania – łatwo go zaimplementować, bo wymaga właściwie tylko dwóch pętli i porównania sąsiednich elementów. W praktyce bubble sort raczej rzadko używa się w profesjonalnych projektach, bo jego złożoność czasowa to O(n^2), co przy dużych zbiorach jest nieefektywne. Jednak czasami, na bardzo małych listach albo gdy szybko trzeba zrobić prosty prototyp, to można sięgnąć po „bąbelki”. Z mojego doświadczenia wynika też, że sortowanie bąbelkowe dobrze obrazuje podstawowe zasady algorytmiki, na przykład jak działa iteracja czy wymiana miejscami zmiennych – to przydatne w nauce. W wielu językach programowania, nawet tych nowoczesnych, można spotkać przykłady z bubble sort jako ilustrację podstaw. To taki klasyk – mało kto używa go zawodowo, ale każdy programista powinien wiedzieć, jak działa. Warto też pamiętać, że istnieją optymalizacje bubble sortu, np. wcześniejsze zakończenie, gdy w danej iteracji nie wystąpiła żadna zamiana. No i taka ciekawostka: choć algorytm nie jest specjalnie szybki, to bardzo łatwo go zaimplementować nawet w językach niskopoziomowych, bo nie wymaga dodatkowej pamięci.
Opis w pytaniu jednoznacznie wskazuje na sortowanie bąbelkowe, a nie szybkie (quicksort), przez wybór czy przez wstawianie. Wiele osób daje się zwieść terminologii lub myli charakterystyczne cechy poszczególnych algorytmów, bo przecież wszystkie mają na celu uporządkowanie danych. Jeśli chodzi o quicksort, to działa on zupełnie inaczej – opiera się na wyborze tzw. pivota (elementu głównego), a następnie dzieli tablicę na dwie części: mniejsze i większe od tego elementu. Proces ten jest rekurencyjny i nie polega na cyklicznym porównywaniu jedynie sąsiadujących elementów, tylko na podziale i sortowaniu podtablic. Z mojego doświadczenia wynika, że quicksort jest znacznie wydajniejszy (średnio O(n log n)), ale już implementacyjnie bardziej złożony. Z kolei sortowanie przez wybór (selection sort) polega na znajdowaniu na każdym przebiegu najmniejszego (lub największego) elementu i umieszczaniu go na właściwej pozycji. Nie ma tu zamiany sąsiadujących elementów w kółko – to raczej systematyczne przesuwanie wybranego elementu do przodu zbioru. Sortowanie przez wstawianie (insertion sort) przypomina układanie kart – bierzesz kolejne elementy i wstawiasz je w odpowiednie miejsce w już częściowo posortowanej liście. Tutaj znowu nie chodzi o ciągłe zamienianie miejscami sąsiednich elementów podczas każdego przebiegu, tylko o przesuwanie elementów do przodu aż do znalezienia właściwej pozycji. Typowym błędem jest sugerowanie się słowem „prosta metoda” i mylenie jej z insertion sort, bo oba algorytmy są faktycznie czytelne, ale sposób działania mają kompletnie inny. Branżowe dobre praktyki podpowiadają, by dobrać algorytm do konkretnego problemu – bąbelkowy przydaje się do pokazania podstaw, ale rzadko bywa praktyczny przy dużych zbiorach. Dlatego dokładne czytanie opisu i rozróżnianie tych subtelnych różnic w działaniu algorytmów jest bardzo ważne, szczególnie przy zadaniach rekrutacyjnych czy na egzaminach zawodowych.