- Porównywane
- Zamienione
- Na miejscu
Sortowanie bąbelkowe
Sortowanie bąbelkowe raz za razem przechodzi przez listę, porównuje każdą parę sąsiadów i zamienia je, gdy lewy jest większy. Po każdym przebiegu największa wartość, która nie jest jeszcze na miejscu, „wypływa” na koniec. Odtwarzaj sortowanie z dowolną prędkością albo przechodź przez nie po jednym porównaniu i obserwuj liczniki porównań, zamian i przebiegów. Naciśnij Odtwórz, aby obejrzeć sortowanie, albo Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kafelki liczą porównania, zamiany i przebiegi. Wybierz liczbę słupków, ich początkowy układ albo wpisz własne liczby. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja uruchamia i wstrzymuje, a Home i End przenoszą na początek i na koniec.
Jak to działa
- Wybierz liczbę słupków i ich początkowy układ: losowy, prawie posortowany, odwrócony lub z kilkoma różnymi wartościami. Możesz też wpisać własne liczby.
- Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
- Obserwuj, jak kafelki liczą porównania, zamiany i przebiegi, i porównaj je z najgorszym przypadkiem.
Jak działa sortowanie bąbelkowe
Zacznij od lewej. Porównaj dwie pierwsze wartości; jeśli lewa jest większa, zamień je. Przesuń się o jedno miejsce w prawo i porównaj znowu, aż do końca listy. To jeden przebieg, po którym największa wartość jest na ostatnim miejscu. Następny przebieg kończy się o jedno miejsce wcześniej. Kontynuuj, aż przebieg nie wykona żadnej zamiany albo zostanie tylko jedna wartość.
Ile to pracy
Dla n wartości pierwszy przebieg wykonuje n − 1 porównań, następny n − 2 i tak dalej, więc pełne sortowanie to najwyżej n(n − 1)/2 porównań. Liczba zamian zawsze równa się liczbie inwersji w liście początkowej, czyli par wartości w złej kolejności. Najwięcej ma ich lista odwrócona: n(n − 1)/2. Lista posortowana nie ma żadnych i dzięki wczesnemu zatrzymaniu wymaga jednego przebiegu z n − 1 porównaniami.
Często zadawane pytania
Skąd nazwa sortowanie bąbelkowe?
Duże wartości wędrują na koniec listy jak bąbelki w wodzie. W każdym przebiegu największa wartość, która nie jest jeszcze na miejscu, przesuwa się krok po kroku w prawo, aż dotrze na swoje ostateczne miejsce.
Ile porównań i zamian wykonuje sortowanie bąbelkowe?
Najwyżej n(n − 1)/2 porównań dla n wartości: 45 dla 10 wartości, 780 dla 40. Liczba zamian zawsze równa się liczbie inwersji w liście początkowej: od zera dla listy posortowanej do n(n − 1)/2 dla odwróconej.
Co daje wczesne zatrzymanie?
Jeśli cały przebieg nie wykona żadnej zamiany, każda para sąsiadów jest w dobrej kolejności, więc lista jest posortowana i można skończyć. Z włączonym wczesnym zatrzymaniem posortowana lista wymaga jednego przebiegu. Bez niego sortowanie bąbelkowe zawsze wykonuje wszystkie n − 1 przebiegów.
Czy sortowanie bąbelkowe stosuje się w praktyce?
Rzadko. Jest proste i stabilne, ale średnio działa w czasie proporcjonalnym do n². Sortowanie przez wstawianie robi to samo w mniejszej liczbie kroków na krótkich lub prawie posortowanych listach, a sortowanie przez scalanie i quicksort są dużo szybsze na długich.
Czy moje liczby są gdzieś wysyłane?
Nie. Sortowanie działa w przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora