1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Täiendus Sorteeri]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvardi Ülikool]

3
00:00:04,240 --> 00:00:07,290
[See on CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Võtame pilk sisestamise sorteerida, algoritm võttes numbrite loendi ja sorteerimine neid.

5
00:00:13,060 --> 00:00:18,300
Algoritm, pea meeles, on lihtsalt samm-sammult korra saavutamise ülesanne.

6
00:00:18,300 --> 00:00:23,640
Põhiidee sisestamise sorteerida, on jagada oma nimekirja kaheks osaks,

7
00:00:23,640 --> 00:00:26,580
järjestatud osa ja sorteerimata osa.

8
00:00:26,580 --> 00:00:29,290
>> Igal sammul algoritm, number on teisaldatud

9
00:00:29,290 --> 00:00:32,439
alates sortimata osal järjestatud osa

10
00:00:32,439 --> 00:00:35,680
kuni lõpuks kogu nimekirja sorteeritakse.

11
00:00:35,680 --> 00:00:43,340
Siin on nimekiri kuue sortimata numbrid - 23, 42, 4, 16, 8, ja 15.

12
00:00:43,340 --> 00:00:47,680
Kuna need numbrid ei ole kõik tõusvas järjekorras, nad sortimata.

13
00:00:47,680 --> 00:00:53,890
Kuna me ei ole alustatud sorteerimine veel, me kaaluma kõiki kuus elementi meie sorteerimata osa.

14
00:00:53,890 --> 00:00:59,270
>> Kui hakkame sorteerimine, me paneme need järjestatud numbrite vasakul need.

15
00:00:59,270 --> 00:01:03,600
Niisiis, alustame 23, esimene osa meie nimekirjas.

16
00:01:03,600 --> 00:01:06,930
Meil ei ole ühtegi elementi meie järjestatud osa veel,

17
00:01:06,930 --> 00:01:12,460
niiet lihtsalt kaaluda 23 olema alguse ja lõpu meie järjestatud osa.

18
00:01:12,460 --> 00:01:16,510
Nüüd on meie järjestatud osa on üks arv, 23,

19
00:01:16,510 --> 00:01:20,260
ja meie sorteerimata osa on need viis numbrit.

20
00:01:20,260 --> 00:01:27,320
Lähme nüüd pane uus number meie sorteerimata osa, 42, arvesse järjestatud osa.

21
00:01:27,320 --> 00:01:35,930
>> Selleks vajame võrrelda 42 kuni 23 - ainult osa meie järjestatud osa siiani.

22
00:01:35,930 --> 00:01:41,980
Nelikümmend kaks on suurem kui 23, nii me lihtsalt lisada 42 kuni lõpuni

23
00:01:41,980 --> 00:01:45,420
on järjestatud osa nimekirjast. Suurepärane!

24
00:01:45,420 --> 00:01:51,850
Nüüd on meie järjestatud osa on kaheosaline ja meie sorteerimata osa on neli elementi.

25
00:01:51,850 --> 00:01:57,200
Niisiis, oletame nüüd kolida 4 järgmine element sorteerimata osa.

26
00:01:57,200 --> 00:02:00,230
Niisiis, kui peaks see olema paigutatud järjestatud osa?

27
00:02:00,230 --> 00:02:04,220
>> Pea meeles, et me tahame panna selle numbri sorteeritud järjekorras

28
00:02:04,220 --> 00:02:08,680
nii meie järjestatud osa jääb õigesti järjestatud üldse korda.

29
00:02:08,680 --> 00:02:14,380
Kui me paneme 4 paremal 42, siis meie nimekirjas on rikkis.

30
00:02:14,380 --> 00:02:18,380
Niisiis, oletame jätkata liigub paremalt vasakule meie omamoodi osa.

31
00:02:18,380 --> 00:02:23,260
Nagu me liikuda, lähme minema iga numbri üles koht, et teha ruumi uue numbri.

32
00:02:25,440 --> 00:02:31,740
Okei, 4 on ka vähem kui 23, nii et me ei saa pannakse see siin.

33
00:02:31,740 --> 00:02:34,480
Liigume 23 õige koht.

34
00:02:36,500 --> 00:02:43,120
>> See tähendab, et me tahaks panna 4 esimesse avasse järjestatud osa.

35
00:02:43,120 --> 00:02:46,300
Märka, kuidas seda ruumi nimekirjas oli juba tühi,

36
00:02:46,300 --> 00:02:51,120
sest me oleme liikunud järjestatud elemendid maha nagu me oleme kokku puutunud nendega.

37
00:02:51,120 --> 00:02:52,740
Hea küll. Niisiis, me oleme poolel teel sinna.

38
00:02:52,740 --> 00:02:57,990
Jätkame meie algoritm, lisades 16 arvesse järjestatud osa.

39
00:02:59,260 --> 00:03:03,820
Kuusteist on alla 42, nii teeme vahetustega 42 paremale.

40
00:03:05,700 --> 00:03:10,190
Kuusteist on ka vähem kui 23, nii teeme ka minema, et element.

41
00:03:11,790 --> 00:03:20,820
>> Nüüd, 16 on suurem kui 4. Niisiis, tundub, et me tahaksime lisada 16 vahel 4 ja 23.

42
00:03:20,820 --> 00:03:24,620
Liikudes läbi järjestatud osa nimekirja paremalt vasakule,

43
00:03:24,620 --> 00:03:29,160
4 on esimene number oleme näinud, mis on väiksem kui arv

44
00:03:29,160 --> 00:03:31,540
me üritame lisada.

45
00:03:31,540 --> 00:03:35,820
Nii, nüüd saame sisestada 16 sellesse tühja pessa,

46
00:03:35,820 --> 00:03:40,520
mis pidage meeles, et me oleme loonud liikuvat elementi sorteeri osa üle

47
00:03:40,520 --> 00:03:43,340
nagu me oleme kokku puutunud nendega.

48
00:03:43,340 --> 00:03:47,900
>> Hea küll. Nüüd oleme neli järjestatud elemendid ja kaks sorteerimata elemendid.

49
00:03:47,900 --> 00:03:51,600
Nii, liigume 8 arvesse järjestatud osa.

50
00:03:51,600 --> 00:03:55,010
Kaheksa on alla 42.

51
00:03:55,010 --> 00:03:56,940
Kaheksa on alla 23.

52
00:03:56,940 --> 00:04:00,230
Ja 8 on väiksem kui 16.

53
00:04:00,230 --> 00:04:03,110
Aga 8 on üle 4.

54
00:04:03,110 --> 00:04:07,280
Niisiis, me tahaksime lisada 8 vahel 4 ja 16.

55
00:04:09,070 --> 00:04:13,650
Ja nüüd me lihtsalt veel üks element left sorteerida - 15.

56
00:04:13,950 --> 00:04:16,589
Viisteist on väiksem kui 42,

57
00:04:16,589 --> 00:04:19,130
Viisteist on alla 23.

58
00:04:19,130 --> 00:04:21,750
Ja 15 on alla 16.

59
00:04:21,750 --> 00:04:24,810
Aga 15 on suurem kui 8.

60
00:04:24,810 --> 00:04:27,440
>> Nii, siin on koht, kus me tahame, et meie lõplik sisestamist.

61
00:04:28,770 --> 00:04:30,330
Ja me oleme valmis.

62
00:04:30,330 --> 00:04:33,540
Meil pole rohkem elemente sorteerimata osa,

63
00:04:33,540 --> 00:04:36,670
ja meie järjestatud osa on õiges järjekorras.

64
00:04:36,670 --> 00:04:40,270
Numbrid on reastatud väiksemast suuremani.

65
00:04:40,270 --> 00:04:44,330
Niisiis, oletame, kui heita pilk mõned pseudokoodi, mis kirjeldab samme me lihtsalt läbi.

66
00:04:46,760 --> 00:04:51,740
>> On line 1 näeme, et me peame itereerima üle iga elemendi nimekirja

67
00:04:51,740 --> 00:04:57,060
välja arvatud esimene, sest esimene osa sorteerimata osa lihtsalt muutunud

68
00:04:57,060 --> 00:05:00,220
esimene element järjestatud osa.

69
00:05:00,220 --> 00:05:06,320
Ridadel 2 ja 3, me kursis hoida meie praegune koht sorteerimata osa.

70
00:05:06,320 --> 00:05:10,450
Element tähistab arvu me praegu liigume järjestatud osa,

71
00:05:10,450 --> 00:05:15,600
ja j esindab meie indeks sorteerimata osa.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, me itereerimise läbi järjestatud osa paremalt vasakule.

73
00:05:20,980 --> 00:05:26,010
Me soovime peatada itereerimise kui element vasakul meie praegune asukoht

74
00:05:26,010 --> 00:05:30,050
on väiksem kui element me üritame lisada.

75
00:05:30,050 --> 00:05:35,600
Real 5, me nihkub iga element kohtame ühe sammu paremale.

76
00:05:35,600 --> 00:05:40,950
Nii on meil selge ruumi lisada, kui leiame esimese elemendi

77
00:05:40,950 --> 00:05:44,080
vähem kui element me liigume.

78
00:05:44,080 --> 00:05:50,800
Real 6 uuendame me oma counter jätkuvalt liikuda vasakule läbi järjestatud osa.

79
00:05:50,800 --> 00:05:56,860
Lõpuks on line 7, me lisada element järjestatud osa nimekirjast.

80
00:05:56,860 --> 00:06:00,020
>> Me teame, et see on okei lisada positsiooni j,

81
00:06:00,020 --> 00:06:05,360
sest me oleme juba liikunud element, mis varem seal ühe sammu paremale.

82
00:06:05,360 --> 00:06:09,460
Pea meeles, et me liigume läbi järjestatud osa paremalt vasakule,

83
00:06:09,460 --> 00:06:13,960
kuid me liigume läbi sorteerimata osa vasakult paremale.

84
00:06:13,960 --> 00:06:19,090
Hea küll. Olgem nüüd pilk kui kaua töötab, et algoritm võttis.

85
00:06:19,090 --> 00:06:25,300
Me kõigepealt küsida, kui kaua see aega võtab selle algoritmi joosta halvimal juhul.

86
00:06:25,300 --> 00:06:29,040
Tuletame meelde, et me esindame see sõiduaega Big O notatsiooni.

87
00:06:32,530 --> 00:06:38,500
Selleks, et sorteerida meie nimekirjas, me pidime itereerime elemendid sorteerimata osa,

88
00:06:38,500 --> 00:06:43,430
ja iga neid elemente, potentsiaalselt üle kõik elemendid järjestatud osa.

89
00:06:43,430 --> 00:06:47,950
Intuitiivselt, see kõlab nagu O (n ^ 2) operatsiooni.

90
00:06:47,950 --> 00:06:51,840
>> Vaadates meie pseudokoodi, meil on silmus Pesastatud sees teise silmuse,

91
00:06:51,840 --> 00:06:55,290
mis tegelikult kõlab O (n ^ 2) operatsiooni.

92
00:06:55,290 --> 00:07:01,590
Kuid järjestatud osa loetelu ei sisaldanud kogu nimekirja kuni lõpuni.

93
00:07:01,590 --> 00:07:06,920
Siiski, me võiks lisada uus element alguses on järjestatud osa

94
00:07:06,920 --> 00:07:09,320
iga iteratsiooni algoritm,

95
00:07:09,320 --> 00:07:14,500
mis tähendab, et me tahaks olla vaadata iga element praegu järjestatud osa.

96
00:07:14,500 --> 00:07:20,090
Niisiis, see tähendab, et me võiks teha ühe võrdlus teise elemendi,

97
00:07:20,090 --> 00:07:24,660
kaks võrdlust kolmandat elementi, ja nii edasi.

98
00:07:24,660 --> 00:07:32,480
Niisiis, trepiastmete arv on summa täisarvud 1 kuni pikkus nimekirja miinus 1.

99
00:07:32,480 --> 00:07:35,240
Me ei esinda seda liitmise.

100
00:07:41,170 --> 00:07:47,270
>> Me ei hakka kohtuvaidlust siin, aga tuleb välja, et see liitmise võrdub

101
00:07:47,270 --> 00:07:57,900
n (n - 1) rohkem kui 2, mis on võrdne n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Rääkides asümptootilisest runtime,

103
00:08:00,800 --> 00:08:05,170
see n ^ 2 perspektiivis läheb domineerima see n perspektiivis.

104
00:08:05,170 --> 00:08:11,430
Nii sisestamise sorteerida on Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Mis siis, kui me jooksime sisestamise järgi Sorteerida juba järjestatud nimekirja.

106
00:08:16,150 --> 00:08:20,960
Sel juhul me lihtsalt luua järjestatud osa vasakult paremale.

107
00:08:20,960 --> 00:08:25,050
Niisiis, me vaid vajadus tellimusel n samme.

108
00:08:25,050 --> 00:08:29,740
>> See tähendab, et sisestamise omamoodi on parimal juhul täitmisel n,

109
00:08:29,740 --> 00:08:34,130
mis me esindame koos Ω (n).

110
00:08:34,130 --> 00:08:36,190
Ja ongi sisestamise sorteerida,

111
00:08:36,190 --> 00:08:40,429
lihtsalt üks paljudest algoritme saame kasutada sorteerida nimekirja.

112
00:08:40,429 --> 00:08:43,210
Minu nimi on Tommy, ja see on CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, sa lihtsalt ei saa lõpetada, et kui ta hakkab.

115
00:09:01,620 --> 00:09:04,760
Oh, me tegime seda - >> Boom!