[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 -