1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Vkládání Třídit]

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

3
00:00:04,240 --> 00:00:07,290
[To je CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Pojďme se podívat na vložení řadit, algoritmus pro přijetí seznamu čísel a třídění.

5
00:00:13,060 --> 00:00:18,300
Algoritmus, pamatujte, je prostě krok-za-krokem postup pro dosažení úkolu.

6
00:00:18,300 --> 00:00:23,640
Základní myšlenkou vložení řadit, je rozdělit na náš seznam na dvě části,

7
00:00:23,640 --> 00:00:26,580
jsou seřazena část a netříděné část.

8
00:00:26,580 --> 00:00:29,290
>> Na každém kroku algoritmu, je přesunuta číslo

9
00:00:29,290 --> 00:00:32,439
z netříděného části do tříděného části

10
00:00:32,439 --> 00:00:35,680
až nakonec je seřazena celý seznam.

11
00:00:35,680 --> 00:00:43,340
Zde je seznam šesti netříděných čísel - 23, 42, 4, 16, 8, a 15.

12
00:00:43,340 --> 00:00:47,680
Vzhledem k tomu, že tato čísla nejsou vše ve vzestupném pořadí, to netříděný oni.

13
00:00:47,680 --> 00:00:53,890
Vzhledem k tomu, jsme se začali řazení dosud, budeme uvažovat o všech šesti prvků naší netříděného část.

14
00:00:53,890 --> 00:00:59,270
>> Jakmile začneme třídění, dáme tyto seřazené čísla vlevo od nich.

15
00:00:59,270 --> 00:01:03,600
Takže, pojďme začít s 23, první prvek v našem seznamu.

16
00:01:03,600 --> 00:01:06,930
Nemáme žádné prvky v naší seřazeny části ještě,

17
00:01:06,930 --> 00:01:12,460
takže se pojďme prostě považují 23 za začátek a konec naší tříděného části.

18
00:01:12,460 --> 00:01:16,510
Nyní, naše seřazeny část má jedno číslo, 23,

19
00:01:16,510 --> 00:01:20,260
a naše netříděného část má těchto pět čísel.

20
00:01:20,260 --> 00:01:27,320
Pojďme se nyní vložit další číslo v našem netříděného části, 42, do tříděného části.

21
00:01:27,320 --> 00:01:35,930
>> Chcete-li tak učinit, budeme muset porovnat 42 k 23 - jediný prvek v našem seřazeny části tak daleko.

22
00:01:35,930 --> 00:01:41,980
Dvaačtyřicet je větší než 23, takže se může jednoduše připojit 42 až do konce

23
00:01:41,980 --> 00:01:45,420
z tříděného části seznamu. Výborně!

24
00:01:45,420 --> 00:01:51,850
Nyní náš seřazeny část má dva prvky, a naše různě část má čtyři prvky.

25
00:01:51,850 --> 00:01:57,200
Takže, pojďme se teď přesunout do 4, další prvek v netříděného části.

26
00:01:57,200 --> 00:02:00,230
Tak by kde se tento umístí do tříděného části?

27
00:02:00,230 --> 00:02:04,220
>> Pamatujte si, že chceme umístit toto číslo v seřazeném pořadí

28
00:02:04,220 --> 00:02:08,680
takže naše seřazeny část zůstává správně seřazeny za všech okolností.

29
00:02:08,680 --> 00:02:14,380
Pokud umístíme 4 na pravé straně 42, pak se náš seznam bude mimo provoz.

30
00:02:14,380 --> 00:02:18,380
Takže, pojďme pokračovat v pohybu zprava doleva v našem druhu porci.

31
00:02:18,380 --> 00:02:23,260
Jak jsme se přestěhovat, pojďme posunout každé číslo dolů na místo, aby se prostor pro nové číslo.

32
00:02:25,440 --> 00:02:31,740
Dobře, 4 je také méně než 23, takže nemůžeme umístit ani zde.

33
00:02:31,740 --> 00:02:34,480
Pojďme se 23 vpravo o jedno místo.

34
00:02:36,500 --> 00:02:43,120
>> To znamená, že bychom chtěli umístit 4 do prvního slotu v seřazeny části.

35
00:02:43,120 --> 00:02:46,300
Všimněte si, jak tento prostor v seznamu byla již prázdná,

36
00:02:46,300 --> 00:02:51,120
protože jsme byli pohybuje seřazené prvky dolů, jak jsme se setkal s nimi.

37
00:02:51,120 --> 00:02:52,740
Dobrá. Takže, jsme v půli cesty.

38
00:02:52,740 --> 00:02:57,990
Pojďme pokračovat v naší algoritmus vložením 16 do tříděného části.

39
00:02:59,260 --> 00:03:03,820
Šestnáct je menší než 42, takže se pojďme posunout 42 na pravé straně.

40
00:03:05,700 --> 00:03:10,190
Šestnáct je také méně než 23, takže se pojďme také posunout tento prvek.

41
00:03:11,790 --> 00:03:20,820
>> Nyní, 16 je větší než 4. Takže to vypadá, že bychom chtěli vložit 16 mezi 4 a 23.

42
00:03:20,820 --> 00:03:24,620
Při pohybu přes seřazeny části seznamu zprava doleva,

43
00:03:24,620 --> 00:03:29,160
4 je první číslo jsme vidět, že je menší, než je počet

44
00:03:29,160 --> 00:03:31,540
snažíme vložit.

45
00:03:31,540 --> 00:03:35,820
Tak, teď můžeme vložit 16 do tohoto prázdného slotu,

46
00:03:35,820 --> 00:03:40,520
které, pamatujte, jsme vytvořili pohybliv prvky v řazení části nad

47
00:03:40,520 --> 00:03:43,340
jak jsme se setkali je.

48
00:03:43,340 --> 00:03:47,900
>> Dobrá. Nyní, máme čtyři seřazené prvky a dvě netříděné prvky.

49
00:03:47,900 --> 00:03:51,600
Takže, pojďme přesunout 8 do tříděného části.

50
00:03:51,600 --> 00:03:55,010
Osm je menší než 42.

51
00:03:55,010 --> 00:03:56,940
Osm je menší než 23.

52
00:03:56,940 --> 00:04:00,230
A 8 je menší než 16.

53
00:04:00,230 --> 00:04:03,110
Ale 8 je větší než 4.

54
00:04:03,110 --> 00:04:07,280
Takže bychom chtěli vložit 8 mezi 4 a 16.

55
00:04:09,070 --> 00:04:13,650
A teď máme jen jednu větší zbývá prvek k řazení - The 15.

56
00:04:13,950 --> 00:04:16,589
Patnáct je nižší než 42,

57
00:04:16,589 --> 00:04:19,130
Patnáct je menší než 23.

58
00:04:19,130 --> 00:04:21,750
A 15 je menší než 16.

59
00:04:21,750 --> 00:04:24,810
Ale 15 je větší než 8.

60
00:04:24,810 --> 00:04:27,440
>> Takže, tady je místo, kde chceme, aby se naše konečné vložení.

61
00:04:28,770 --> 00:04:30,330
A jsme hotovi.

62
00:04:30,330 --> 00:04:33,540
Nemáme žádné další prvky v netříděného části,

63
00:04:33,540 --> 00:04:36,670
a naše seřazeny část je ve správném pořadí.

64
00:04:36,670 --> 00:04:40,270
Čísla jsou seřazeny od nejmenší k největší.

65
00:04:40,270 --> 00:04:44,330
Takže, pojďme se podívat na některé pseudokódu, který popisuje kroky, jsme právě provedli.

66
00:04:46,760 --> 00:04:51,740
>> Na řádku 1, můžeme vidět, že budeme muset iteraci každý prvek v seznamu

67
00:04:51,740 --> 00:04:57,060
kromě první, bude od prvního prvku v netříděného části jednoduše se

68
00:04:57,060 --> 00:05:00,220
první prvek v tříděném části.

69
00:05:00,220 --> 00:05:06,320
Na řádcích 2 a 3, jsme sledování našeho současného místa v netříděného části.

70
00:05:06,320 --> 00:05:10,450
Element reprezentuje číslo v současné době pohybuje do tříděného části,

71
00:05:10,450 --> 00:05:15,600
a j reprezentuje náš index do netříděného části.

72
00:05:15,600 --> 00:05:20,980
>> Na řádku 4, jsme iterace jsou seřazeny části zprava doleva.

73
00:05:20,980 --> 00:05:26,010
Chceme zastavit iterace, jakmile prvku na levé straně naší současné pozice

74
00:05:26,010 --> 00:05:30,050
je menší než prvek se snažíme vložit.

75
00:05:30,050 --> 00:05:35,600
Na řádku 5, jsme přesouvá každý prvek my se setkáme o jedno místo vpravo.

76
00:05:35,600 --> 00:05:40,950
Tak, budeme mít volný prostor pro vložení do kdy najdeme první prvek

77
00:05:40,950 --> 00:05:44,080
méně než prvku Stěhujeme.

78
00:05:44,080 --> 00:05:50,800
Na řádku 6, jsme aktualizaci našeho počítadla nadále pohybovat doleva přes seřazeny část.

79
00:05:50,800 --> 00:05:56,860
A konečně, na řádku 7, jsme vkládání prvku do tříděného části seznamu.

80
00:05:56,860 --> 00:06:00,020
>> Víme, že je to v pořádku vložit do polohy j,

81
00:06:00,020 --> 00:06:05,360
proto, že jsme již přestěhovali prvek, který býval tam jedno místo vpravo.

82
00:06:05,360 --> 00:06:09,460
Pamatujte si, že jdeme přes seřazeny část zprava doleva,

83
00:06:09,460 --> 00:06:13,960
ale jdeme přes netříděného část zleva doprava.

84
00:06:13,960 --> 00:06:19,090
Dobrá. Pojďme se teď podívat na to, jak dlouho běží, že algoritmus se.

85
00:06:19,090 --> 00:06:25,300
Ukážeme si klást otázku, jak dlouho to trvá, než to algoritmus běžet v nejhorším případě.

86
00:06:25,300 --> 00:06:29,040
Připomeňme si, že zastupujeme tento běžící čas s Big O notace.

87
00:06:32,530 --> 00:06:38,500
Pokud je chcete seřadit náš seznam, museli jsme iteraci prvky v netříděného části,

88
00:06:38,500 --> 00:06:43,430
a pro každý z těchto prvků, případně přes všechny prvky v uspořádané části.

89
00:06:43,430 --> 00:06:47,950
Intuitivně, to zní jako O (n ^ 2) provozu.

90
00:06:47,950 --> 00:06:51,840
>> Při pohledu na našem pseudokódu, máme smyčku vnořené uvnitř jiné smyčky,

91
00:06:51,840 --> 00:06:55,290
, která ostatně zní jako O (n ^ 2) provozu.

92
00:06:55,290 --> 00:07:01,590
Nicméně, jsou seřazeny část seznamu neobsahovala celý seznam až do samého konce.

93
00:07:01,590 --> 00:07:06,920
Přesto bychom mohli potenciálně vložit nový prvek na samém počátku tříděného části

94
00:07:06,920 --> 00:07:09,320
na každé iteraci algoritmu,

95
00:07:09,320 --> 00:07:14,500
což znamená, že bychom se podívat na každý prvek v současné době v tříděném části.

96
00:07:14,500 --> 00:07:20,090
Takže, to znamená, že by mohly vytvořit jednu srovnání pro druhý prvek,

97
00:07:20,090 --> 00:07:24,660
dvě srovnání na třetí prvek, a tak dále.

98
00:07:24,660 --> 00:07:32,480
Takže, celkový počet kroků je součet celých čísel od 1 do délky seznamu mínus 1.

99
00:07:32,480 --> 00:07:35,240
Můžeme reprezentovat to s sumace.

100
00:07:41,170 --> 00:07:47,270
>> Nebudeme zacházet do summations zde, ale ukazuje se, že toto shrnutí je rovna

101
00:07:47,270 --> 00:07:57,900
n (n - 1) v průběhu 2, který je ekvivalentní n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Když se mluví o asymptotické běhu,

103
00:08:00,800 --> 00:08:05,170
tento n ^ 2 termín bude ovládat tento n termín.

104
00:08:05,170 --> 00:08:11,430
Takže, vložení sort Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Co když jsme běželi vložení Řadit již tříděném seznamu.

106
00:08:16,150 --> 00:08:20,960
V tomto případě bychom jednoduše vybudovat seřazena část zleva doprava.

107
00:08:20,960 --> 00:08:25,050
Takže, budeme potřebovat pouze na pořadí kroků n.

108
00:08:25,050 --> 00:08:29,740
>> To znamená, že vkládání způsob má nejlépe případu výkon n,

109
00:08:29,740 --> 00:08:34,130
které představují s Ω (n).

110
00:08:34,130 --> 00:08:36,190
A to je pro vložení řadit,

111
00:08:36,190 --> 00:08:40,429
jen jeden z mnoha algoritmů můžeme použít k seřazení seznamu.

112
00:08:40,429 --> 00:08:43,210
Mé jméno je Tommy, a to je CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, si prostě nemůže přestat, že jakmile začne.

115
00:09:01,620 --> 00:09:04,760
Oh, jsme udělali - >> Boom!