1
00:00:00,000 --> 00:00:02,826
>> [Prehrávanie 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 iný
Algoritmus môžeme použiť pre triedenie poľa.

4
00:00:09,370 --> 00:00:12,350
Zmyslom tohto algoritmu
je budovať svoje zoradené pole

5
00:00:12,350 --> 00:00:19,670
v mieste, radenie prvkov z
spôsob, ako idete, aby uvoľnili miesto.

6
00:00:19,670 --> 00:00:22,240
To je mierne odlišný
od výberu druhu alebo bublina

7
00:00:22,240 --> 00:00:25,460
triedenie, napríklad tam, kde
sme úprave miesta,

8
00:00:25,460 --> 00:00:26,910
kde robíme swapy.

9
00:00:26,910 --> 00:00:29,760
>> V tomto prípade sme, čo sa vlastne
robí, je posuvné prvky

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

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

12
00:00:34,030 --> 00:00:37,646
No povedzme, svojvoľne povedať, že
Prvý prvok poľa je zoradené.

13
00:00:37,646 --> 00:00:38,770
Staviame na mieste.

14
00:00:38,770 --> 00:00:42,660
>> Budeme ísť jeden prvok v čase a
stavať to, a tak prvá vec, ktorú vidíme,

15
00:00:42,660 --> 00:00:43,890
je jedným z prvkov poľa.

16
00:00:43,890 --> 00:00:47,720
A samozrejme, jeden
Prvok poľa je triedený.

17
00:00:47,720 --> 00:00:50,850
>> Potom budeme tento proces opakovať until--
budeme opakovať nasledujúci postup

18
00:00:50,850 --> 00:00:52,900
kým sa všetky prvky sú zoradené.

19
00:00:52,900 --> 00:00:57,770
Pozrite sa na ďalšie netriedený prvku a
vložte ju do triedeného časti,

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

21
00:01:01,209 --> 00:01:03,750
Dúfajme, že to vizualizácia
vám pomôže vidieť presne to, čo je

22
00:01:03,750 --> 00:01:05,980
sa deje s vkladacie druhu.

23
00:01:05,980 --> 00:01:08,010
>> Takže znovu, tu je naša
Celý netriedený poľa,

24
00:01:08,010 --> 00:01:10,970
všetky prvky uvedené v červenej farbe.

25
00:01:10,970 --> 00:01:13,320
A poďme nasledujte
kroky nášho pseudokódu.

26
00:01:13,320 --> 00:01:16,970
Prvá vec, ktorú robíme, je nazývame
Prvý prvok poľa, triediť.

27
00:01:16,970 --> 00:01:20,920
Takže sme len chcel povedať
päť, teraz ste triediť.

28
00:01:20,920 --> 00:01:24,570
>> Potom sa pozrieme na ďalšie
netriedený prvok poľa

29
00:01:24,570 --> 00:01:27,610
a chceme vložiť, že
do zoradené časti,

30
00:01:27,610 --> 00:01:29,750
tým, že presúva prvkov nad.

31
00:01:29,750 --> 00:01:33,470
Takže dvoch je ďalší netriedeného
prvok poľa.

32
00:01:33,470 --> 00:01:36,250
Je zrejmé, že pred tým, než patrí
päť, takže to, čo budeme robiť

33
00:01:36,250 --> 00:01:41,580
je druh držať dvoch stranou na sekundu,
presunúť päť nad, a potom vložte dve

34
00:01:41,580 --> 00:01:43,210
pred piatou, kam by mal ísť.

35
00:01:43,210 --> 00:01:45,280
A teraz môžeme povedať, že dvaja sú zoradené.

36
00:01:45,280 --> 00:01:48,400
>> Takže ako vidíte, máme len tak ďaleko
sa pozrel na dva prvky poľa.

37
00:01:48,400 --> 00:01:50,600
Ešte sme sa pozrel na
odpočinku vôbec, ale my sme

38
00:01:50,600 --> 00:01:54,582
mám tieto dva prvky radené podľa
spôsob radiacej mechanizmus.

39
00:01:54,582 --> 00:01:56,410
>> Takže sme opäť proces opakovať.

40
00:01:56,410 --> 00:01:58,850
Pozrite sa na ďalšie netriedeného
element, to je jeden.

41
00:01:58,850 --> 00:02:04,010
Poďme si myslí, že stranou na sekundu,
posunúť všetko nad a dal jeden

42
00:02:04,010 --> 00:02:05,570
ak by malo ísť.

43
00:02:05,570 --> 00:02:08,110
>> Opäť platí, stále sme len niekedy
Pozrel sa na jeden, dva a päť.

44
00:02:08,110 --> 00:02:12,480
Nevieme, čo ešte príde,
ale my sme radené tieto tri prvky.

45
00:02:12,480 --> 00:02:16,030
>> Ďalšie netriedený prvkom je
tri, takže budeme ju bokom.

46
00:02:16,030 --> 00:02:18,200
Budeme posun nad to, čo sme
je potrebné, na ktoré, tentoraz

47
00:02:18,200 --> 00:02:21,820
nie je všetko, ako v predchádzajúcom
dva prípady, je to len päť.

48
00:02:21,820 --> 00:02:25,440
A potom budeme držať tri v,
medzi dvoma a piatimi.

49
00:02:25,440 --> 00:02:27,849
>> Šesť je ďalší netriedeného
element k poľu.

50
00:02:27,849 --> 00:02:31,140
A v skutočnosti šiestich je väčší ako päť, tak
my ani nemusíte robiť žiadne odkladanie.

51
00:02:31,140 --> 00:02:35,710
Môžeme len pripnúť šesť vpravo na
koniec zoradené časti.

52
00:02:35,710 --> 00:02:38,270
>> A konečne, štyri je
Posledná netriedený element.

53
00:02:38,270 --> 00:02:42,060
Tak sme to stranou, preexponované
prvky musíme prejsť cez,

54
00:02:42,060 --> 00:02:43,780
a potom dal štyri tam, kam patrí.

55
00:02:43,780 --> 00:02:46,400
A teraz sa pozri, máme sort
všetkých prvkov.

56
00:02:46,400 --> 00:02:48,150
Všimnite si, s vložením
triedenie, sme nemali

57
00:02:48,150 --> 00:02:50,240
ísť tam a späť cez pole.

58
00:02:50,240 --> 00:02:54,720
Šli sme len cez pole
raz, a my posunul veci

59
00:02:54,720 --> 00:02:59,870
že by sme už stretli, aby
aby sa uvoľnilo miesto pre nové prvky.

60
00:02:59,870 --> 00:03:02,820
>> Takže to, čo je najhorší prípad
Scenár s vloženie druhom?

61
00:03:02,820 --> 00:03:05,090
V najhoršom prípade sa
pole je v opačnom poradí.

62
00:03:05,090 --> 00:03:11,180
Musíte presunúť každý z n prvkov
až do polohy N, zakaždým sme

63
00:03:11,180 --> 00:03:12,880
vykonať vloženie.

64
00:03:12,880 --> 00:03:15,720
To je veľa posúvanie.

65
00:03:15,720 --> 00:03:18,014
>> V najlepšom prípade sa
Pole je dokonale zoradené.

66
00:03:18,014 --> 00:03:20,680
A niečo ako, čo sa stalo
s piatimi a šiestimi v príklade,

67
00:03:20,680 --> 00:03:23,779
kde sme mohli len pripináčika to na
aby bolo nutné robiť žiadne radenie,

68
00:03:23,779 --> 00:03:24,820
by sme v podstate robiť.

69
00:03:24,820 --> 00:03:27,560
>> Ak si predstaviť, že naše
Poľa bola jedna až šesť,

70
00:03:27,560 --> 00:03:29,900
by sme začať tým,
prehlasuje jeden je triedený.

71
00:03:29,900 --> 00:03:33,300
Dva prichádza potom, čo jeden, takže môžeme len
hovoriť, OK, dobre jedna a dve sú zoradené.

72
00:03:33,300 --> 00:03:36,190
Tri prichádza po dvoch tak, OK,
jedna a dve a tri sú zoradené.

73
00:03:36,190 --> 00:03:39,590
>> Nie sme akýmkoľvek swapy, my sme
Len pohybujúce sa tento riadok ľubovoľný

74
00:03:39,590 --> 00:03:42,460
medzi triedené a netriedené, ako sme ísť.

75
00:03:42,460 --> 00:03:46,646
Ako efektívne, ako sme to urobili v príklade,
sústruženie prvky modrej, ako budeme postupovať.

76
00:03:46,646 --> 00:03:48,270
Takže to, čo je najhorší prípad runtime, potom?

77
00:03:48,270 --> 00:03:51,854
Pamätajte si, že ak budeme musieť presunúť každý z
na n prvky prípadne n pozície,

78
00:03:51,854 --> 00:03:54,020
dúfajme, že vám dáva
idea, že najhorší prípad

79
00:03:54,020 --> 00:03:57,770
runtime je veľký O n na druhú.

80
00:03:57,770 --> 00:04:00,220
>> V prípade, že pole je dokonale
radené, všetko, čo musíte urobiť,

81
00:04:00,220 --> 00:04:04,480
je pozrieť sa na každé jednotlivé súčasti
raz, a potom sme hotoví.

82
00:04:04,480 --> 00:04:08,440
Takže v najlepšom prípade je to omega n.

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

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

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