1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Merge sort]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Questo è CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Parliamo di merge sort.

5
00:00:09,000 --> 00:00:14,000
Finora abbiamo visto bubble sort, insertion sort e selection sort.

6
00:00:14,000 --> 00:00:17,000
Anche se sarò tipo di onda la mia mano a ciò che intendo con una migliore,

7
00:00:17,000 --> 00:00:21,000
merge sort esegue in genere meglio di qualsiasi di questi 3 tipi.

8
00:00:22,000 --> 00:00:27,000
>> Ma prima di parlare di merge sort, parliamo di fusione 2 liste filtrate.

9
00:00:27,000 --> 00:00:31,000
Chiameremo il processo di prendere due liste ordinate, come questi,

10
00:00:31,000 --> 00:00:35,000
e fare un unico elenco ordinato da loro - fusione delle liste.

11
00:00:35,000 --> 00:00:37,750
Come possiamo fare questo?

12
00:00:37,750 --> 00:00:41,290
Bene, una idea è quella di attaccare una sola lista sulla fine della lista altri

13
00:00:41,290 --> 00:00:43,830
e poi ordinare l'elenco risultante.

14
00:00:43,830 --> 00:00:47,220
>> Anche se questo funziona, è un sacco di lavoro inutile.

15
00:00:47,220 --> 00:00:49,900
Siamo in grado di farlo più velocemente di una semplice selezione.

16
00:00:49,900 --> 00:00:54,100
Si noti che una idea sbagliata è quella di prendere solo tazze alternati da ogni lista.

17
00:00:54,100 --> 00:00:56,460
Anche se ciò può sembrare che le opere in un primo momento,

18
00:00:56,460 --> 00:01:05,760
facendo questo si finisce con 4, 8, 15, 23, 16 - si noti che 16 e 23 sono fuori luogo.

19
00:01:05,760 --> 00:01:09,380
Questo è dovuto al fatto 2 elementi che dovrebbero apparire consecutivo nell'elenco unito

20
00:01:09,380 --> 00:01:11,720
sono nella stessa lista iniziale.

21
00:01:11,720 --> 00:01:14,850
Sia 15 e 16 sono nella lista a sinistra.

22
00:01:14,850 --> 00:01:19,810
Il trucco è quello di approfittare del fatto che entrambe le liste sono già ordinati.

23
00:01:19,810 --> 00:01:23,320
Questo significa che se ci limitiamo a guardare i primi elementi di entrambe le liste -

24
00:01:23,320 --> 00:01:29,580
Qui, 4 e 8 - uno di essi deve essere il primo elemento della lista unito.

25
00:01:29,580 --> 00:01:31,620
Beh, perché?

26
00:01:31,620 --> 00:01:33,520
Entrambe le liste sono già ordinati,

27
00:01:33,520 --> 00:01:38,410
e quindi o 4 o 8 deve essere il più piccolo elemento quando si combinano le 2 liste.

28
00:01:38,410 --> 00:01:41,770
In questo caso, il più piccolo è 4,

29
00:01:41,770 --> 00:01:46,370
in modo da poter estrarre 4 e ne fanno il primo elemento della nostra lista unita.

30
00:01:46,370 --> 00:01:50,710
Ora continuiamo la fusione dei restanti 3 elementi della prima lista

31
00:01:50,710 --> 00:01:52,920
e quattro elementi del secondo elenco.

32
00:01:52,920 --> 00:01:57,150
>> Ancora una volta, abbiamo solo bisogno di guardare il primo elemento di entrambe le liste.

33
00:01:57,150 --> 00:02:01,060
Il più piccolo dei due deve essere il secondo elemento della nostra lista unito.

34
00:02:01,060 --> 00:02:05,440
Questa volta, tra l'8 e il 15 il più piccolo è di 8, e così inserire tale

35
00:02:05,440 --> 00:02:09,240
come secondo elemento della nostra lista ordinata.

36
00:02:09,240 --> 00:02:12,180
Siamo in grado di proseguire il confronto con i primi elementi di entrambe le liste

37
00:02:12,180 --> 00:02:14,420
e rimuovendo il minore dei due.

38
00:02:14,420 --> 00:02:19,460
Confronto tra 15 e 23, il 15 è più piccolo e così questo è il nostro terzo elemento.

39
00:02:21,000 --> 00:02:23,910
Ora confronto 16 e 23, 16 è minore.

40
00:02:23,910 --> 00:02:26,820
Ecco, questo è il quarto elemento.

41
00:02:26,820 --> 00:02:30,390
>> Si noti che 2 elementi provenivano dalla stessa lista di fila.

42
00:02:30,390 --> 00:02:34,400
È per questo che la lista risultante dalla fusione non può semplicemente gli elementi si alternano dalle 2 liste.

43
00:02:34,400 --> 00:02:40,020
Confronto tra 50 e 23, 23 è più piccolo, in modo da scegliere quella.

44
00:02:40,770 --> 00:02:44,070
Tra 50 e 42, 42 è più piccolo.

45
00:02:44,070 --> 00:02:48,290
Tra 50 e 108, 50 è più piccolo.

46
00:02:48,290 --> 00:02:52,330
E, infine, dobbiamo solo 108, quindi deve andare alla fine della nostra lista.

47
00:02:53,750 --> 00:02:56,180
Si noti che abbiamo una bella lista ordinata.

48
00:02:56,180 --> 00:02:59,040
Ogni volta che abbiamo messo a confronto i primi 2 elementi delle 2 liste

49
00:02:59,040 --> 00:03:02,730
siamo stati in grado di determinare l'elemento successivo della lista risultante dalla fusione.

50
00:03:02,730 --> 00:03:08,070
Ciò significa che se l'elenco finale contiene numeri n, dove n è qui 8,

51
00:03:08,070 --> 00:03:12,610
allora abbiamo bisogno al massimo n confronti per ottenere tutti quei numeri nel posto giusto.

52
00:03:13,230 --> 00:03:16,230
Tale algoritmo è detto per l'esecuzione in tempo lineare,

53
00:03:16,230 --> 00:03:18,090
ma non ti preoccupare che qui.

54
00:03:18,570 --> 00:03:22,810
>> Usando il nostro algoritmo per la fusione, siamo in grado di fare un veloce algoritmo di ordinamento per fusione.

55
00:03:22,810 --> 00:03:25,170
Quindi, cerchiamo di ripristinare le nostre liste.

56
00:03:35,210 --> 00:03:37,750
Ci sono 2 grandi passi nel processo di merge sort.

57
00:03:37,750 --> 00:03:41,500
Primo, continuamente dividere la lista di tazze in due metà

58
00:03:41,500 --> 00:03:44,860
finché non avremo un gruppo di liste con solo 1 tazza in loro.

59
00:03:44,860 --> 00:03:47,350
Non preoccupatevi se una lista contiene un numero dispari

60
00:03:47,350 --> 00:03:49,880
e non si può fare un taglio perfettamente pulito tra di loro.

61
00:03:49,880 --> 00:03:53,750
Basta scegliere arbitrariamente quale lista per includere la coppa in più trovi

62
00:03:53,750 --> 00:03:56,240
Quindi, cerchiamo di dividere queste liste.

63
00:03:58,140 --> 00:04:01,310
Ora abbiamo 2 liste.

64
00:04:04,120 --> 00:04:06,570
Ora abbiamo 4 liste.

65
00:04:10,350 --> 00:04:13,870
>> E ora abbiamo 8 liste con una sola tazza in ogni elenco.

66
00:04:13,870 --> 00:04:16,630
Quindi il gioco è fatto per il passaggio 1.

67
00:04:16,630 --> 00:04:22,230
Per la fase 2, più volte unisce coppie di liste utilizzando l'algoritmo di unione abbiamo imparato prima.

68
00:04:22,230 --> 00:04:29,160
Unione di 108 e 15, si finisce con l'elenco 15, 108.

69
00:04:30,330 --> 00:04:36,250
Unione di 50 e 4, si finisce con 4, 50.

70
00:04:36,960 --> 00:04:41,400
Unione di 8 e 42, si finisce con l'8, 42.

71
00:04:42,790 --> 00:04:48,130
E la fusione 23 e 16, si finisce con 16, 23.

72
00:04:49,740 --> 00:04:52,450
Ora tutte le nostre liste sono di dimensione 2.

73
00:04:53,020 --> 00:04:56,180
Si noti che ciascuna delle 4 liste è ordinato.

74
00:04:56,180 --> 00:04:59,160
>> Così possiamo iniziare a unire coppie di liste.

75
00:04:59,160 --> 00:05:03,240
Unione di 15 e 108 e 4 e 50 -

76
00:05:03,240 --> 00:05:11,170
prima prendere la 4, poi il 15, poi il 50, allora il 108.

77
00:05:11,170 --> 00:05:15,120
Unione di 8, 42 e 16, 23,

78
00:05:15,120 --> 00:05:22,440
basta prendere l'8, poi il 16, poi il 23, poi il 42.

79
00:05:22,440 --> 00:05:27,370
Così ora abbiamo solo 2 liste di dimensione 4, ciascuno dei quali viene ordinato.

80
00:05:27,370 --> 00:05:30,980
Così ora uniamo queste 2 liste.

81
00:05:30,980 --> 00:05:33,440
Per prima cosa prendere la 4.

82
00:05:33,440 --> 00:05:36,580
Poi prendere la 8.

83
00:05:36,580 --> 00:05:50,700
Poi prendiamo il 15 e 16, poi 23, poi 42, poi 50, poi 108.

84
00:05:50,700 --> 00:05:52,220
E abbiamo finito.

85
00:05:52,220 --> 00:05:54,900
Ora abbiamo una lista ordinata.

86
00:05:54,900 --> 00:05:57,890
Quindi, la velocità era questo, esattamente?

87
00:05:57,890 --> 00:06:02,000
In termini tecnici, merge sort è O (n log n),

88
00:06:02,000 --> 00:06:07,380
mentre tutti bubble sort, insertion sort e selection sort sono O (n ²).

89
00:06:07,380 --> 00:06:11,120
In realtà, come si vedrà presto, non sarà in grado di elaborare una sorta

90
00:06:11,120 --> 00:06:14,820
che esegue meglio di O (n log n) nel caso generale.

91
00:06:14,820 --> 00:06:19,120
Anche in questo caso, non preoccupatevi di questa notazione O grande se non l'avete ancora visto.

92
00:06:19,120 --> 00:06:23,490
>> Basta sapere che questo significa che se volevamo ordinare un elenco molto grande

93
00:06:23,490 --> 00:06:26,820
ordinamento bubble sort, insertion sort, e la selezione potrebbe prendere

94
00:06:26,820 --> 00:06:29,500
significativamente più lungo di merge sort.

95
00:06:29,500 --> 00:06:33,210
Ciò non significa che merge sort sarà più veloce per tutti gli elenchi

96
00:06:33,210 --> 00:06:36,220
o anche per qualsiasi lista unica sotto una certa dimensione.

97
00:06:36,220 --> 00:06:41,950
Ad esempio, per inserzione potrebbe essere il più veloce di ordinamento per tutte le liste inferiori a 5 elementi.

98
00:06:41,950 --> 00:06:47,360
In pratica, merge sort è solitamente più veloce per le liste piccole come 50 elementi.

99
00:06:47,360 --> 00:06:51,120
>> Ma questa velocità in più non viene senza un prezzo.

100
00:06:51,120 --> 00:06:54,770
A differenza dei nostri altri tipi, che prende una lista e modificare l'elenco sul posto

101
00:06:54,770 --> 00:06:58,740
fino a quando si ottiene un elenco ordinato, merge sort ha bisogno di spazio aggiuntivo

102
00:06:58,740 --> 00:07:00,900
di fondere due liste insieme.

103
00:07:00,900 --> 00:07:04,690
Non si può utilizzare immediatamente gli elenchi che vengono uniti per memorizzare l'elenco unito

104
00:07:04,690 --> 00:07:08,880
dal momento che potrebbero sostituire gli elementi che devono ancora essere uniti.

105
00:07:08,880 --> 00:07:13,540
Questo spazio è un po 'di prezzo, ma di solito non è irragionevole.

106
00:07:13,540 --> 00:07:15,330
E questo è tutto per merge sort.

107
00:07:15,330 --> 00:07:18,490
>> Il mio nome è Rob Bowden, e questo è CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- La selezione e ordinamento.

110
00:07:24,000 --> 00:07:25,880
[Ride]

111
00:07:25,880 --> 00:07:31,480
Oh, devo prendere quel troppo, perché sono passato come stavo presentando.

112
00:07:31,480 --> 00:07:35,680
Elenco sulla sinistra. E 'stato un errore di battitura.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] ho fatto un casino -

114
00:07:39,290 --> 00:07:41,190
[Ride]

115
00:07:41,190 --> 00:07:44,190
Io non so che cosa -