1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Vkladanie Triediť]

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
Poďme sa pozrieť na vloženie radiť, algoritmus pre prijatie zoznamu čísel a triedenie.

5
00:00:13,060 --> 00:00:18,300
Algoritmus, pamätajte, je jednoducho krok-za-krokom postup pre dosiahnutie úlohy.

6
00:00:18,300 --> 00:00:23,640
Základnou myšlienkou vloženie radiť, je rozdeliť na náš zoznam na dve časti,

7
00:00:23,640 --> 00:00:26,580
sú zoradené časť a netriedené časť.

8
00:00:26,580 --> 00:00:29,290
>> Na každom kroku algoritmu, je presunutá číslo

9
00:00:29,290 --> 00:00:32,439
z netriedeného časti do triedeného časti

10
00:00:32,439 --> 00:00:35,680
až nakoniec je zoradená celý zoznam.

11
00:00:35,680 --> 00:00:43,340
Tu je zoznam šiestich netriedených čísel - 23, 42, 4, 16, 8, a 15.

12
00:00:43,340 --> 00:00:47,680
Vzhľadom k tomu, že tieto čísla nie sú všetko vo vzostupnom poradí, to netriedený oni.

13
00:00:47,680 --> 00:00:53,890
Vzhľadom k tomu, sme sa začali radenie doteraz, budeme uvažovať o všetkých šiestich prvkov našej netriedeného časť.

14
00:00:53,890 --> 00:00:59,270
>> Akonáhle začneme triedenie, dáme tieto zoradené čísla vľavo od nich.

15
00:00:59,270 --> 00:01:03,600
Takže, poďme začať s 23, prvý prvok v našom zozname.

16
00:01:03,600 --> 00:01:06,930
Nemáme žiadne prvky v našej zoradené časti ešte,

17
00:01:06,930 --> 00:01:12,460
takže sa poďme jednoducho považujú 23 za začiatok a koniec našej triedeného časti.

18
00:01:12,460 --> 00:01:16,510
Teraz, naše zoradené časť má jedno číslo, 23,

19
00:01:16,510 --> 00:01:20,260
a naše netriedeného časť má týchto päť čísel.

20
00:01:20,260 --> 00:01:27,320
Poďme sa teraz vložiť ďalšie číslo v našom netriedeného časti, 42, do triedeného časti.

21
00:01:27,320 --> 00:01:35,930
>> Ak chcete tak urobiť, budeme musieť porovnať 42 k 23 - jediný prvok v našom zoradené časti tak ďaleko.

22
00:01:35,930 --> 00:01:41,980
Štyridsaťdva je väčší ako 23, takže sa môže jednoducho pripojiť 42 až do konca

23
00:01:41,980 --> 00:01:45,420
z triedeného časti zoznamu. Výborne!

24
00:01:45,420 --> 00:01:51,850
Teraz náš zoradené časť má dva prvky, a naše rôzne časť má štyri prvky.

25
00:01:51,850 --> 00:01:57,200
Takže, poďme sa teraz presunúť do 4, ďalší prvok v netriedeného časti.

26
00:01:57,200 --> 00:02:00,230
Tak by kde sa tento umiestni do triedeného časti?

27
00:02:00,230 --> 00:02:04,220
>> Pamätajte si, že chceme umiestniť toto číslo v zoradené poradí

28
00:02:04,220 --> 00:02:08,680
takže naše zoradené časť zostáva správne zoradené za všetkých okolností.

29
00:02:08,680 --> 00:02:14,380
Ak umiestnime 4 na pravej strane 42, potom sa náš zoznam bude mimo prevádzky.

30
00:02:14,380 --> 00:02:18,380
Takže, poďme pokračovať v pohybe sprava doľava v našom druhu porciu.

31
00:02:18,380 --> 00:02:23,260
Ako sme sa presťahovať, poďme posunúť každé číslo nadol na miesto, aby sa priestor pre nové číslo.

32
00:02:25,440 --> 00:02:31,740
Dobre, 4 je tiež menej ako 23, takže nemôžeme umiestniť ani tu.

33
00:02:31,740 --> 00:02:34,480
Poďme sa 23 vpravo o jedno miesto.

34
00:02:36,500 --> 00:02:43,120
>> To znamená, že by sme chceli umiestniť 4 do prvého slotu v zoradené časti.

35
00:02:43,120 --> 00:02:46,300
Všimnite si, ako tento priestor v zozname bola už prázdna,

36
00:02:46,300 --> 00:02:51,120
pretože sme boli pohybuje zoradené prvky dole, ako sme sa stretol s nimi.

37
00:02:51,120 --> 00:02:52,740
Dobrá. Takže, sme v polovici cesty.

38
00:02:52,740 --> 00:02:57,990
Poďme pokračovať v našej algoritmus vložením 16 do triedeného časti.

39
00:02:59,260 --> 00:03:03,820
Šestnásť je menší ako 42, takže sa poďme posunúť 42 na pravej strane.

40
00:03:05,700 --> 00:03:10,190
Šestnásť je tiež menej ako 23, takže sa poďme tiež posunúť tento prvok.

41
00:03:11,790 --> 00:03:20,820
>> Teraz, 16 je väčší ako 4. Takže to vyzerá, že by sme chceli vložiť 16 medzi 4 a 23.

42
00:03:20,820 --> 00:03:24,620
Pri pohybe cez zoradené časti zoznamu sprava doľava,

43
00:03:24,620 --> 00:03:29,160
4 je prvé číslo sme vidieť, že je menšie, než je počet

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

45
00:03:31,540 --> 00:03:35,820
Tak, teraz môžeme vložiť 16 do tohto prázdneho slotu,

46
00:03:35,820 --> 00:03:40,520
ktoré, pamätajte, sme vytvorili pohybliv prvky v radenia časti nad

47
00:03:40,520 --> 00:03:43,340
ako sme sa stretli je.

48
00:03:43,340 --> 00:03:47,900
>> Dobrá. Teraz, máme štyri zoradené prvky a dve netriedené prvky.

49
00:03:47,900 --> 00:03:51,600
Takže, poďme presunúť 8 do triedeného časti.

50
00:03:51,600 --> 00:03:55,010
Osem je menší ako 42.

51
00:03:55,010 --> 00:03:56,940
Osem je menší ako 23.

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

53
00:04:00,230 --> 00:04:03,110
Ale 8 je väčšia ako 4.

54
00:04:03,110 --> 00:04:07,280
Takže by sme chceli vložiť 8 medzi 4 a 16.

55
00:04:09,070 --> 00:04:13,650
A teraz máme len jednu väčšiu zostáva prvok k radeniu - The 15.

56
00:04:13,950 --> 00:04:16,589
Pätnásť je nižší ako 42,

57
00:04:16,589 --> 00:04:19,130
Pätnásť je menší ako 23.

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

59
00:04:21,750 --> 00:04:24,810
Ale 15 je väčší ako 8.

60
00:04:24,810 --> 00:04:27,440
>> Takže, tu je miesto, kde chceme, aby sa naše konečné vloženie.

61
00:04:28,770 --> 00:04:30,330
A sme hotoví.

62
00:04:30,330 --> 00:04:33,540
Nemáme žiadne ďalšie prvky v netriedeného časti,

63
00:04:33,540 --> 00:04:36,670
a naše zoradené časť je v správnom poradí.

64
00:04:36,670 --> 00:04:40,270
Čísla sú zoradené od najmenšej k najväčšej.

65
00:04:40,270 --> 00:04:44,330
Takže, poďme sa pozrieť na niektoré pseudokódu, ktorý popisuje kroky, sme práve vykonali.

66
00:04:46,760 --> 00:04:51,740
>> Na riadku 1, môžeme vidieť, že budeme musieť iteráciu každý prvok v zozname

67
00:04:51,740 --> 00:04:57,060
okrem prvej, bude od prvého prvku v netriedeného časti jednoducho sa

68
00:04:57,060 --> 00:05:00,220
prvý prvok v triedenom časti.

69
00:05:00,220 --> 00:05:06,320
Na riadkoch 2 a 3, sme sledovaní nášho súčasného miesta v netriedeného časti.

70
00:05:06,320 --> 00:05:10,450
Element reprezentuje číslo v súčasnej dobe pohybuje do triedeného časti,

71
00:05:10,450 --> 00:05:15,600
a j reprezentuje náš index do netriedeného časti.

72
00:05:15,600 --> 00:05:20,980
>> Na riadku 4, sme iterácie sú zoradené časti sprava doľava.

73
00:05:20,980 --> 00:05:26,010
Chceme zastaviť iterácie, akonáhle prvku na ľavej strane našej súčasnej pozície

74
00:05:26,010 --> 00:05:30,050
je menšia ako prvok sa snažíme vložiť.

75
00:05:30,050 --> 00:05:35,600
Na riadku 5, sme presúva každý prvok my sa stretneme o jedno miesto vpravo.

76
00:05:35,600 --> 00:05:40,950
Tak, budeme mať voľný priestor pre vloženie do kedy nájdeme prvý prvok

77
00:05:40,950 --> 00:05:44,080
menej ako prvku Sťahujeme.

78
00:05:44,080 --> 00:05:50,800
Na riadku 6, sme aktualizáciu nášho počítadla naďalej pohybovať doľava cez zoradené časť.

79
00:05:50,800 --> 00:05:56,860
A konečne, na riadku 7, sme vkladanie prvku do triedeného časti zoznamu.

80
00:05:56,860 --> 00:06:00,020
>> Vieme, že je to v poriadku vložiť do polohy j,

81
00:06:00,020 --> 00:06:05,360
preto, že sme už presťahovali prvok, ktorý býval tam jedno miesto vpravo.

82
00:06:05,360 --> 00:06:09,460
Pamätajte si, že ideme cez zoradené časť sprava doľava,

83
00:06:09,460 --> 00:06:13,960
ale ideme cez netriedeného časť zľava doprava.

84
00:06:13,960 --> 00:06:19,090
Dobrá. Poďme sa teraz pozrieť na to, ako dlho beží, že algoritmus sa.

85
00:06:19,090 --> 00:06:25,300
Ukážeme si klásť otázku, ako dlho to trvá, než to algoritmus bežať v najhoršom prípade.

86
00:06:25,300 --> 00:06:29,040
Pripomeňme si, že zastupujeme tento bežiaci čas s Big O notácie.

87
00:06:32,530 --> 00:06:38,500
Pokiaľ ich chcete zoradiť náš zoznam, museli sme iteráciu prvky v netriedeného časti,

88
00:06:38,500 --> 00:06:43,430
a pre každý z týchto prvkov, prípadne cez všetky prvky v usporiadanej časti.

89
00:06:43,430 --> 00:06:47,950
Intuitívne, to znie ako O (n ^ 2) prevádzky.

90
00:06:47,950 --> 00:06:51,840
>> Pri pohľade na našom pseudokódu, máme slučku vnorené vo vnútri inej slučky,

91
00:06:51,840 --> 00:06:55,290
, Ktorá napokon znie ako O (n ^ 2) prevádzky.

92
00:06:55,290 --> 00:07:01,590
Avšak, sú zoradené časť zoznamu neobsahovala celý zoznam až do samého konca.

93
00:07:01,590 --> 00:07:06,920
Napriek tomu by sme mohli potenciálne vložiť nový prvok na samom začiatku triedeného časti

94
00:07:06,920 --> 00:07:09,320
na každej iterácii algoritmu,

95
00:07:09,320 --> 00:07:14,500
čo znamená, že by sme sa pozrieť na každý prvok v súčasnej dobe v triedenom časti.

96
00:07:14,500 --> 00:07:20,090
Takže, to znamená, že by mohli vytvoriť jednu porovnaní pre druhý prvok,

97
00:07:20,090 --> 00:07:24,660
dve porovnaní na tretí prvok, a tak ďalej.

98
00:07:24,660 --> 00:07:32,480
Takže, celkový počet krokov je súčet celých čísel od 1 do dĺžky zoznamu mínus 1.

99
00:07:32,480 --> 00:07:35,240
Môžeme reprezentovať to s sumácia.

100
00:07:41,170 --> 00:07:47,270
>> Nebudeme zachádzať do summations tu, ale ukazuje sa, že toto zhrnutie je rovná

101
00:07:47,270 --> 00:07:57,900
n (n - 1) v priebehu 2, ktorý je ekvivalentný n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Keď sa hovorí o asymptotickej behu,

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

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

105
00:08:11,430 --> 00:08:16,150
Čo keď sme bežali vloženie Radiť už triedenom zozname.

106
00:08:16,150 --> 00:08:20,960
V tomto prípade by sme jednoducho vybudovať zoradená časť zľava doprava.

107
00:08:20,960 --> 00:08:25,050
Takže, budeme potrebovať len na poradie krokov n

108
00:08:25,050 --> 00:08:29,740
>> To znamená, že vkladanie spôsob má najlepšie prípadu výkon n,

109
00:08:29,740 --> 00:08:34,130
ktoré predstavujú s Ω (n).

110
00:08:34,130 --> 00:08:36,190
A to je pre vloženie radiť,

111
00:08:36,190 --> 00:08:40,429
len jeden z mnohých algoritmov môžeme použiť na zoradenie zoznamu.

112
00:08:40,429 --> 00:08:43,210
Moje meno 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 jednoducho nemôže prestať, že akonáhle začne.

115
00:09:01,620 --> 00:09:04,760
Oh, sme urobili - >> Boom!