[Powered by Google Translate] [Merge sort] [Rob Bowden - Harvard University] [Questo è CS50. - CS50.TV] Parliamo di merge sort. Finora abbiamo visto bubble sort, insertion sort e selection sort. Anche se sarò tipo di onda la mia mano a ciò che intendo con una migliore, merge sort esegue in genere meglio di qualsiasi di questi 3 tipi. 

Ma prima di parlare di merge sort, parliamo di fusione 2 liste filtrate. Chiameremo il processo di prendere due liste ordinate, come questi, e fare un unico elenco ordinato da loro - fusione delle liste. Come possiamo fare questo? Bene, una idea è quella di attaccare una sola lista sulla fine della lista altri e poi ordinare l'elenco risultante. 

Anche se questo funziona, è un sacco di lavoro inutile. Siamo in grado di farlo più velocemente di una semplice selezione. Si noti che una idea sbagliata è quella di prendere solo tazze alternati da ogni lista. Anche se ciò può sembrare che le opere in un primo momento, facendo questo si finisce con 4, 8, 15, 23, 16 - si noti che 16 e 23 sono fuori luogo. Questo è dovuto al fatto 2 elementi che dovrebbero apparire consecutivo nell'elenco unito sono nella stessa lista iniziale. Sia 15 e 16 sono nella lista a sinistra. Il trucco è quello di approfittare del fatto che entrambe le liste sono già ordinati. Questo significa che se ci limitiamo a guardare i primi elementi di entrambe le liste - Qui, 4 e 8 - uno di essi deve essere il primo elemento della lista unito. Beh, perché? Entrambe le liste sono già ordinati, e quindi o 4 o 8 deve essere il più piccolo elemento quando si combinano le 2 liste. In questo caso, il più piccolo è 4, in modo da poter estrarre 4 e ne fanno il primo elemento della nostra lista unita. Ora continuiamo la fusione dei restanti 3 elementi della prima lista e quattro elementi del secondo elenco. 

Ancora una volta, abbiamo solo bisogno di guardare il primo elemento di entrambe le liste. Il più piccolo dei due deve essere il secondo elemento della nostra lista unito. Questa volta, tra l'8 e il 15 il più piccolo è di 8, e così inserire tale come secondo elemento della nostra lista ordinata. Siamo in grado di proseguire il confronto con i primi elementi di entrambe le liste e rimuovendo il minore dei due. Confronto tra 15 e 23, il 15 è più piccolo e così questo è il nostro terzo elemento. Ora confronto 16 e 23, 16 è minore. Ecco, questo è il quarto elemento. 

Si noti che 2 elementi provenivano dalla stessa lista di fila. È per questo che la lista risultante dalla fusione non può semplicemente gli elementi si alternano dalle 2 liste. Confronto tra 50 e 23, 23 è più piccolo, in modo da scegliere quella. Tra 50 e 42, 42 è più piccolo. Tra 50 e 108, 50 è più piccolo. E, infine, dobbiamo solo 108, quindi deve andare alla fine della nostra lista. Si noti che abbiamo una bella lista ordinata. Ogni volta che abbiamo messo a confronto i primi 2 elementi delle 2 liste siamo stati in grado di determinare l'elemento successivo della lista risultante dalla fusione. Ciò significa che se l'elenco finale contiene numeri n, dove n è qui 8, allora abbiamo bisogno al massimo n confronti per ottenere tutti quei numeri nel posto giusto. Tale algoritmo è detto per l'esecuzione in tempo lineare, ma non ti preoccupare che qui. 

Usando il nostro algoritmo per la fusione, siamo in grado di fare un veloce algoritmo di ordinamento per fusione. Quindi, cerchiamo di ripristinare le nostre liste. Ci sono 2 grandi passi nel processo di merge sort. Primo, continuamente dividere la lista di tazze in due metà finché non avremo un gruppo di liste con solo 1 tazza in loro. Non preoccupatevi se una lista contiene un numero dispari e non si può fare un taglio perfettamente pulito tra di loro. Basta scegliere arbitrariamente quale lista per includere la coppa in più trovi Quindi, cerchiamo di dividere queste liste. Ora abbiamo 2 liste. Ora abbiamo 4 liste. 

E ora abbiamo 8 liste con una sola tazza in ogni elenco. Quindi il gioco è fatto per il passaggio 1. Per la fase 2, più volte unisce coppie di liste utilizzando l'algoritmo di unione abbiamo imparato prima. Unione di 108 e 15, si finisce con l'elenco 15, 108. Unione di 50 e 4, si finisce con 4, 50. Unione di 8 e 42, si finisce con l'8, 42. E la fusione 23 e 16, si finisce con 16, 23. Ora tutte le nostre liste sono di dimensione 2. Si noti che ciascuna delle 4 liste è ordinato. 

Così possiamo iniziare a unire coppie di liste. Unione di 15 e 108 e 4 e 50 - prima prendere la 4, poi il 15, poi il 50, allora il 108. Unione di 8, 42 e 16, 23, basta prendere l'8, poi il 16, poi il 23, poi il 42. Così ora abbiamo solo 2 liste di dimensione 4, ciascuno dei quali viene ordinato. Così ora uniamo queste 2 liste. Per prima cosa prendere la 4. Poi prendere la 8. Poi prendiamo il 15 e 16, poi 23, poi 42, poi 50, poi 108. E abbiamo finito. Ora abbiamo una lista ordinata. Quindi, la velocità era questo, esattamente? In termini tecnici, merge sort è O (n log n), mentre tutti bubble sort, insertion sort e selection sort sono O (n ²). In realtà, come si vedrà presto, non sarà in grado di elaborare una sorta che esegue meglio di O (n log n) nel caso generale. Anche in questo caso, non preoccupatevi di questa notazione O grande se non l'avete ancora visto. 

Basta sapere che questo significa che se volevamo ordinare un elenco molto grande ordinamento bubble sort, insertion sort, e la selezione potrebbe prendere significativamente più lungo di merge sort. Ciò non significa che merge sort sarà più veloce per tutti gli elenchi o anche per qualsiasi lista unica sotto una certa dimensione. Ad esempio, per inserzione potrebbe essere il più veloce di ordinamento per tutte le liste inferiori a 5 elementi. In pratica, merge sort è solitamente più veloce per le liste piccole come 50 elementi. 

Ma questa velocità in più non viene senza un prezzo. A differenza dei nostri altri tipi, che prende una lista e modificare l'elenco sul posto fino a quando si ottiene un elenco ordinato, merge sort ha bisogno di spazio aggiuntivo di fondere due liste insieme. Non si può utilizzare immediatamente gli elenchi che vengono uniti per memorizzare l'elenco unito dal momento che potrebbero sostituire gli elementi che devono ancora essere uniti. Questo spazio è un po 'di prezzo, ma di solito non è irragionevole. E questo è tutto per merge sort. 

Il mio nome è Rob Bowden, e questo è CS50. [CS50.TV] - La selezione e ordinamento. [Ride] Oh, devo prendere quel troppo, perché sono passato come stavo presentando. Elenco sulla sinistra. E 'stato un errore di battitura. [Misspoke] ho fatto un casino - [Ride] Io non so che cosa -