Porównania
Zapisy
Scalenia

  • Scalany fragment
  • Porównywane
  • Zapisane z powrotem
  • Dotąd scalone

Więcej o sortowaniu przez scalanie

Sortowanie przez scalanie

Sortowanie przez scalanie to algorytm typu „dziel i zwyciężaj”. Dzieli listę na pół, każdą połowę sortuje w ten sam sposób i scala dwie posortowane połowy, za każdym razem biorąc mniejszą z pierwszych wartości. Zobacz, jak połowy trafiają do rzędu bufora i wracają w kolejności, w dowolnym tempie lub krok po kroku, i licz porównania, zapisy i scalenia. Naciśnij Odtwórz, aby obejrzeć sortowanie, albo Krok i Wstecz, aby przechodzić krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kafelki liczą porównania, zapisy z powrotem do listy i scalenia. 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ć krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
  3. Obserwuj każde scalanie: dwie posortowane połowy schodzą do bufora, a mniejsza z pierwszych wartości wraca w górę, po jednej naraz.

Jak działa sortowanie przez scalanie

Pojedyncza wartość jest już posortowana. Dłuższą listę podziel na dwie połowy i posortuj każdą sortowaniem przez scalanie. Potem je scal: spójrz na pierwszą wartość każdej połowy, przenieś mniejszą do wyniku i powtarzaj, aż obie połowy będą puste. Skoro obie połowy są posortowane, wynik też jest posortowany.

Zawsze n log n

Dzielenie na pół raz za razem daje około log₂ n poziomów, a każdy poziom scaleń zapisuje każdą wartość raz, więc sortowanie wykonuje około n log₂ n zapisów i najwyżej tyle samo porównań. W przeciwieństwie do sortowania bąbelkowego, przez wybieranie i przez wstawianie nie rośnie to jak n², a kolejność listy ma znacznie mniejsze znaczenie. Ceną jest bufor tak długi jak lista. Sortowanie przez scalanie jest też stabilne i dlatego stanowi podstawę sortowania w językach Python i Java.

Często zadawane pytania

Jak działa sortowanie przez scalanie?

Dzieli listę na pół, sortuje każdą połowę sortowaniem przez scalanie i scala dwie posortowane połowy, za każdym razem biorąc mniejszą z ich pierwszych wartości. Lista z jedną wartością jest już posortowana, więc na niej dzielenie się kończy.

Ile porównań wykonuje sortowanie przez scalanie?

Dla n wartości najwyżej około n log₂ n − n + 1 i co najmniej około połowy n log₂ n. Dla 40 wartości to najwyżej 177. Liczba zapisów z powrotem do listy jest dla danego n zawsze taka sama: jeden na wartość na każdym poziomie scalania.

Dlaczego sortowanie przez scalanie potrzebuje dodatkowej pamięci?

Szybkie scalenie dwóch połów w miejscu jest trudne, więc zwykłe sortowanie przez scalanie kopiuje połowy do bufora i zapisuje je z powrotem w kolejności. Bufor jest tak długi jak lista i to główna wada w porównaniu z sortowaniem szybkim i przez kopcowanie.

Czy sortowanie przez scalanie jest stabilne?

Tak. Gdy dwie pierwsze wartości są równe, najpierw idzie ta z lewej połowy, więc równe wartości zachowują pierwotną kolejność.

Czy moje liczby są gdzieś wysyłane?

Nie. Sortowanie działa w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora