[Powered by Google Translate] [Merge Sort] [Rob Bowden - Harvard University] [To jest CS50. - CS50.TV] Porozmawiajmy o sortowanie korespondencji seryjnej. Dotychczas widzieliśmy sortowania bąbelkowego, sortowanie wstawiania i sortować wyboru. Chociaż ja w rodzaj fali moją rękę na to, co mam na myśli, lepiej, scalić sort ogólnie działa lepiej niż którykolwiek z tych 3 rodzajów. 

Ale zanim mówić o rodzaju łączenia, pomówmy o łączenie 2 sortowanie listy. Zadzwonimy proces podejmowania 2 sortowanie listy, jak te, i co jeden posortowanej listy z nich - łączenie list. W jaki sposób możemy to zrobić? Cóż, jeden pomysł jest po prostu trzymać jedną listę na końcu drugiej listy a następnie posortować listę wynikową. 

Mimo to działa, to jest dużo niepotrzebnej pracy. Możemy to zrobić szybciej, niż tylko sortowanie. Zauważ, że jeden zły pomysł jest po prostu wziąć filiżanek przemian z każdej listy. Mimo, że może wydawać się, że prace w pierwszym, robi, że skończymy z 4, 8, 15, 23, 16 - zauważ, że 16 i 23 są nie na miejscu. To dlatego, że 2 elementy, które powinny pojawić kolejny w połączonej listy w tej samej pierwszej listy. 15 i 16, zarówno w liście są po lewej stronie. Sztuką jest, aby skorzystać z faktu, że obie listy są już posortowane. Oznacza to, że jeśli tylko patrzeć pierwszych elementów obu listach - o, 4 i 8 - jeden z nich musi być pierwszym elementem połączonego listy. Cóż, to dlaczego? Obydwa z tych list już posortowane, i tak 4 lub 8 może być najmniejszy element, kiedy łączymy 2 list. W tym przypadku, jest najmniejsza 4 więc możemy wziąć 4 i sprawiają, że pierwszy element naszej połączonej listy. Teraz możemy kontynuować łączenie pozostałe 3 elementy pierwszej listy i 4 elementy drugiej listy. 

Po raz kolejny, tylko trzeba spojrzeć na pierwszy element obu listach. Mniejsza z 2 musi być drugi element naszej połączonej listy. Tym razem, od 8 do 15 jest najmniejsza 8, a więc, że wprowadzić jako drugi element naszego sortowanej listy. Możemy kontynuować porównywanie pierwszych elementów obu list i usunięcie z 2 mniejsze. Porównując 15 i 23, 15 jest mniejsza, i tak, że to nasz trzeci element. Teraz porównanie 16 i 23, 16 jest mniejszy. Więc to czwarty element. 

Zauważ, że 2 elementy pochodziły z tej samej listy w wierszu. Dlatego lista powstała w wyniku połączenia nie można po prostu alternatywne elementy z 2 list. Porównując 50 i 23, 23 jest mniejszy, więc wybraliśmy to. Pomiędzy 50 i 42, 42 jest mniejszy. Pomiędzy 50 i 108, 50 jest mniejszy. I wreszcie, musimy tylko 108, więc musi iść na końcu naszej listy. Zauważ, że mamy ładne, posortowaną listę. Za każdym razem, w porównaniu pierwsze 2 elementy 2 list udało się ustalić, kolejnym elementem połączonego listy. Oznacza to, że jeżeli ostateczna lista zawiera n liczb, gdzie n tutaj jest 8, to musimy co najwyżej n porównań, aby wszystkie te numery w odpowiednim miejscu. Taki algorytm jest powiedziane, aby uruchomić w czasie liniowym, ale nie martw się o tym tutaj. 

Korzystanie z naszego algorytmu scalania, możemy szybki algorytm sortowania korespondencji seryjnej. No to zresetować nasze listy. Istnieją 2 duże kroki w procesie sortowania korespondencji seryjnej. Po pierwsze, stale podzielić listę na pół filiżanki dopóki mamy kilka list z tylko 1 filiżankę w nich. Nie martw się, jeśli lista zawiera nieparzystą liczbę i nie można zrobić idealnie czyste cięcie między nimi. Wystarczy dowolnie wybrać, które lista zawierać dodatkową filiżankę w. No to podzielić tych list. Teraz mamy 2 list. Teraz mamy 4 list. 

A teraz mamy 8 list z jednego kubka w każdym liście. Więc to jest to dla kroku 1. Dla kroku 2, to wielokrotnie łączy pary list algorytmem scalania dowiedzieliśmy wcześniej. Połączenie 108 i 15, ale kończy się z listy 15, 108. Scalanie 50 i 4, ale kończy się z 4, 50. Połączenie 8 i 42, ale kończy się z 8, 42. I połączenie 23 i 16, ale kończy się z 16, 23. Teraz wszystkie nasze listy są wielkości 2. Zauważ, że każdy z 4 listy są sortowane. 

Więc możemy zacząć łączenie par list ponownie. Scalanie 15 i 108 oraz 4 i 50 - najpierw wziąć do 4, a następnie 15, a następnie 50, a następnie 108. Połączenie 8, 42 i 16, 23, najpierw się 8, a następnie 16, a następnie 23, a następnie 42. Więc teraz mamy tylko 2 listy rozmiar 4, z których każdy jest posortowane. Więc teraz połączyć te 2 list. Najpierw bierzemy 4. Następnie bierzemy 8. Następnie bierzemy 15 i 16, potem 23, potem 42, potem 50, potem 108. I gotowe. Mamy teraz posortowana lista. Tak jak szybko to było dokładnie? Z technicznego punktu widzenia, sort merge jest O (n log n), natomiast wszystkie sortowanie bąbelkowe, sortowanie wstawiania, i rodzaju selekcji O (n ²). W rzeczywistości, jak można dowiedzieć się wkrótce, że nie będzie w stanie wymyślić coś w rodzaju że działa lepiej niż O (n log n) w przypadku ogólnym. Ponownie, nie martw się o tym wielkim notacji O, jeśli nie widziałeś jeszcze. 

Po prostu wiem, że to oznacza, że ​​jeśli chcemy, aby posortować listę naprawdę duży sort sortowanie bąbelkowe, sortowanie wstawiania i wybór może potencjalnie wziąć znacznie dłużej niż seryjnej sortowania. To nie znaczy, że sort merge będzie szybciej dla wszystkich list lub nawet dla pojedynczej listy w określonej wielkości. Na przykład, może być swego rodzaju wprowadzenie najszybciej sortowania wszystkich list mniejszych niż 5 elementów. W praktyce, sort merge jest zazwyczaj szybsza dla list tak małych jak 50 elementów. 

Ale ta dodatkowa prędkość nie przychodzi bez ceny. W przeciwieństwie do naszych innych rodzajów, które mają listę i zmodyfikować listę w lokalu aż dojdziemy posortowaną listę, sort merge potrzebuje dodatkowego miejsca scalić 2 list razem. Nie możemy od razu korzystać z list, które są scalane do przechowywania scaloną listę gdyż moglibyśmy zastąpić elementy, które wciąż muszą zostać połączone. Ta przestrzeń jest trochę cena, ale to zazwyczaj nie jest bezzasadne. I to na sortowanie korespondencji seryjnej. 

Nazywam się Rob Bowden, a to CS50. [CS50.TV] - I wybór rodzaju. [Śmieje się] Och, muszę wziąć to zbyt bo przeszedłem jak byłem przedstawianie go. Lista po lewej stronie. To była literówka. [Misspoke] spieprzyłem - [Śmieje się] Nie wiem, co -