[MUZYKI] 

DOUG LLOYD: OK, więc scalanie jakby to kolejny algorytm które możemy wykorzystać do uporządkowania elementy tablicy. Ale jak zobaczymy, to dostał bardzo zasadnicza różnica od wyboru sortowania, bańki sortowanie i Sortowanie przez wstawianie które sprawiają, że naprawdę bardzo mądre. 

Podstawową ideą scalania sortowania jest sortowanie mniejsze tablice a następnie połączyć te tablice razem, lub połączyć them-- stąd name-- posortowanych. Sposób, że sortowanie przez scalanie robi to jest, wykorzystując narzędzie nazywa rekurencji, która jest co będziemy mówić o szybko, ale my naprawdę nie rozmawialiśmy o jeszcze. 

Oto Podstawową ideą łączenia rodzaju. Sortuj lewą połowę tablicy, przy założeniu, że N jest większe niż 1. I co mam na myśli, kiedy mówię, przy założeniu, że N jest większe niż 1, Myślę, że możemy się zgodzić, że jeśli tablicy składa się tylko z jednego elementu, to jest klasyfikowane. My nie faktycznie trzeba zrobić coś do niego. Możemy po prostu oświadczyć, że mają być posortowane. To tylko jeden element. 

Tak więc pseudocode znowu jest sortować lewą połowę tablicy, następnie posortować prawa połowa tablica, następnie połączyć dwie połówki razem. Teraz już możesz być myślenia, to niby tylko Brzmi, jakbyś odwlekania the-- nie jesteś rzeczywiście robi nic. Mówisz posortować lewo połowa, sortowania prawą połowę, ale nie mówisz mi, jak to robisz. 

Ale pamiętaj, że tak długo, jak tablica jest pojedynczy element, możemy zadeklarować załatwiania. Wtedy możemy po prostu połączyć je razem. I to jest rzeczywiście podstawową ideą łączenia rodzaju, jest rozbicie go tak, że Twoje tablice są wielkości jednego. A potem odbudować stamtąd. 

Sortowanie przez scalanie jest zdecydowanie skomplikowany algorytm. I to jest też trochę skomplikowanych wizualizacji. Więc mam nadzieję, wizualizacja, że tu pomoże podążać. A ja spróbuję opowiedzieć rzeczy i przejść przez to trochę bardziej wolniej niż inne po prostu mam nadzieję, że się głowę wokół idei za sortowanie przez scalanie. 

Mamy więc taką samą tablicę jako Algorytm sortowania filmy inne jeśli widziałem them-- tablica sześciu elementów. A nasz kod pseudokod tutaj jest swego lewą połowę, sortowania prawą połowę, połączyć dwie połówki razem. Więc weźmy to bardzo ciemny ceglasty Tablica i sortować lewą połowę. 

Więc na razie, jedziemy ignorować rzeczy po prawej stronie. To tam, ale jesteśmy jeszcze nie w tym kroku. Nie jesteśmy w posortować Prawa połowa tablicy. Jesteśmy w rodzaju z lewej połowa macierzy. I właśnie ze względu bycia trochę więcej jasne, więc mogę polecić do tego, co mamy na krok, Mam zamiar przełączyć Kolor ten zestaw do pomarańczy. Teraz, my wciąż mówimy o same lewej połowie oryginalnej macierzy. Ale mam nadzieję, że będąc w stanie odnoszą się do kolorów różnych elementów, będzie to zrobić to trochę więcej jasne, co się tutaj dzieje. 

OK, więc teraz mamy trzy element tablicy. W jaki sposób uporządkować lewą połowę tego Tablica, która jest wciąż ten krok? Staramy się rozwiązać w lewo połowa z cegły czerwonej array-- którego lewa połowa Mam teraz w kolorze pomarańczowym. 

Cóż, możemy spróbować powtórzyć ten proces ponownie. Tak więc nadal jesteśmy w Środek próbuje uporządkować lewa połowa pełnego tablicy. Lewa połowa tablica, jestem po prostu arbitralnie zdecydować, że lewa połowa będzie mniejsza niż prawej połowie bo to się dzieje składa się z trzech elementów. 

I tak mam zamiar powiedzieć, że Lewa połowa lewej połowy tablicy jest po prostu elementem pięć. Pięć, jest pojedynczy element tablica, wiemy, jak go rozwiązać. I tak pięć jest posortowana. Jesteśmy po prostu się do stwierdzenia, że. To jeden element tablicy. 

Więc my teraz posortowane Lewa połowa lewej half-- czy raczej mamy posortowane lewa połowa pomarańczy. Więc teraz, aby jeszcze kompletne lewej połowie całkowitej tablicowej, która, musimy posortować prawą połowę z pomarańczy, lub tych rzeczy. Jak mamy to zrobić? Cóż, mamy tablicę dwóch elementów. Więc możemy posortować lewą połowę tablicy, która jest dwa. Dwa to pojedynczy element. Więc to jest klasyfikowane domyślnie. Wtedy możemy posortować prawą połowę tej części tablicy, jeden. To rodzaj domyślnie. 

To jest pierwszy raz osiągnęliśmy etap scalania. Mamy za sobą, chociaż jesteśmy teraz trochę zagnieżdżone down-- i to jest rodzaj tricky Rzecz z rekursji jest, trzeba, aby utrzymać udać się, gdzie jesteśmy. Tak więc mamy jakby w lewo połowy części pomarańczowej. 

A teraz jesteśmy w środku sortowania prawa połowa części pomarańczowej. I w tym procesie, mają Teraz, który ma być w kroku połączyć dwie połówki razem. Kiedy patrzymy na dwóch połówek tablicy, widzimy dwa do jednego. Który element jest mniejszy? Jeden. 

Następnie, który element jest mniejszy? Cóż, to dwa albo nic. Więc to jest dwa. Więc teraz, po prostu znowu wrobić gdzie jesteśmy w kontekście, mamy posortowane lewa połowa pomarańczowy i prawa połowa pochodzenia. Wiem, że się zmieniłem kolory ponownie, ale to, gdzie byliśmy. A powód to zrobiłem Jest tak, ponieważ proces ten jest zamierza poddawać się, iteracji dół. Mamy klasyfikowane w lewo połowa dawnego pomarańczowy i prawa połowa dawnego pomarańczowy. 

Teraz musimy połączyć te dwie połówki razem też. To krok jesteśmy na. Więc rozważyć wszystkie Elementy, które są teraz zielone, Lewa połowa pierwotnej macierzy. I możemy połączyć te W ten sam sposób zrobiliśmy dla łączenia dwóch i jedną chwilą. 

Lewa połowa, najmniejszy Element na lewej połowie jest pięć. Najmniejszy element prawa połowa jest jeden. Który z nich jest mniejsza? Jeden. 

Najmniejszy element lewa połowa jest pięć. Najmniejszy element prawa połowa jest dwa. Jaka jest najmniejsza? Dwa. I wtedy wreszcie pięć i nic nie możemy powiedzieć, pięć. 

OK, więc duży obraz, niech zrobić sobie przerwę na chwilę i dowiedzieć się, gdzie jesteśmy. Jeśli zaczęliśmy od na samym początku, że zostało zakończone na ogólna tablica tylko krok kodu pseudocode tutaj. Mamy posortowane Lewa połowa tablicy. 

Przypomnijmy, że oryginalny zamówienie było pięć, dwa, jeden. Przechodząc przez ten proces i zagnieżdżenie się i powtarzając, dalszego złamania problem na mniejsze i mniejsze części, mamy teraz zakończone kroku w Pseudokod dla całego układu początkowego. Mamy klasyfikowane jego lewą połowę. 

Więc teraz niech nie zamrażać. A teraz uporządkować prawo połowy oryginalnej macierzy. I mamy zamiar to zrobić poprzez przechodzi przez to samo iteracyjny Proces łamania rzeczy w dół a następnie połączenie ich ze sobą. 

Więc lewa połowa czerwony lub lewa połowa na prawej połowie oryginału tablica, mam zamiar powiedzieć to trzy. Znowu mam być tutaj spójne. Jeśli masz dziwne liczba elementów, to nie ma większego znaczenia, czy dokonać w lewo, jeden mniejszy lub prawy mniejszy. 

Liczy się to, że w każdym przypadku wystąpi ten problem w prowadzeniu scalanie, musisz być spójne. Albo zawsze trzeba dokonać lewa strona mniejsze czy zawsze trzeba zrobić prawa strona mniejsze. Tutaj zdecydowałem się zawsze sprawiają, że lewa strona mniejsze kiedy moja tablica, lub moje sub-macierzy, jest dziwnym rozmiarze. 

Trzy jest pojedynczy element, i tak to jest klasyfikowane. Mamy wykorzystała tego założenia w całym naszym procesie tak daleko. Więc teraz niech uporządkować prawo pół prawej połowie lub prawa połowa czerwieni. 

Ponownie musimy podzielić to w dół. To nie jest pojedynczy element tablicy. Nie możemy oświadczyć, że sortowane. I tak, po pierwsze, będziemy sortowanie lewą połowę. 

Lewa połowa jest pojedynczy element, więc jest to rodzaj domyślnie. Następnie jedziemy do sortowania prawo pół, który jest pojedynczy element. To klasyfikowane domyślnie. I teraz, możemy połączyć te dwa razem. Cztery jest mniejsza, a następnie sześć jest mniejszy. 

Ponownie, co zrobiliśmy w tym momencie? Mamy klasyfikowane w lewo połowę prawą połowę. Lub powrót do oryginału kolory, którzy tam byli, my klasyfikowane w lewo połowa miększego czerwony. Pierwotnie był ciemny cegły czerwony, a teraz jest to bardziej miękkie czerwony, czy to był bardziej miękki czerwony. 

A potem mamy posortowane Prawa połowa miększej czerwieni. Teraz, dobrze, że są zielone znowu, po prostu bo jedziemy przez proces. I musimy powtórzyć to w kółko. 

Więc teraz możemy połączyć te dwie połówki razem. I to jest to, co robimy tutaj. Więc czarnej linii tylko podzielone lewą połowę i prawa połowa tej części sortowania. 

Porównujemy najmniejszą wartość Po lewej stronie array-- i przepraszam, najmniejszy wartość lewej połowie do najmniejszej wartości z prawej połowę, a okaże się, że trzech jest mniejszy. A teraz nieco o optymalizacji, prawda? Jest rzeczywiście nic lewo na lewym boku. 

Nie ma nic Pozostałe po lewej stronie, więc możemy efektywnie tylko move-- możemy zadeklarować reszta to jest rzeczywiście sortowane i po prostu przykleić go na, ponieważ nie ma nic innego porównać przeciw. I wiemy, że prawa strona z prawej strony jest posortowana. 

OK, więc teraz niech zamrażać ponownie i dowiedzieć się, gdzie jesteśmy w tej historii. W ogólnej tablicy co osiągnęliśmy? Mamy rzeczywiście osiągnąć teraz kroki jeden i krok drugi. Mamy klasyfikowane lewą połowę, a mamy klasyfikowane prawą połowę. 

Więc teraz pozostaje tylko dla nas scalić te dwie połówki. Więc porównanie najniższa wyceniane element każdej połówce matrycy z kolei i przejść. Jednym z nich jest mniejsza niż trzy, więc idzie. 

Dwa jest mniejsza niż trzy, więc dwa idzie. Trzy jest mniejsza niż 5, więc trzy idzie. Cztery jest mniejsza niż 5, więc cztery idzie. Następnie pięć jest mniej niż sześciu, a sześć jest wszystko, co pozostało. 

Teraz wiem, że było dużo schodów. A my pozostawia wiele w naszej pamięci ślad. I to właśnie te szare kwadraty są. I to chyba było jak, że wziął wiele dłużej niż Sortowanie przez wstawianie, bańka sortowanie, czy wybór rodzaju. 

Ale w rzeczywistości, ponieważ Wiele z tych procesów dzieją się w tym samym time-- która jest coś, czego będziesz znowu mówić, gdy mówimy o rekurencja w przyszłości video-- algorytm ten rzeczywiście wyraźnie jest zasadniczo inna niż wszystko widzieliśmy wcześniej ale także znacznie bardziej wydajny. 

Dlaczego? Cóż, w najgorszym scenariusz, mamy do podziału n elementy się a następnie łączą je. Ale kiedy rekombinacji im, co robimy jest w zasadzie podwojenie rozmiar mniejszych tablic. Mamy kilka jednego elementu tablice, które skutecznie łączą się z dwóch tablic elementów. A potem weźmiemy te Obie tablice elementów i połączyć je ze sobą w cztery tablice elementu, i tak dalej, i tak dalej, i tak dalej, aż mają jeden n element tablicy. 

Ale ilu podwojeń trwa dostać się do n? Pomyśl na przykład w książce telefonicznej. Ile razy mamy do łez książka telefoniczna na pół, o ile więcej Czasy mamy oderwać książki telefonicznej w połowie, jeżeli rozmiar książki telefonicznej podwoiła się? Jest tylko jeden, prawda? 

Więc jest jakiś logarytmiczna elementem tutaj. Ale my też jeszcze co najmniej spojrzeć na wszystkie elementy N. Tak więc w najgorszym przypadku, sortowanie przez scalanie przebiega n log n. Musimy patrzeć na wszystkie elementy n, i musimy je połączyć razem w dzienniku n zestawów kroków. W najlepszym przypadku, tablica jest doskonale klasyfikowane. To wspaniale. Ale w oparciu o algorytm mamy tutaj wciąż mamy do podziału i rekombinacji. Chociaż w tym przypadku, rekombinacji jest rodzaj nieskuteczne. Nie jest to konieczne. Ale wciąż przejść przez cały proces tak. 

Tak więc w najlepszym wypadku w najgorszym przypadku, ten algorytm działa w czasie n log n. Sortowanie przez scalanie jest zdecydowanie nieco trudniejsze niż w innych głównych algorytmów sortowania Mówiliśmy o CS50, ale jest znacznie bardziej wydajne. 

I tak, jeśli kiedykolwiek znajdziesz okazja do tego potrzebują lub wykorzystać go do sortowania duży zestaw danych, coraz Twoja głowa wokół idei rekursji będzie naprawdę potężny. I to się dzieje, aby Państwa programy naprawdę znacznie bardziej wydajne za pomocą sortowanie przez scalanie kontra cokolwiek innego. Jestem Doug Lloyd. To CS50.