Sortowanie przez scalanie to jeden z podstawowych algorytmów informatyki, sformułowany w 1945 roku przez wielkiego matematyka Johna von Neumanna. Uczestnicząc w Projekcie Manhattan Neumann stanął przed koniecznością wydajnego przetwarzania ogromnych ilości danych. Opracowana przez niego metoda wykorzystywała zasadę „dziel i rządź”, co znacznie skróciło czas pracy.
Zasada i zastosowanie algorytmu
Metoda sortowania przez scalanie jest używana w problemach z sortowaniem struktur, które mają uporządkowany dostęp do elementów, takich jak tablice, listy, strumienie.
Podczas przetwarzania początkowy blok danych jest dzielony na małe komponenty, do jednego elementu, który w rzeczywistości jest już posortowaną listą. Następnie jest ponownie składany we właściwej kolejności.
Sortowanie tablicy o określonej długości wymaga dodatkowego obszaru pamięci o tym samym rozmiarze, w którym posortowana tablica jest gromadzona w częściach.
Metody można użyć do uporządkowania dowolnego porównywalnego typu danych, takiego jak liczby lub ciągi.
Scalanie posortowanedziałki
Aby zrozumieć algorytm, zacznijmy jego analizę od końca - od mechanizmu scalania posortowanych bloków.
Wyobraźmy sobie, że mamy dwie tablice liczb posortowane w dowolny sposób, które muszą być ze sobą połączone, aby sortowanie nie zostało przerwane. Dla uproszczenia posortujemy liczby w kolejności rosnącej.
Elementarny przykład: obie tablice składają się z jednego elementu każda.
int przyp1={31}; int arr2={18};
Aby je scalić, musisz wziąć element zero z pierwszej tablicy (nie zapomnij, że numeracja zaczyna się od zera) i element zero z drugiej tablicy. Są to odpowiednio 31 i 18. Zgodnie z warunkiem sortowania liczba 18 powinna być pierwsza, ponieważ jest mniejsza. Po prostu umieść liczby we właściwej kolejności:
int wynik={18, 31};
Spójrzmy na bardziej skomplikowany przykład, w którym każda tablica składa się z kilku elementów:
int arr1={2, 17, 19, 45}; int tab2={5, 6, 21, 30};
Algorytm scalania będzie polegał na sekwencyjnym porównywaniu mniejszych elementów i umieszczaniu ich w wynikowej tablicy we właściwej kolejności. Aby śledzić aktualne indeksy, wprowadźmy dwie zmienne - index1 i index2. Początkowo ustawiamy je na zero, ponieważ tablice są posortowane, a najmniejsze elementy znajdują się na początku.
int indeks1=0; int indeks2=0;
Napiszmy cały proces scalania krok po kroku:
- Pobierz element o indeksie1 z tablicy arr1, a element o indeksie2 z tablicy arr2.
- Porównaj, wybierz najmniejsze z nich i wstawwynikowa tablica.
- Zwiększ bieżący indeks mniejszego elementu o 1.
- Kontynuuj od pierwszego kroku.
Na pierwszej orbicie sytuacja będzie wyglądać tak:
indeks1=0; indeks2=0; arr1[0]=2; arr2[0]=5; przyp1[0] < przyp2[0]; indeks1++; wynik[0]=arr1[0]; // wynik=[2]
W drugiej turze:
indeks1=1; indeks2=0; arr1[1]=17; arr2[0]=5; przyp1[1] > przyp2[0]; indeks2++; wynik[1]=arr2[0]; // wynik=[2, 5]
Po trzecie:
indeks1=1; indeks2=1; arr1[1]=17; arr2[1]=6; przyp1[1] > przyp2[1]; indeks2++; wynik[2]=arr2[1]; // wynik=[2, 5, 6]
I tak dalej, aż wynikiem będzie całkowicie posortowana tablica: {2, 5, 6, 17, 21, 19, 30, 45}.
Pewne trudności mogą powstać w przypadku łączenia tablic o różnych długościach. Co się stanie, jeśli jeden z bieżących indeksów osiągnął ostatni element, a druga tablica nadal zawiera elementy?
int przyp1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 krok indeks1=0, indeks2=0; 1 2 wynik={1, 2}; // 3-stopniowy indeks1=1, indeks2=1; 4 < 5 wynik={1, 2, 4}; //4 stopnie indeks1=2, indeks2=1 ??
Zmienna index1 osiągnęła wartość 2, ale tablica arr1 nie zawiera elementu o tym indeksie. Tutaj wszystko jest proste: wystarczy przenieść pozostałe elementy drugiej tablicy do wynikowej, zachowując ich kolejność.
wynik={1, 2, 4, 5, 6, 7, 9};
Ta sytuacja wskazuje nam na potrzebędopasuj bieżący indeks sprawdzania do długości scalanej tablicy.
Schemat łączenia uporządkowanych sekwencji (A i B) o różnych długościach:
- Jeśli długość obu sekwencji jest większa niż 0, porównaj A[0] i B[0] i przenieś mniejszą do bufora.
- Jeżeli długość jednej z sekwencji wynosi 0, weź pozostałe elementy drugiej sekwencji i bez zmiany ich kolejności przejdź na koniec bufora.
Realizacja drugiego etapu
Przykład łączenia dwóch posortowanych tablic w Javie jest podany poniżej.
int a1=nowy int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nowy int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=nowy int[a1.długość + a2.długość]; int i=0, j=0; for (int k=0; k a1.długość-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Tutaj:
- a1 i a2 to oryginalne posortowane tablice, które mają zostać połączone;
- a3 – ostatnia tablica;
- i oraz j są indeksami bieżących elementów dla tablic a1 i a2.
Pierwszy i drugi warunek if zapewniają, że indeksy nie wykraczają poza rozmiar tablicy. Bloki trzeciego i czwartego warunku są odpowiednio przenoszone do wynikowej tablicy mniejszego elementu.
Dziel i zwyciężaj
Więc nauczyliśmy się łączyć posortowanezbiory wartości. Można powiedzieć, że druga część algorytmu sortowania przez scalanie - samo scalenie - została już posortowana.
Jednak nadal musisz zrozumieć, jak przejść z oryginalnej nieposortowanej tablicy liczb do kilku posortowanych, które można połączyć.
Rozważmy pierwszy etap algorytmu i nauczmy się rozdzielać tablice.
To nie jest trudne - oryginalna lista wartości jest podzielona na pół, następnie każda część jest również rozwidlona i tak dalej, aż do uzyskania bardzo małych bloków.
Długość takich minimalnych elementów może być równa jeden, co oznacza, że same mogą być posortowaną tablicą, ale nie jest to warunek konieczny. Rozmiar bloku jest określany z góry, a do jego uporządkowania można użyć dowolnego odpowiedniego algorytmu sortowania, który działa wydajnie z tablicami o małych rozmiarach (na przykład sortowanie szybkie lub sortowanie przez wstawianie).
Wygląda tak.
// oryginalna tablica {34, 95, 10, 2, 102, 70}; // pierwszy podział {34, 95, 10} i {2, 102, 70}; // drugi podział {34} i {95, 10} i {2} i {102, 70}
Wynikowe bloki, składające się z 1-2 elementów, są bardzo łatwe do ułożenia.
Następnie musisz scalić już posortowane małe tablice w pary, zachowując kolejność członków, którą już nauczyliśmy się robić.
Realizacja pierwszego etapu
Rekursywne partycjonowanie tablicy jest pokazane poniżej.
unieważnij mergeSort(T a, długi początek, długi koniec) { długi podział; jeśli(start < finisz) { split=(start + finisz)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); scalanie(a, start, split, finish); } }
Co dzieje się w tym kodzie:
-
Funkcja mergeSort pobiera początkową tablicę
a
oraz lewą i prawą granicę regionu do posortowania (indeksy start i
- finish).
-
Jeśli długość tej sekcji jest większa niż jeden (
start < finish
), to jest ona podzielona na dwie części (według indeksu
- split), a każdy z nich jest sortowany rekurencyjnie.
-
W wywołaniu funkcji rekurencyjnej dla lewej strony, przekazywany jest indeks początkowy wykresu i indeks
split
. Dla prawej, odpowiednio, początek będzie miał postać
- (podział + 1), a koniec będzie ostatnim indeksem oryginalnej sekcji.
-
Funkcja
merge
pobiera dwie uporządkowane sekwencje (
a[start]…a[split]
i
- a[split +1]…a[finish]) i łączy je w kolejności sortowania.
Mechanika funkcji scalania została omówiona powyżej.
Ogólny schemat algorytmu
Metoda tablicy sortowania przez scalanie składa się z dwóch dużych kroków:
- Podziel nieposortowaną oryginalną tablicę na małe części.
- Zbierz je w pary, zgodnie z regułą sortowania.
Duże i złożone zadanie jest podzielone na wiele prostych, które są kolejno rozwiązywane, co prowadzi do pożądanego rezultatu.
Ocena metody
Złożoność czasowa sortowania przez scalanie jest określona przez wysokość podzielonego drzewaalgorytm i jest równa liczbie elementów w tablicy (n) razy jej logarytm (log n). Takie oszacowanie nazywa się logarytmicznym.
Jest to zarówno zaleta, jak i wada metody. Jego czas działania nie zmienia się nawet w najgorszym przypadku, gdy oryginalna tablica jest sortowana w odwrotnej kolejności. Jednak podczas przetwarzania całkowicie posortowanych danych algorytm nie zapewnia oszczędności czasu.
Ważne jest również, aby zwrócić uwagę na koszt pamięci metody sortowania przez scalanie. Są równe rozmiarem oryginalnej kolekcji. W tym dodatkowo przydzielonym obszarze, posortowana tablica jest składana z kawałków.
Wdrożenie algorytmu
Sortowanie przez scalanie Pascal jest pokazane poniżej.
Procedura MergeSort(nazwa: ciąg; var f: tekst); Var a1, a2, s, i, j, kol, tmp: liczba całkowita; f1, f2: tekst; b: logiczne Rozpocznijkol:=0; Przypisz(f, nazwa); reset(f); Chociaż nie EOF(f) zacznij czytać(f, a1); wz(kol); koniec; zamknij(f); Assign(f1, '{nazwa pierwszego pliku pomocniczego}'); Assign(f2, '{nazwa drugiego pliku pomocniczego}'); s:=1; Podczas gdy (s<kol) zaczyna się Reset(f); przepisać(f1); przepisz (f2); Dla i:=1 do kol div 2 zacznij Read(f, a1); Napisz(f1, a1, ' '); koniec; Jeśli (kol div 2) mod s0 to zacznij tmp:=kol div 2; Podczas gdy tmp mod s0 zaczyna się Read(f, a1); Napisz(f1, a1, ' '); przyw(tmp); koniec; koniec; Chociaż nie EOF(f) rozpocznij Read(f, a2); Napisz(f2, a2, ' '); koniec; zamknij(f); zamknij(f1); zamknij(f2); przepisać(f); reset (f1); reset (f2); Czytaj(f1, a1); Czytaj(f2, a2); Chociaż (nie EOF(f1)) i (nie EOF(f2)) zaczynają się i:=0; j:=0; b:=prawda; Podczas gdy (b) i (nie EOF(f1)) i (nie EOF(f2)) zaczynają się Jeśli (a1<a2) to zaczyna sięNapisz(f, a1, ' '); Czytaj(f1, a1); inc(i); End else begin Write(f, a2, ' '); Czytaj(f2, a2); inc(j); koniec; Jeśli (i=s) lub (j=s) to b:=fałsz; koniec; Jeśli nie b, to zacznij Chociaż (i<s) i (nie EOF(f1)) zaczynają się Write(f, a1, ' '); Czytaj(f1, a1); inc(i); koniec; Chociaż (j<s) i (nie EOF(f2)) zaczynają się Write(f, a2, ' '); Czytaj(f2, a2); inc(j); koniec; koniec; koniec; Chociaż nie EOF(f1), zaczynaj tmp:=a1; Czytaj(f1, a1); Jeśli nie EOF(f1) to Write(f, tmp, ' ') else Write(f, tmp); koniec; Chociaż nie EOF(f2) zaczyna się tmp:=a2; Czytaj(f2, a2); Jeśli nie EOF(f2) to Write(f, tmp, ' ') else Write(f, tmp); koniec; zamknij(f); zamknij(f1); zamknij(f2); s:=s2; koniec; Usuń(f1); Usuń(f2); Koniec;
Widocznie działanie algorytmu wygląda tak (góra - kolejność nieuporządkowana, dół - kolejność).
Sortowanie danych zewnętrznych
Bardzo często zachodzi potrzeba sortowania niektórych danych znajdujących się w zewnętrznej pamięci komputera. W niektórych przypadkach mają imponujące rozmiary i nie można ich umieścić w pamięci RAM, aby ułatwić do nich dostęp. W takich przypadkach używane są zewnętrzne metody sortowania.
Konieczność dostępu do nośników zewnętrznych obniża wydajność czasu przetwarzania.
Złożoność pracy polega na tym, że algorytm może jednocześnie uzyskać dostęp tylko do jednego elementu strumienia danych. I w tym przypadku jeden z najlepszych wyników daje metoda sortowania przez scalanie, która może porównywać elementy dwóch plików sekwencyjnie jeden po drugim.
Odczytywanie danych zźródła zewnętrznego, ich przetwarzanie i zapis do pliku końcowego odbywa się w uporządkowanych blokach (seriach). Zgodnie ze sposobem pracy z wielkością zamówionych serii, istnieją dwa rodzaje sortowania: proste i naturalne łączenie.
Proste scalanie
Dzięki prostemu połączeniu długość serii jest stała.
Tak więc w oryginalnym nieposortowanym pliku wszystkie serie składają się z jednego elementu. Po pierwszym kroku rozmiar zwiększa się do dwóch. Dalej - 4, 8, 16 i tak dalej.
Działa tak:
- Plik źródłowy (f) jest podzielony na dwa pomocnicze - f1, f2.
- Są one ponownie połączone w jeden plik (f), ale jednocześnie wszystkie elementy są porównywane w parach i parach formularzy. Rozmiar serii na tym etapie wynosi dwa.
- Krok 1 jest powtarzany.
- Krok 2 jest powtarzany, ale już uporządkowane dwójki są scalane w posortowane czwórki.
- Pętla jest kontynuowana, zwiększając serię w każdej iteracji, aż cały plik zostanie posortowany.
Skąd wiesz, że sortowanie zewnętrzne z prostym scaleniem zostało zakończone?
- długość nowej serii (po połączeniu) nie mniejsza niż całkowita liczba elementów;
- został tylko jeden odcinek;
- Plik pomocniczy f2 pozostał pusty.
Wady prostego scalania są następujące: ponieważ długość przebiegu jest ustalona w każdym przebiegu scalania, częściowo uporządkowane dane będą przetwarzane tak długo, jak dane całkowicie losowe.
Naturalna fuzja
Ta metoda nie ogranicza długościseria, ale wybiera maksymalną możliwą.
Algorytm sortowania:
- Czytanie początkowej sekwencji z pliku f. Pierwszy odebrany element jest zapisywany w pliku f1.
- Jeżeli następny wpis spełnia warunek sortowania, jest tam zapisywany, jeśli nie, to do drugiego pliku pomocniczego f2.
- W ten sposób wszystkie rekordy pliku źródłowego są dystrybuowane, a uporządkowana sekwencja jest tworzona w f1, która określa bieżący rozmiar serii.
- Pliki f1 i f2 są połączone.
- Cykl się powtarza.
Ze względu na niestały rozmiar serii konieczne jest oznaczenie końca sekwencji specjalnym znakiem. Dlatego podczas łączenia zwiększa się liczba porównań. Ponadto rozmiar jednego z plików pomocniczych może być zbliżony do rozmiaru oryginału.
Naturalne scalanie jest średnio wydajniejsze niż proste scalanie z sortowaniem zewnętrznym.
Cechy algorytmu
Porównując dwie identyczne wartości, metoda zachowuje ich pierwotną kolejność, czyli jest stabilna.
Proces sortowania można z powodzeniem podzielić na wiele wątków.
Film wyraźnie pokazuje działanie algorytmu sortowania przez scalanie.
