- Scalany fragment
- Porównywane
- Zapisane z powrotem
- Dotąd scalone
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
- 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ć krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
- 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