1
00:00:00,000 --> 00:00:02,826
>> [Přehrávání hudby]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Takže insertion sort je jiný
Algoritmus můžeme použít pro třídění pole.

4
00:00:09,370 --> 00:00:12,350
Smyslem tohoto algoritmu
je budovat své seřazené pole

5
00:00:12,350 --> 00:00:19,670
v místě, řazení prvků z
způsob, jak jdete, aby uvolnily místo.

6
00:00:19,670 --> 00:00:22,240
To je mírně odlišný
od výběru druhu nebo bublina

7
00:00:22,240 --> 00:00:25,460
třídění, například tam, kde
jsme úpravě místa,

8
00:00:25,460 --> 00:00:26,910
kde děláme swapy.

9
00:00:26,910 --> 00:00:29,760
>> V tomto případě jsme, co se vlastně
dělá, je posuvné prvky

10
00:00:29,760 --> 00:00:31,390
nad, z cesty.

11
00:00:31,390 --> 00:00:34,030
Jak tento algoritmus
práce v pseudokódu?

12
00:00:34,030 --> 00:00:37,646
No řekněme, svévolně říci, že
První prvek pole je seřazeny.

13
00:00:37,646 --> 00:00:38,770
Stavíme na místě.

14
00:00:38,770 --> 00:00:42,660
>> Budeme jít jeden prvek v čase a
stavět to, a tak první věc, kterou vidíme,

15
00:00:42,660 --> 00:00:43,890
je jedním z prvků pole.

16
00:00:43,890 --> 00:00:47,720
A samozřejmě, jeden
Prvek pole je tříděn.

17
00:00:47,720 --> 00:00:50,850
>> Pak budeme tento proces opakovat until--
budeme opakovat následující postup

18
00:00:50,850 --> 00:00:52,900
dokud se všechny prvky jsou seřazeny.

19
00:00:52,900 --> 00:00:57,770
Podívejte se na další netříděný prvku a
vložte ji do tříděného části,

20
00:00:57,770 --> 00:01:01,209
posunutím požadované číslo
prvků z cesty.

21
00:01:01,209 --> 00:01:03,750
Doufejme, že to vizualizace
vám pomůže vidět přesně to, co je

22
00:01:03,750 --> 00:01:05,980
se děje s vkládací druhu.

23
00:01:05,980 --> 00:01:08,010
>> Takže znovu, tady je naše
Celý netříděný pole,

24
00:01:08,010 --> 00:01:10,970
všechny prvky uvedené v červené barvě.

25
00:01:10,970 --> 00:01:13,320
A pojďme následujte
kroky našeho pseudokódu.

26
00:01:13,320 --> 00:01:16,970
První věc, kterou děláme, je nazýváme
První prvek pole, třídit.

27
00:01:16,970 --> 00:01:20,920
Takže jsme jen chtěl říct
pět, nyní jste třídit.

28
00:01:20,920 --> 00:01:24,570
>> Pak se podíváme na další
netříděný prvek pole

29
00:01:24,570 --> 00:01:27,610
a chceme vložit, že
do seřazené části,

30
00:01:27,610 --> 00:01:29,750
tím, že přesouvá prvků nad.

31
00:01:29,750 --> 00:01:33,470
Takže dvou je další netříděného
prvek pole.

32
00:01:33,470 --> 00:01:36,250
Je zřejmé, že před tím, než patří
pět, takže to, co budeme dělat

33
00:01:36,250 --> 00:01:41,580
je druh držet dvou stranou na vteřinu,
přesunout pět nad, a pak vložte dvě

34
00:01:41,580 --> 00:01:43,210
před pátou, kam by měl jít.

35
00:01:43,210 --> 00:01:45,280
A nyní můžeme říci, že dva jsou seřazeny.

36
00:01:45,280 --> 00:01:48,400
>> Takže jak vidíte, máme jenom tak daleko
se podíval na dva prvky pole.

37
00:01:48,400 --> 00:01:50,600
Ještě jsme se podíval na
odpočinku vůbec, ale my jsme

38
00:01:50,600 --> 00:01:54,582
mám tyto dva prvky řazeny podle
způsob řadicí mechanismus.

39
00:01:54,582 --> 00:01:56,410
>> Takže jsme opět proces opakovat.

40
00:01:56,410 --> 00:01:58,850
Podívejte se na další netříděného
element, to je jeden.

41
00:01:58,850 --> 00:02:04,010
Pojďme si myslí, že stranou na vteřinu,
posunout vše nad a dal jeden

42
00:02:04,010 --> 00:02:05,570
pokud by mělo jít.

43
00:02:05,570 --> 00:02:08,110
>> Opět platí, stále jsme jen někdy
Podíval se na jeden, dva a pět.

44
00:02:08,110 --> 00:02:12,480
Nevíme, co ještě přijde,
ale my jsme řazeny tyto tři prvky.

45
00:02:12,480 --> 00:02:16,030
>> Další netříděný prvkem je
tři, takže budeme ji stranou.

46
00:02:16,030 --> 00:02:18,200
Budeme posun nad to, co jsme
je třeba, na které, tentokrát

47
00:02:18,200 --> 00:02:21,820
není všechno, jak v předchozím
dva případy, je to jen pět.

48
00:02:21,820 --> 00:02:25,440
A pak budeme držet tři v,
mezi dvěma a pěti.

49
00:02:25,440 --> 00:02:27,849
>> Šest je další netříděného
element k poli.

50
00:02:27,849 --> 00:02:31,140
A ve skutečnosti šesti je větší než pět, tak
my ani nemusíte dělat žádné odkládání.

51
00:02:31,140 --> 00:02:35,710
Můžeme jen připnout šest vpravo na
konec seřazené části.

52
00:02:35,710 --> 00:02:38,270
>> A konečně, čtyři je
Poslední netříděný element.

53
00:02:38,270 --> 00:02:42,060
Tak jsme to stranou, PŘEEXPONOVÁNO
prvky musíme přejít přes,

54
00:02:42,060 --> 00:02:43,780
a pak dal čtyři tam, kam patří.

55
00:02:43,780 --> 00:02:46,400
A teď se podívej, máme sort
všech prvků.

56
00:02:46,400 --> 00:02:48,150
Všimněte si, s vložením
třídění, jsme neměli

57
00:02:48,150 --> 00:02:50,240
jít tam a zpět přes pole.

58
00:02:50,240 --> 00:02:54,720
Šli jsme jen přes pole
jednou, a my posunul věci

59
00:02:54,720 --> 00:02:59,870
že bychom již setkali, aby
aby se uvolnilo místo pro nové prvky.

60
00:02:59,870 --> 00:03:02,820
>> Takže to, co je nejhorší případ
Scénář s vložení druhem?

61
00:03:02,820 --> 00:03:05,090
V nejhorším případě se
pole je v opačném pořadí.

62
00:03:05,090 --> 00:03:11,180
Musíte přesunout každý z n prvků
až do polohy N, pokaždé jsme

63
00:03:11,180 --> 00:03:12,880
provést vložení.

64
00:03:12,880 --> 00:03:15,720
To je hodně posouvání.

65
00:03:15,720 --> 00:03:18,014
>> V nejlepším případě se
Pole je dokonale seřazeny.

66
00:03:18,014 --> 00:03:20,680
A něco jako, co se stalo
s pěti a šesti v příkladu,

67
00:03:20,680 --> 00:03:23,779
kde jsme mohli jen připínáček to na
aniž by bylo nutné dělat žádné řazení,

68
00:03:23,779 --> 00:03:24,820
bychom v podstatě dělat.

69
00:03:24,820 --> 00:03:27,560
>> Pokud si představit, že naše
Pole byla jedna až šest,

70
00:03:27,560 --> 00:03:29,900
bychom začít tím,
prohlašuje jeden je tříděn.

71
00:03:29,900 --> 00:03:33,300
Dva přichází poté, co jeden, takže můžeme jen
říkat, OK, dobře jedna a dvě jsou seřazeny.

72
00:03:33,300 --> 00:03:36,190
Tři přichází po dvou tak, OK,
jedna a dvě a tři jsou seřazeny.

73
00:03:36,190 --> 00:03:39,590
>> Nejsme jakýmkoliv swapy, my jsme
Jen pohybující se tento řádek libovolný

74
00:03:39,590 --> 00:03:42,460
mezi tříděny a netříděné, jak jsme jít.

75
00:03:42,460 --> 00:03:46,646
Jak efektivně, jako jsme to udělali v příkladu,
soustružení prvky modré, jak budeme postupovat.

76
00:03:46,646 --> 00:03:48,270
Takže to, co je nejhorší případ runtime, pak?

77
00:03:48,270 --> 00:03:51,854
Pamatujte si, že pokud budeme muset přesunout každý z
na n prvky případně n pozice,

78
00:03:51,854 --> 00:03:54,020
doufejme, že vám dává
idea, že nejhorší případ

79
00:03:54,020 --> 00:03:57,770
runtime je velký O n na druhou.

80
00:03:57,770 --> 00:04:00,220
>> V případě, že pole je dokonale
řazeny, vše, co musíte udělat,

81
00:04:00,220 --> 00:04:04,480
je podívat se na každé jednotlivé součásti
jednou, a pak jsme hotovi.

82
00:04:04,480 --> 00:04:08,440
Takže v nejlepším případě je to omega n.

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

84
00:04:09,490 --> 00:04:11,760
To je CS50.

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