1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Ordina inserire]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard University]

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

4
00:00:07,290 --> 00:00:13,060
Diamo un'occhiata a ordinamento per inserzione, un algoritmo per fare un elenco di numeri e ordinarli.

5
00:00:13,060 --> 00:00:18,300
Un algoritmo, lo ricordiamo, è semplicemente un passo per passo la procedura per realizzare un compito.

6
00:00:18,300 --> 00:00:23,640
L'idea alla base insertion sort, è quello di dividere la nostra lista in due parti,

7
00:00:23,640 --> 00:00:26,580
una porzione di cernita e di una parte non ordinato.

8
00:00:26,580 --> 00:00:29,290
>> Ad ogni passo dell'algoritmo, un numero viene spostato

9
00:00:29,290 --> 00:00:32,439
dalla porzione misti alla porzione ordinati

10
00:00:32,439 --> 00:00:35,680
finché alla fine l'intero elenco è ordinato.

11
00:00:35,680 --> 00:00:43,340
Ecco l'elenco dei sei numeri non ordinati - 23, 42, 4, 16, 8, e 15.

12
00:00:43,340 --> 00:00:47,680
Dal momento che questi numeri non sono tutti in ordine crescente, sono ordinati.

13
00:00:47,680 --> 00:00:53,890
Dal momento che non hanno iniziato l'ordinamento ancora, prenderemo in considerazione tutti e sei gli elementi nostra parte indifferenziati.

14
00:00:53,890 --> 00:00:59,270
>> Una volta che cominciamo ordinamento, metteremo questi numeri ordinati a sinistra di questi.

15
00:00:59,270 --> 00:01:03,600
Allora, cominciamo con 23, il primo elemento nella nostra lista.

16
00:01:03,600 --> 00:01:06,930
Non ci sono elementi nella nostra parte ancora ordinati,

17
00:01:06,930 --> 00:01:12,460
quindi cerchiamo di prendere in considerazione solo 23 per l'inizio e la fine della nostra porzione ordinati.

18
00:01:12,460 --> 00:01:16,510
Ora, la nostra parte ha ordinato un numero, 23,

19
00:01:16,510 --> 00:01:20,260
e la nostra parte non ordinato ha queste cinque numeri.

20
00:01:20,260 --> 00:01:27,320
Passiamo ora inserire il numero successivo nella nostra parte indifferenziati, 42, nella porzione ordinata.

21
00:01:27,320 --> 00:01:35,930
>> Per fare ciò, abbiamo bisogno di confrontare il 42 al 23 - l'unico elemento della nostra porzione ordinati finora.

22
00:01:35,930 --> 00:01:41,980
Quarantadue è più grande di 23, in modo che possiamo semplicemente aggiungere 42 alla fine

23
00:01:41,980 --> 00:01:45,420
della porzione della lista ordinata. Fantastico!

24
00:01:45,420 --> 00:01:51,850
Ora la nostra porzione ordinati ha due elementi, e la nostra parte indifferenziati ha quattro elementi.

25
00:01:51,850 --> 00:01:57,200
Allora, ora passare alla 4, l'elemento successivo nella parte indifferenziati.

26
00:01:57,200 --> 00:02:00,230
Così, dove deve essere collocato nella porzione ordinata?

27
00:02:00,230 --> 00:02:04,220
>> Ricordate, ora vogliamo mettere questo numero in modo ordinato

28
00:02:04,220 --> 00:02:08,680
così la nostra porzione ordinati rimane ordinato correttamente in ogni momento.

29
00:02:08,680 --> 00:02:14,380
Se poniamo il 4 alla destra del 42, allora la nostra lista sarà fuori servizio.

30
00:02:14,380 --> 00:02:18,380
Quindi, cerchiamo di continuare a spostare da destra a sinistra nella nostra porzione di sorta.

31
00:02:18,380 --> 00:02:23,260
Come ci muoviamo, facciamo spostare ogni numero giù un posto per fare spazio al nuovo numero.

32
00:02:25,440 --> 00:02:31,740
Ok, 4 è anche inferiore a 23, in modo da non possiamo mettere neanche qui.

33
00:02:31,740 --> 00:02:34,480
Passiamo il 23 giusto posto.

34
00:02:36,500 --> 00:02:43,120
>> Questo significa che ci piacerebbe mettere il 4 nel primo slot nella parte ordinata.

35
00:02:43,120 --> 00:02:46,300
Si noti come questo spazio della lista è già vuoto,

36
00:02:46,300 --> 00:02:51,120
perché abbiamo elementi in movimento filtrate così li abbiamo incontrati.

37
00:02:51,120 --> 00:02:52,740
Bene. Quindi, siamo a metà strada.

38
00:02:52,740 --> 00:02:57,990
Continuiamo il nostro algoritmo inserendo il 16 nella porzione ordinata.

39
00:02:59,260 --> 00:03:03,820
Sedici è inferiore a 42, quindi cerchiamo di spostare il 42 a destra.

40
00:03:05,700 --> 00:03:10,190
Sedici è anche meno di 23, quindi cerchiamo di cambiare anche tale elemento.

41
00:03:11,790 --> 00:03:20,820
>> Ora, 16 è maggiore di 4. Quindi, sembra che vorremmo inserire la 16 tra il 4 e il 23.

42
00:03:20,820 --> 00:03:24,620
Mentre si muove attraverso la porzione della lista ordinata da destra a sinistra,

43
00:03:24,620 --> 00:03:29,160
4 è il primo numero abbiamo visto che è inferiore al numero

44
00:03:29,160 --> 00:03:31,540
stiamo cercando di inserire.

45
00:03:31,540 --> 00:03:35,820
Quindi, ora siamo in grado di inserire il 16 in questo slot vuoto,

46
00:03:35,820 --> 00:03:40,520
che, ricordiamo, abbiamo creato da elementi in movimento nella parte ordinamento sopra

47
00:03:40,520 --> 00:03:43,340
come li abbiamo incontrati.

48
00:03:43,340 --> 00:03:47,900
>> Bene. Ora, abbiamo quattro elementi ordinati e due elementi non sottoposti a cernita.

49
00:03:47,900 --> 00:03:51,600
Quindi, cerchiamo di spostare il 8 nella porzione ordinata.

50
00:03:51,600 --> 00:03:55,010
Otto è inferiore a 42.

51
00:03:55,010 --> 00:03:56,940
Otto è inferiore a 23.

52
00:03:56,940 --> 00:04:00,230
E 8 è inferiore a 16.

53
00:04:00,230 --> 00:04:03,110
Ma 8 è maggiore di 4.

54
00:04:03,110 --> 00:04:07,280
Quindi, vorremmo inserire la 8 tra il 4 e il 16.

55
00:04:09,070 --> 00:04:13,650
Ed ora non ci resta che un elemento in più a sinistra per ordinare - il 15.

56
00:04:13,950 --> 00:04:16,589
Quindici è inferiore a 42,

57
00:04:16,589 --> 00:04:19,130
Quindici è inferiore a 23.

58
00:04:19,130 --> 00:04:21,750
E 15 è inferiore a 16.

59
00:04:21,750 --> 00:04:24,810
Ma 15 è maggiore di 8.

60
00:04:24,810 --> 00:04:27,440
>> Così, qui è dove vogliamo rendere il nostro inserimento definitivo.

61
00:04:28,770 --> 00:04:30,330
E abbiamo finito.

62
00:04:30,330 --> 00:04:33,540
Non ci sono più elementi nella parte non ordinata,

63
00:04:33,540 --> 00:04:36,670
e la nostra parte è ordinata secondo l'ordine corretto.

64
00:04:36,670 --> 00:04:40,270
I numeri sono ordinati dal più piccolo al più grande.

65
00:04:40,270 --> 00:04:44,330
Quindi, diamo uno sguardo ad alcuni pseudocodice che descrive i passaggi che abbiamo appena eseguiti.

66
00:04:46,760 --> 00:04:51,740
>> In linea 1, possiamo vedere che abbiamo bisogno di eseguire iterazioni su ogni elemento della lista

67
00:04:51,740 --> 00:04:57,060
tranne la prima, in quanto il primo elemento nella porzione unsorted diventerà semplicemente

68
00:04:57,060 --> 00:05:00,220
il primo elemento nella porzione ordinata.

69
00:05:00,220 --> 00:05:06,320
Sulle linee 2 e 3, stiamo tenendo traccia del nostro posto attuale nella parte indifferenziati.

70
00:05:06,320 --> 00:05:10,450
Elemento rappresenta il numero che stiamo muovendo nella porzione ordinata,

71
00:05:10,450 --> 00:05:15,600
e j rappresenta il nostro indice nella porzione indifferenziati.

72
00:05:15,600 --> 00:05:20,980
>> In linea 4, che stiamo scorrendo la porzione ordinati da destra a sinistra.

73
00:05:20,980 --> 00:05:26,010
Vogliamo fermare iterazione volta che l'elemento a sinistra della nostra posizione attuale

74
00:05:26,010 --> 00:05:30,050
è minore l'elemento che stiamo cercando di inserire.

75
00:05:30,050 --> 00:05:35,600
Sulla linea 5, ci stiamo spostando ogni elemento che incontriamo uno spazio a destra.

76
00:05:35,600 --> 00:05:40,950
In questo modo, avremo uno spazio libero da inserire quando troviamo il primo elemento

77
00:05:40,950 --> 00:05:44,080
meno l'elemento ci stiamo muovendo.

78
00:05:44,080 --> 00:05:50,800
In linea 6, stiamo aggiornando il nostro contatore per continuare a spostare a sinistra attraverso la porzione ordinata.

79
00:05:50,800 --> 00:05:56,860
Infine, sulla linea 7, stiamo inserendo l'elemento nella porzione ordinata della lista.

80
00:05:56,860 --> 00:06:00,020
>> Sappiamo che è giusto da inserire in posizione j,

81
00:06:00,020 --> 00:06:05,360
perché abbiamo già spostato l'elemento che ha usato per essere lì uno spazio a destra.

82
00:06:05,360 --> 00:06:09,460
Ricordate, ci stiamo muovendo attraverso la porzione ordinati da destra a sinistra,

83
00:06:09,460 --> 00:06:13,960
ma ci stiamo muovendo attraverso la parte non ordinata da sinistra a destra.

84
00:06:13,960 --> 00:06:19,090
Bene. Diamo ora un'occhiata a quanto tempo in esecuzione che l'algoritmo ha preso.

85
00:06:19,090 --> 00:06:25,300
Ecco ora la domanda quanto tempo ci vuole per questo algoritmo per l'esecuzione nel caso peggiore.

86
00:06:25,300 --> 00:06:29,040
Ricordiamo che noi rappresentiamo il tempo di esecuzione con Big notazione O.

87
00:06:32,530 --> 00:06:38,500
Al fine di risolvere la nostra lista, abbiamo dovuto scorrere gli elementi nella parte non ordinata,

88
00:06:38,500 --> 00:06:43,430
e per ciascuno di tali elementi, potenzialmente su tutti gli elementi della porzione ordinata.

89
00:06:43,430 --> 00:06:47,950
Intuitivamente, questo suona come un (n ^ 2) O.

90
00:06:47,950 --> 00:06:51,840
>> Guardando alla nostra pseudocodice, abbiamo un ciclo annidato all'interno di un altro ciclo,

91
00:06:51,840 --> 00:06:55,290
che, anzi, suona come un (n ^ 2) O.

92
00:06:55,290 --> 00:07:01,590
Tuttavia, la porzione di elenco ordinato non conteneva l'intero elenco fino alla fine.

93
00:07:01,590 --> 00:07:06,920
Ancora, si potrebbe potenzialmente inserire un nuovo elemento all'inizio della parte ordinata

94
00:07:06,920 --> 00:07:09,320
su ogni iterazione dell'algoritmo,

95
00:07:09,320 --> 00:07:14,500
il che significa che avremmo dovuto guardare ogni elemento attualmente nella porzione ordinata.

96
00:07:14,500 --> 00:07:20,090
Quindi, questo significa che potrebbe fare una comparazione per il secondo elemento,

97
00:07:20,090 --> 00:07:24,660
due confronti per il terzo elemento, e così via.

98
00:07:24,660 --> 00:07:32,480
Così, il numero totale di operazioni è la somma dei numeri interi da 1 a la lunghezza della lista meno 1.

99
00:07:32,480 --> 00:07:35,240
Possiamo rappresentare questo con una sommatoria.

100
00:07:41,170 --> 00:07:47,270
>> Non andrà in sommatorie qui, ma si scopre che questa somma è uguale a

101
00:07:47,270 --> 00:07:57,900
n (n - 1) su 2, che equivale n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Quando si parla di esecuzione asintotico,

103
00:08:00,800 --> 00:08:05,170
questo termine n ^ 2 sta per dominare questo termine n.

104
00:08:05,170 --> 00:08:11,430
Quindi, insertion sort è Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Che cosa succede se abbiamo corso ordinamento per inserimento in un elenco già ordinato.

106
00:08:16,150 --> 00:08:20,960
In tal caso, saremmo semplicemente costruire la parte ordinati da sinistra a destra.

107
00:08:20,960 --> 00:08:25,050
Quindi, ci sarà solo bisogno dell'ordine di n passi.

108
00:08:25,050 --> 00:08:29,740
>> Ciò significa che insertion sort ha una migliore prestazione nel caso di n,

109
00:08:29,740 --> 00:08:34,130
che noi rappresentiamo con Ω (n).

110
00:08:34,130 --> 00:08:36,190
E questo è tutto per insertion sort,

111
00:08:36,190 --> 00:08:40,429
solo uno dei molti algoritmi possiamo utilizzare per ordinare un elenco.

112
00:08:40,429 --> 00:08:43,210
Il mio nome è Tommy, e questo è CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, non si può fermare che una volta che si avvia.

115
00:09:01,620 --> 00:09:04,760
Oh, abbiamo fatto - Boom! >>