1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Lisätään Lajittele]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvardin yliopisto]

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

4
00:00:07,290 --> 00:00:13,060
Katsotaanpa katsomaan lisäys lajitella algoritmi ottaa listan numeroiden ja lajittelusta.

5
00:00:13,060 --> 00:00:18,300
Algoritmi, muistan, on yksinkertaisesti askel-askeleelta menettely toteutuksessa tehtävään.

6
00:00:18,300 --> 00:00:23,640
Perusajatuksena lisäys lajitella, on jakaa meidän listan kahteen osaan,

7
00:00:23,640 --> 00:00:26,580
lajitellaan osa ja lajittelemattoman osan.

8
00:00:26,580 --> 00:00:29,290
>> Jokaisessa vaiheessa algoritmi, numero on siirretty

9
00:00:29,290 --> 00:00:32,439
alkaen lajittelemattoman osuuden lajiteltu osaan

10
00:00:32,439 --> 00:00:35,680
kunnes lopulta koko lajitellaan.

11
00:00:35,680 --> 00:00:43,340
Tässä on luettelo kuusi lajittelemattoman numerot - 23, 42, 4, 16, 8, ja 15.

12
00:00:43,340 --> 00:00:47,680
Koska nämä luvut eivät ole kaikki nousevassa järjestyksessä, he lajittelematta.

13
00:00:47,680 --> 00:00:53,890
Koska emme ole alkaneet lajittelu vielä, me harkita kaikkia kuutta osa meidän lajittelemattoman osan.

14
00:00:53,890 --> 00:00:59,270
>> Kun alamme lajittelu, laitamme nämä lajitellaan numerot vasemmalle näitä.

15
00:00:59,270 --> 00:01:03,600
Joten Aloitetaan 23, ensimmäinen elementti listalta.

16
00:01:03,600 --> 00:01:06,930
Meillä ei ole mitään elementtejä meidän lajiteltu osaan vielä,

17
00:01:06,930 --> 00:01:12,460
joten katsotaanpa yksinkertaisesti pitävät 23 on alku ja loppu meidän lajiteltu osan.

18
00:01:12,460 --> 00:01:16,510
Nyt meidän lajiteltu osa on yksi numero, 23,

19
00:01:16,510 --> 00:01:20,260
ja meidän lajittelemattoman osa on nämä viisi numeroa.

20
00:01:20,260 --> 00:01:27,320
Katsotaanpa nyt laittamaan seuraavan numeron meidän lajittelemattoman osaan, 42, tulee lajitella osaan.

21
00:01:27,320 --> 00:01:35,930
>> Voit tehdä niin, meidän täytyy verrata 42 23 - ainoa osatekijä lajiteltu osassa toistaiseksi.

22
00:01:35,930 --> 00:01:41,980
Neljäkymmentäkaksi on suurempi kuin 23, joten voimme yksinkertaisesti liittää 42 loppuun

23
00:01:41,980 --> 00:01:45,420
on järjestetty osan luettelosta. Hienoa!

24
00:01:45,420 --> 00:01:51,850
Nyt meidän lajiteltu osassa on kaksi elementtiä, ja meidän lajittelemattoman osassa on neljä elementtiä.

25
00:01:51,850 --> 00:01:57,200
Joten, nyt on nyt siirtyä 4, seuraava osa lajittelemattoman osaan.

26
00:01:57,200 --> 00:02:00,230
Joten, jos tämä olisi sijoitettava lajiteltu osaan?

27
00:02:00,230 --> 00:02:04,220
>> Muista, me haluamme asettaa tämän numeron lajiteltu järjestyksessä

28
00:02:04,220 --> 00:02:08,680
joten meidän lajiteltu osa pysyy oikein lajitellaan aina.

29
00:02:08,680 --> 00:02:14,380
Jos asetamme 4 oikealla 42, niin lista tulee epäkunnossa.

30
00:02:14,380 --> 00:02:18,380
Joten, jatkakaamme liikkuu oikealta vasemmalle meidän lajitella osaan.

31
00:02:18,380 --> 00:02:23,260
Kun siirrymme, katsotaanpa siirtää kunkin numeron alas paikka tehdä tilaa uuden numeron.

32
00:02:25,440 --> 00:02:31,740
Okei, 4 on myös pienempi kuin 23, joten emme voi sijoittaa sen tässäkään.

33
00:02:31,740 --> 00:02:34,480
Siirrytään 23 oikea paikka.

34
00:02:36,500 --> 00:02:43,120
>> Tämä tarkoittaa haluaisimme sijoittaa 4 ensimmäiseen aukkoon lajiteltu osaan.

35
00:02:43,120 --> 00:02:46,300
Huomaa, miten tämä tila luettelossa oli jo tyhjä,

36
00:02:46,300 --> 00:02:51,120
koska olemme siirtymässä lajiteltu elementtejä alas olemme kohdanneet heidät.

37
00:02:51,120 --> 00:02:52,740
Selvä. Joten olemme puolimatkassa.

38
00:02:52,740 --> 00:02:57,990
Jatketaan meidän algoritmi lisäämällä 16 osaksi lajiteltu osaan.

39
00:02:59,260 --> 00:03:03,820
Kuusitoista on alle 42, joten katsotaanpa siirtää 42 oikealle.

40
00:03:05,700 --> 00:03:10,190
Kuusitoista on myös pienempi kuin 23, joten katsotaanpa myös siirtää kyseistä tekijää.

41
00:03:11,790 --> 00:03:20,820
>> Nyt, 16 on suurempi kuin 4. Joten näyttää siltä, ​​haluaisimme lisätä 16 välillä 4 ja 23.

42
00:03:20,820 --> 00:03:24,620
Liikkuessaan lajiteltu osan luettelon oikealta vasemmalle,

43
00:03:24,620 --> 00:03:29,160
4 on ensimmäinen numero olemme nähneet, joka on pienempi kuin määrä,

44
00:03:29,160 --> 00:03:31,540
yritämme lisätä.

45
00:03:31,540 --> 00:03:35,820
Joten, nyt voimme lisätä 16 tähän tyhjään paikkaan

46
00:03:35,820 --> 00:03:40,520
joka, muistakaa, olemme luonut liikkuvia osia lajitella osan yli

47
00:03:40,520 --> 00:03:43,340
kuten olemme kohdanneet heidät.

48
00:03:43,340 --> 00:03:47,900
>> Selvä. Nyt meillä on neljä lajiteltu elementtejä ja kaksi lajittelemattoman elementtejä.

49
00:03:47,900 --> 00:03:51,600
Joten, lähdetään 8 osaksi lajiteltu osaan.

50
00:03:51,600 --> 00:03:55,010
Kahdeksan on alle 42.

51
00:03:55,010 --> 00:03:56,940
Kahdeksan on vähemmän kuin 23.

52
00:03:56,940 --> 00:04:00,230
Ja 8 on alle 16.

53
00:04:00,230 --> 00:04:03,110
Mutta 8 on suurempi kuin 4.

54
00:04:03,110 --> 00:04:07,280
Joten haluaisimme lisätä 8 välillä 4 ja 16.

55
00:04:09,070 --> 00:04:13,650
Ja nyt meillä on vain yksi elementti jäljellä lajitella - 15.

56
00:04:13,950 --> 00:04:16,589
Viisitoista on vähemmän kuin 42,

57
00:04:16,589 --> 00:04:19,130
Viisitoista on vähemmän kuin 23.

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

59
00:04:21,750 --> 00:04:24,810
Mutta 15 on suurempi kuin 8.

60
00:04:24,810 --> 00:04:27,440
>> Niin, tässä on, jos haluamme tehdä meidän lopullinen paikoilleen.

61
00:04:28,770 --> 00:04:30,330
Ja olemme tehneet.

62
00:04:30,330 --> 00:04:33,540
Meillä ei ole enempää elementtejä lajittelemattoman osaan,

63
00:04:33,540 --> 00:04:36,670
ja meidän lajitellaan osa on oikeassa järjestyksessä.

64
00:04:36,670 --> 00:04:40,270
Numerot ovat järjesteltyinä pienimmästä suurimpaan.

65
00:04:40,270 --> 00:04:44,330
Joten sallikaa katsomaan joitakin pseudokoodi joka kuvaa vaiheita me juuri suoritettu.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, voimme nähdä, että meidän täytyy toistaa kullakin elementti luettelossa

67
00:04:51,740 --> 00:04:57,060
paitsi ensimmäinen, koska ensimmäinen elementti lajittelemattoman osaan tulee yksinkertaisesti

68
00:04:57,060 --> 00:05:00,220
ensimmäinen elementti on lajiteltu osaan.

69
00:05:00,220 --> 00:05:06,320
Riveillä 2 ja 3, olemme tarkkailemalla nykyiseen paikka lajittelemattoman osaan.

70
00:05:06,320 --> 00:05:10,450
Elementti edustaa numero parhaillaan siirtymässä lajiteltu osaan,

71
00:05:10,450 --> 00:05:15,600
ja j edustaa indeksinä lajittelemattoman osaan.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, olemme iteroimalla läpi lajiteltu osan oikealta vasemmalle.

73
00:05:20,980 --> 00:05:26,010
Haluamme pysäyttää iteroimalla kerran elementin vasemmalle nykyiseen aseman

74
00:05:26,010 --> 00:05:30,050
on pienempi kuin elementin yritämme lisätä.

75
00:05:30,050 --> 00:05:35,600
Riviltä 5, olemme siirtymässä jokainen elementti kohtaamme yhden askeleen oikealle.

76
00:05:35,600 --> 00:05:40,950
Näin meillä on selkeä tila, joka lisätään, kun löydämme ensimmäinen osa

77
00:05:40,950 --> 00:05:44,080
vähemmän kuin elementti liikumme.

78
00:05:44,080 --> 00:05:50,800
Rivillä 6, me päivitämme vastoin edelleen siirtyä vasemmalle läpi lajiteltu osan.

79
00:05:50,800 --> 00:05:56,860
Lopuksi, rivillä 7, me työntämällä elementin lajiteltu osan luettelosta.

80
00:05:56,860 --> 00:06:00,020
>> Tiedämme, että se on okei lisätä asentoon j,

81
00:06:00,020 --> 00:06:05,360
koska olemme jo siirtyneet elementti, joka aiemmin olemassa yksi tilaa oikealle.

82
00:06:05,360 --> 00:06:09,460
Muista, liikumme läpi lajiteltu osan oikealta vasemmalle,

83
00:06:09,460 --> 00:06:13,960
mutta olemme siirtymässä läpi lajittelemattoman osan vasemmalta oikealle.

84
00:06:13,960 --> 00:06:19,090
Selvä. Katsotaanpa nyt katsomaan kuinka kauan käynnissä, että algoritmi kesti.

85
00:06:19,090 --> 00:06:25,300
Meillä tulee ensin kysyä, kuinka kauan kestää tämä algoritmi ajaa pahimmassa tapauksessa.

86
00:06:25,300 --> 00:06:29,040
Muistutan, että me edustamme tällä käyntiaika Big O notaatio.

87
00:06:32,530 --> 00:06:38,500
Jotta lajitella listalta, jouduimme iteroida yli elementtejä lajittelemattoman osaan,

88
00:06:38,500 --> 00:06:43,430
ja jokainen näistä seikoista, mahdollisesti kaikkien elementtien lajiteltu osaan.

89
00:06:43,430 --> 00:06:47,950
Intuitiivisesti tämä kuulostaa O (n ^ 2) toiminta.

90
00:06:47,950 --> 00:06:51,840
>> Tarkasteltaessa meidän pseudokoodilla, meillä on silmukka sisäkkäin toisen silmukan,

91
00:06:51,840 --> 00:06:55,290
joka todellakin kuulostaa O (n ^ 2) toimintaa.

92
00:06:55,290 --> 00:07:01,590
Kuitenkin lajiteltu osa listasta ei sisältänyt koko listan loppuun asti.

93
00:07:01,590 --> 00:07:06,920
Silti voisimme mahdollisesti lisätään uusi elementti alusta lajiteltu osan

94
00:07:06,920 --> 00:07:09,320
joka iterointia algoritmi,

95
00:07:09,320 --> 00:07:14,500
mikä tarkoittaa, että meidän täytyisi katsoa jokaisen elementin hetkellä lajiteltu osaan.

96
00:07:14,500 --> 00:07:20,090
Niin, se tarkoittaa, että voisimme mahdollisesti tehdä yksi vertailu toinen elementti,

97
00:07:20,090 --> 00:07:24,660
kaksi vertailua varten kolmas elementti, ja niin edelleen.

98
00:07:24,660 --> 00:07:32,480
Niin, että vaiheiden kokonaismäärä on summa kokonaisluvut 1 listan pituus miinus 1.

99
00:07:32,480 --> 00:07:35,240
Voimme edustaa tämän kanssa summattu.

100
00:07:41,170 --> 00:07:47,270
>> Emme aio mennä summaussarjojen täällä, mutta näyttää siltä, ​​että tämä summattu vastaa

101
00:07:47,270 --> 00:07:57,900
n (n - 1) yli 2, joka vastaa n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Kun puhutaan asymptoottinen runtime,

103
00:08:00,800 --> 00:08:05,170
tämä n ^ 2 termi tulee hallitsemaan tätä n. aikavälillä.

104
00:08:05,170 --> 00:08:11,430
Niin, lisäys sort on Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Mitä jos me juoksi lisäys lajitella jo lajiteltu luettelo.

106
00:08:16,150 --> 00:08:20,960
Tässä tapauksessa, olimme yksinkertaisesti rakentaa lajiteltu osan vasemmalta oikealle.

107
00:08:20,960 --> 00:08:25,050
Joten me vain tarvitsemme määräyksestä n askelta.

108
00:08:25,050 --> 00:08:29,740
>> Tämä tarkoittaa, että lisäys tavallaan on parhaassa tapauksessa suorituskyvyn n,

109
00:08:29,740 --> 00:08:34,130
jota edustavat kanssa Ω (n).

110
00:08:34,130 --> 00:08:36,190
Ja se on siinä asetettavaksi lajitella,

111
00:08:36,190 --> 00:08:40,429
vain yksi monista algoritmien voimme käyttää lajittelemaan lista.

112
00:08:40,429 --> 00:08:43,210
Nimeni on Tommy, ja tämä on CS50.

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

114
00:08:46,110 --> 00:08:49,230
Voi, et vain voi lopettaa, että kun se alkaa.

115
00:09:01,620 --> 00:09:04,760
Voi, teimme että - >> Boom!