[Powered by Google Translate] [Sloučit Třídit] [Rob Bowden - Harvard University] [To je CS50. - CS50.TV] Pojďme mluvit o jakési sloučení. Zatím jste viděli bubble sort, vložení druhu, a výběr řazení. I když budu trochu vlny mé ruky na to, co tím myslím lepší, sloučit druh obecně lepší než některý z těchto 3 druhů. 

Ale dříve, než mluvit o jakési sloučení, pojďme mluvit o sloučení 2 tříděné seznamy. Zavoláme proces přijímání 2 tříděné seznamy, jako jsou tyto, a dělat jeden seřazený seznam z nich - sloučení seznamů. Jak to můžeme udělat? No, jeden nápad je jen držet jeden seznam na konci druhého seznamu a pak třídit výsledný seznam. 

Zatímco toto funguje, je to hodně zbytečné práce. Můžeme to udělat rychleji, než jen třídění. Všimněte si, že jeden špatný nápad, je prostě vzít střídající poháry z každého seznamu. I když to může vypadat jako to funguje na první, dělá, že jsme skončili s 4, 8, 15, 23, 16 - oznámení, že 16 a 23 jsou z místa. To je proto, že 2 prvky, které by měly být uvedeny za sebou ve sloučené seznamu jsou ve stejné původního seznamu. Oba 15 a 16 jsou v seznamu na levé straně. Trik je využít skutečnosti, že oba seznamy jsou již seřazeny. To znamená, že pokud se jen podívat na první prvky obou seznamů - zde, 4 a 8 - musí být jeden z nich rovněž být první prvek sloučeného seznamu. No, proč to je? Oba tyto seznamy jsou již seřazeny, a tak buď 4 nebo 8, musí být nejmenší prvek, když spojíme 2 seznamy. V tomto případě, nejmenší je 4, takže můžeme vzít ven 4 a dělat to první prvek naší sloučené seznamu. Nyní budeme pokračovat sloučení zbývající 3 prvky prvního seznamu a 4 prvky druhého seznamu. 

Opět jsme Stačí se podívat na první prvek obou seznamů. Menší z 2 musí být druhý prvek naší sloučené seznamu. Tentokrát mezi 8 a 15 nejmenší je 8, a tak jsme se vložit, aby jako druhý prvek našeho tříděného seznamu. Můžeme pokračovat v porovnání prvních prvky obou seznamů a odstranění menší z 2. Porovnání 15 a 23, 15 je menší, a tak to je naše třetí element. Nyní srovnání 16 a 23, 16, je menší. Tak to je čtvrtý element. 

Všimněte si, že 2 prvky pocházejí ze stejného seznamu v řadě. To je důvod, proč vzniklý seznam nemůže jen střídají prvky od 2 seznamů. Porovnání 50 a 23, 23 je menší, tak jsme se rozhodli, že. Mezi 50 a 42, 42 je menší. Mezi 50 a 108, 50 je menší. A konečně, musíme jen 108, tak to musí jít na konci našeho seznamu. Všimněte si, že máme pěkný, seřazený seznam. Pokaždé, když jsme porovnali první 2 prvky 2 seznamů jsme byli schopni určit další prvek sloučeného seznamu. To znamená, že v případě, že konečný seznam obsahuje n čísla, kde n je zde 8, pak musíme na většině n srovnání dostat všechny z těchto čísel na správné místo. Takový algoritmus je řekl, aby spuštění v lineárním čase, ale nebojte se o tom zde. 

Pomocí našeho algoritmu pro slučování, můžeme udělat rychlý sloučení řazení algoritmus. Takže, pojďme obnovit naše seznamy. K dispozici jsou 2 velké kroky v procesu druhu korespondence. Za prvé, neustále rozdělí seznam šálků do poloviny dokud nebudeme mít spoustu seznamů pouze s 1 šálkem v nich. Nebojte se, pokud seznam obsahuje lichý počet a nemůžete udělat dokonale čistý řez mezi nimi. Jen libovolně vybrat, které uvádějí, aby zahrnovala další šálek dovnitř Takže, pojďme rozdělit tyto seznamy. Nyní máme 2 seznamy. Nyní máme 4 seznamy. 

A teď máme 8 seznamů s jedním šálkem v každém seznamu. Tak to je to v 1. kroku. Pro kroku 2, jsme opakovaně spojí dva seznamy algoritmem sloučení jsme se naučili předtím. Sloučení 108 a 15, skončíme s přehledem 15, 108. Sloučení 50 a 4, skončíme s 4, 50. Sloučení 8 a 42, skončíme s 8, 42. A sloučení 23 a 16, skončíme s 16, 23. Nyní jsou všechny naše seznamy jsou velikosti 2. Všimněte si, že každý z 4 seznamech seřazeny. 

Takže můžeme začít sloučením dvojice seznamů znovu. Sloučení 15 a 108 a 4 a 50 - první přijmout 4, pak 15, pak 50, pak 108. Sloučení 8, 42 a 16, 23, nejprve se 8, pak 16, pak 23, pak 42. Takže teď máme jen 2 seznamy velikosti 4, je seřazena z nichž každý. Takže teď jsme sloučit tyto 2 seznamy. Nejprve jsme se na 4. Pak budeme mít 8. Pak budeme mít 15 a 16, pak 23, pak 42, pak 50, pak 108. A jsme hotovi. Nyní máme seřazený seznam. Tak, jak rychle to bylo přesně? Z technického hlediska, sloučení sort je O (n log n), vzhledem k tomu, všechny bubliny druhu, vložení seřadit, a výběr druhu jsou O (n ²). Ve skutečnosti, jak budete brzy naučí, nebudete schopni přijít s jakýmsi že jsou lepší než O (n log n) v obecném případě. Opět, nebojte se o této velké O notace, pokud jste ho ještě neviděli ještě. 

Jen vím, že to znamená, že pokud bychom chtěli seřadit opravdu velký seznam bublina sort, vložení sort, a výběr sort by mohl mít podstatně déle než sloučení řazení. To neznamená, že sloučení třídění bude rychlejší pro všechny seznamy nebo dokonce pro každou jednotlivou seznamu pod určité velikosti. Například, může vložení druh nejrychlejší řazení pro všech seznamů menší než 5 prvků. V praxi, sloučení druh je obvykle rychlejší seznamy jak malý jako 50 prvků. 

Ale to navíc rychlost nepřijde bez ceny. Na rozdíl od našich ostatních druhů, které se v seznamu a upravit seznam v místě dokud nebudeme mít seřazený seznam, merge sort potřebuje další místo sloučit 2 seznamy dohromady. Nemůžeme ihned používat seznamy, které jsou sloučeny uložit sloučený seznam protože bychom mohli přepsat prvky, které ještě potřebují být sloučeny. Tento prostor je trochu cenu, ale to obvykle není nepřiměřené. A to je pro druh korespondence. 

Mé jméno je Rob Bowden, a to je CS50. [CS50.TV] - A výběr druhu. [Smích] Oh, musím vzít, že příliš, protože jsem přešel, jak jsem byl, že ho představuje. Seznamu na levé straně. To byl překlep. [Misspoke] I podělal - [Smích] Já nevím, co -