Porównania
Zamiany
Przebieg

  • Porównywane
  • Zamienione
  • Na miejscu

Więcej o sortowaniu bąbelkowym

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

  1. 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.
  2. 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.
  3. 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