1
00:00:00,000 --> 00:00:02,826
>> [RIPRODUZIONE DI BRANI MUSICALI]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Quindi insertion sort è un altro
algoritmo si può utilizzare per ordinare un array.

4
00:00:09,370 --> 00:00:12,350
L'idea alla base di questo algoritmo
è quello di costruire il vostro array ordinato

5
00:00:12,350 --> 00:00:19,670
in posto, spostando gli elementi di
il modo in cui, come si va, per fare spazio.

6
00:00:19,670 --> 00:00:22,240
Questo è leggermente diverso
da ordinamento per selezione o bolla

7
00:00:22,240 --> 00:00:25,460
sorta, per esempio, dove
stiamo regolando le posizioni,

8
00:00:25,460 --> 00:00:26,910
dove stiamo facendo swap.

9
00:00:26,910 --> 00:00:29,760
>> In questo caso ciò che siamo realmente
facendo è elementi scorrevoli

10
00:00:29,760 --> 00:00:31,390
sopra, fuori strada.

11
00:00:31,390 --> 00:00:34,030
Come funziona questo algoritmo
lavorare in pseudocodice?

12
00:00:34,030 --> 00:00:37,646
Pozzo di lasciare che arbitrariamente dire che la
primo elemento dell'array è ordinato.

13
00:00:37,646 --> 00:00:38,770
Stiamo costruendo al suo posto.

14
00:00:38,770 --> 00:00:42,660
>> Noi stiamo andando andiamo un elemento alla volta e
costruire, e così la prima cosa che vediamo

15
00:00:42,660 --> 00:00:43,890
è un array di un elemento.

16
00:00:43,890 --> 00:00:47,720
E per definizione, uno
matrice elemento è ordinato.

17
00:00:47,720 --> 00:00:50,850
>> Poi ci ripete questo processo until--
ci ripetiamo il seguente processo

18
00:00:50,850 --> 00:00:52,900
fino a quando tutti gli elementi sono ordinati.

19
00:00:52,900 --> 00:00:57,770
Guardate il prossimo elemento misti e
inserirla nella porzione ordinata,

20
00:00:57,770 --> 00:01:01,209
spostando il numero richiesto
di elementi di mezzo.

21
00:01:01,209 --> 00:01:03,750
Speriamo che questa visualizzazione
vi aiuterà a vedere esattamente che cosa è

22
00:01:03,750 --> 00:01:05,980
succedendo con insertion sort.

23
00:01:05,980 --> 00:01:08,010
>> Quindi, di nuovo, ecco la nostra
intero array indifferenziati,

24
00:01:08,010 --> 00:01:10,970
tutti gli elementi indicati in rosso.

25
00:01:10,970 --> 00:01:13,320
E seguiamo il
passi del nostro pseudocodice.

26
00:01:13,320 --> 00:01:16,970
La prima cosa che facciamo, è che chiamiamo
primo elemento dell'array, filtrate.

27
00:01:16,970 --> 00:01:20,920
Così siamo solo dire andando
cinque, il gioco è ora risolto.

28
00:01:20,920 --> 00:01:24,570
>> Poi guardiamo alla prossima
elemento indifferenziato della matrice

29
00:01:24,570 --> 00:01:27,610
e vogliamo inserire tale
nella porzione filtrate,

30
00:01:27,610 --> 00:01:29,750
spostando gli elementi sopra.

31
00:01:29,750 --> 00:01:33,470
Così due è il prossimo indifferenziati
elemento della matrice.

32
00:01:33,470 --> 00:01:36,250
Chiaramente appartiene prima della
cinque, quindi quello che faremo

33
00:01:36,250 --> 00:01:41,580
è una sorta di tenere due da parte per un secondo,
spostare cinque sopra, e quindi inserire due

34
00:01:41,580 --> 00:01:43,210
prima delle cinque, dove dovrebbe andare.

35
00:01:43,210 --> 00:01:45,280
E ora possiamo dire che due è ordinato.

36
00:01:45,280 --> 00:01:48,400
>> Quindi, come potete vedere, abbiamo soltanto finora
esaminato due elementi della matrice.

37
00:01:48,400 --> 00:01:50,600
Non abbiamo guardato il
riposiamo a tutti, ma abbiamo

38
00:01:50,600 --> 00:01:54,582
GOT questi due elementi ordinati per
modo del meccanismo di spostamento.

39
00:01:54,582 --> 00:01:56,410
>> Quindi ripetiamo di nuovo il processo.

40
00:01:56,410 --> 00:01:58,850
Guardate la prossima indifferenziati
elemento, questo è uno.

41
00:01:58,850 --> 00:02:04,010
Facciamo sostengono che parte per un secondo,
spostare tutto finito, e mettere uno

42
00:02:04,010 --> 00:02:05,570
dove dovrebbe andare.

43
00:02:05,570 --> 00:02:08,110
>> Anche in questo caso, ancora, abbiamo sempre e solo
guardato uno, due e cinque.

44
00:02:08,110 --> 00:02:12,480
Noi non sappiamo che cosa altro è in arrivo,
ma abbiamo risolto questi tre elementi.

45
00:02:12,480 --> 00:02:16,030
>> Successivo elemento indifferenziati è
tre, quindi dovremo metterlo da parte.

46
00:02:16,030 --> 00:02:18,200
Ti spostiamo su quello che
necessario che, questa volta

47
00:02:18,200 --> 00:02:21,820
non è tutto come nel precedente
due casi, è solo il cinque.

48
00:02:21,820 --> 00:02:25,440
E poi ci atteniamo alle tre,
tra i due e cinque.

49
00:02:25,440 --> 00:02:27,849
>> Sei è il prossimo indifferenziati
elemento all'array.

50
00:02:27,849 --> 00:02:31,140
E infatti sei è maggiore di cinque, così
non abbiamo nemmeno bisogno di fare qualsiasi scambio.

51
00:02:31,140 --> 00:02:35,710
Possiamo solo virare sei a destra sulla
l'estremità della porzione filtrate.

52
00:02:35,710 --> 00:02:38,270
>> Infine, quattro è il
ultimo elemento non differenziati.

53
00:02:38,270 --> 00:02:42,060
Quindi dovremo metterla da parte, spostiamo sopra
gli elementi che devono passare sopra,

54
00:02:42,060 --> 00:02:43,780
e poi mettere quattro in cui essa appartiene.

55
00:02:43,780 --> 00:02:46,400
E ora guarda, abbiamo sorta
di tutti gli elementi.

56
00:02:46,400 --> 00:02:48,150
Notate con inserzione
tipo, non abbiamo avuto

57
00:02:48,150 --> 00:02:50,240
andare avanti e indietro attraverso l'array.

58
00:02:50,240 --> 00:02:54,720
Ci siamo andati solo attraverso l'array
una volta, e abbiamo spostato le cose

59
00:02:54,720 --> 00:02:59,870
che avevamo già incontrato, al fine
per fare spazio per i nuovi elementi.

60
00:02:59,870 --> 00:03:02,820
>> Allora qual è il caso peggiore
scenario con insertion sort?

61
00:03:02,820 --> 00:03:05,090
Nel caso peggiore, la
array è in ordine inverso.

62
00:03:05,090 --> 00:03:11,180
Dovete spostare ciascuno degli elementi n
fino a n posizioni, ogni volta che ci

63
00:03:11,180 --> 00:03:12,880
fare un inserimento.

64
00:03:12,880 --> 00:03:15,720
Questo è un sacco di spostamento.

65
00:03:15,720 --> 00:03:18,014
>> Nel migliore dei casi, la
array è perfettamente ordinato.

66
00:03:18,014 --> 00:03:20,680
E un po 'come quello che è successo
con cinque e sei nell'esempio,

67
00:03:20,680 --> 00:03:23,779
dove abbiamo potuto appena virare su
senza dover fare qualsiasi spostamento,

68
00:03:23,779 --> 00:03:24,820
avremmo essenzialmente facciamo.

69
00:03:24,820 --> 00:03:27,560
>> Se si immagina che la nostra
matrice era uno a sei,

70
00:03:27,560 --> 00:03:29,900
avremmo Cominciamo da
dichiarando uno è ordinato.

71
00:03:29,900 --> 00:03:33,300
Due viene dopo uno così possiamo solo
dicono, OK, bene uno e due sono ordinati.

72
00:03:33,300 --> 00:03:36,190
Tre arriva dopo due così, OK,
uno e due e tre sono ordinati.

73
00:03:36,190 --> 00:03:39,590
>> Non stiamo facendo alcun swap, siamo
semplicemente spostando questa linea arbitraria

74
00:03:39,590 --> 00:03:42,460
tra ordinato e non ordinato come andiamo.

75
00:03:42,460 --> 00:03:46,646
Nel modo più efficace come abbiamo fatto nell'esempio,
trasformando elementi blu, come si procede.

76
00:03:46,646 --> 00:03:48,270
Allora qual è il runtime caso peggiore, allora?

77
00:03:48,270 --> 00:03:51,854
Ricordate, se dobbiamo passare ciascuno di
gli n elementi eventualmente posizioni n,

78
00:03:51,854 --> 00:03:54,020
speriamo che ti dà
un'idea che il caso peggiore

79
00:03:54,020 --> 00:03:57,770
runtime è Big O di n al quadrato.

80
00:03:57,770 --> 00:04:00,220
>> Se la matrice è perfettamente
ordinato, tutto quello che dobbiamo fare

81
00:04:00,220 --> 00:04:04,480
è guardare ogni singolo elemento
una volta, e poi abbiamo finito.

82
00:04:04,480 --> 00:04:08,440
Così nel migliore dei casi, si tratta di omega di n.

83
00:04:08,440 --> 00:04:09,490
>> Sono Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Questo è CS50.

85
00:04:11,760 --> 00:04:13,119