1
00:00:00,000 --> 00:00:03,360
>> [Musiikkia]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG Lloyd: Selvä, joten
kuplalajittelu on algoritmi

4
00:00:06,730 --> 00:00:08,730
voit lajitella joukko elementtejä.

5
00:00:08,730 --> 00:00:10,850
Katsotaanpa katsomaan miten se toimii.

6
00:00:10,850 --> 00:00:13,240
>> Joten perusajatuksena
kuplalajittelu on tämä.

7
00:00:13,240 --> 00:00:17,340
Me yleensä haluavat siirtyä korkeammalle
arvosti yleensä oikealle,

8
00:00:17,340 --> 00:00:20,340
ja laske arvosti yleisesti
vasemmalle, kun odotamme.

9
00:00:20,340 --> 00:00:23,256
Haluamme alempi asiat olevan
alussa, ja korkeampi asiat

10
00:00:23,256 --> 00:00:24,970
olla lopussa.

11
00:00:24,970 --> 00:00:26,130
>> Miten teemme tämän?

12
00:00:26,130 --> 00:00:28,040
Hyvin pseudokoodilla koodi,
voisimme sanoa, katsotaanpa

13
00:00:28,040 --> 00:00:30,320
asettaa swap laskuri muu kuin nolla.

14
00:00:30,320 --> 00:00:32,570
Näemme miksi me teemme, että toinen.

15
00:00:32,570 --> 00:00:36,090
Ja sitten toistamme seuraavat
kunnes swap laskuri on 0,

16
00:00:36,090 --> 00:00:39,910
tai kunnes teemme mitään swap lainkaan.

17
00:00:39,910 --> 00:00:43,170
>> Nollaa swap laskuri
0 jos se ei ole jo 0.

18
00:00:43,170 --> 00:00:46,420
Sitten katsoa joka
vierekkäisen parin elementtejä.

19
00:00:46,420 --> 00:00:49,550
Jos nämä kaksi tekijää ovat
ei kunnossa, vaihtaa niitä,

20
00:00:49,550 --> 00:00:51,620
ja lisätään 1 swap laskuri.

21
00:00:51,620 --> 00:00:53,870
Jos olet ajatellut
tämä ennen kuin visualisoida sitä,

22
00:00:53,870 --> 00:00:57,471
huomaa, että tämä siirtyy alemman
arvosti vasemmalle

23
00:00:57,471 --> 00:01:00,720
ja korkeampi arvosti oikealle,
tehokkaasti tehdä mitä haluamme tehdä,

24
00:01:00,720 --> 00:01:03,940
joka on siirtää nämä ryhmät
elementtien tavoin.

25
00:01:03,940 --> 00:01:07,035
Katsotaanpa visualisoida miten tämä
voisi näyttää käyttämällä array

26
00:01:07,035 --> 00:01:10,504
että me testata
nämä algoritmit.

27
00:01:10,504 --> 00:01:13,420
Meillä lajittelematonta joukko täällä taas,
merkitty kaikki elementit

28
00:01:13,420 --> 00:01:14,840
on punaisella.

29
00:01:14,840 --> 00:01:17,970
Ja minä käänsin swap laskuri
on nollasta poikkeava arvo.

30
00:01:17,970 --> 00:01:20,610
I mielivaltaisesti Valitsin
negatiivinen 1-- se ei ole 0.

31
00:01:20,610 --> 00:01:23,840
Haluamme toistaa tämän prosessin
kunnes swap laskuri on 0.

32
00:01:23,840 --> 00:01:26,540
Siksi minä asetan swap
vastoin joitakin ei-nolla,

33
00:01:26,540 --> 00:01:29,400
koska muuten
swap laskuri olisi 0.

34
00:01:29,400 --> 00:01:31,610
Olisimme edes alkaa
prosessi algoritmin.

35
00:01:31,610 --> 00:01:33,610
Joten jälleen vaiheet are--
Nollaa swap laskuri

36
00:01:33,610 --> 00:01:37,900
0, sitten katsoa joka vieressä
pari, ja jos he epäkunnossa,

37
00:01:37,900 --> 00:01:40,514
vaihtaa niitä, ja lisää 1
swap laskuri.

38
00:01:40,514 --> 00:01:41,680
Aloitetaanpa tässä prosessissa.

39
00:01:41,680 --> 00:01:44,430
Joten ensimmäinen asia mitä teemme on
asetamme swap laskuri 0,

40
00:01:44,430 --> 00:01:46,660
ja sitten me alkaa etsiä
jokaisen vierekkäisen parin.

41
00:01:46,660 --> 00:01:49,140
>> Joten ensin alkaa katsella 5 ja 2.

42
00:01:49,140 --> 00:01:52,410
Näemme, että he ovat poissa
tilata ja niin me vaihtaa niitä.

43
00:01:52,410 --> 00:01:53,830
Ja lisäämme 1 swap laskuri.

44
00:01:53,830 --> 00:01:57,860
Joten nyt meidän swap laskuri on 1,
ja 2 ja 5 on kytketty.

45
00:01:57,860 --> 00:01:59,370
Nyt toista prosessi uudelleen.

46
00:01:59,370 --> 00:02:03,540
>> Katsomme seuraavaksi vierekkäisten,
5 ja 1-- he ovat myös epäkunnossa,

47
00:02:03,540 --> 00:02:06,960
joten me vaihtaa niitä ja lisätä
1 swap laskuri.

48
00:02:06,960 --> 00:02:08,900
Sitten katsomme 5 ja 3.

49
00:02:08,900 --> 00:02:13,830
Ne ovat epäkunnossa, joten swap
niitä ja lisäämme 1 swap laskuri.

50
00:02:13,830 --> 00:02:15,550
Sitten katsomme 5 ja 6.

51
00:02:15,550 --> 00:02:18,630
He järjestyksessä, joten emme oikeastaan
täytyy vaihtaa mitään tällä kertaa.

52
00:02:18,630 --> 00:02:20,250
Sitten katsomme 6 ja 4.

53
00:02:20,250 --> 00:02:24,920
Ne ovat myös epäkunnossa, joten swap
niitä ja lisäämme 1 swap laskuri.

54
00:02:24,920 --> 00:02:26,230
>> Nyt huomaa, mitä on tapahtunut.

55
00:02:26,230 --> 00:02:29,514
Olemme siirtyneet 6 aina loppuun.

56
00:02:29,514 --> 00:02:32,180
Joten valinta lajitella, jos olet
nähdä, että video, mitä teimme oli

57
00:02:32,180 --> 00:02:35,290
päädyimme liikkuva
pienin elementtejä rakentamisessa

58
00:02:35,290 --> 00:02:39,640
lajitellut array olennaisesti
vasemmalta oikealle, pienimmästä suurimpaan.

59
00:02:39,640 --> 00:02:43,200
Kun kyseessä on kuplalajittelu, jos olemme
seuraa tätä tiettyyn algoritmiin,

60
00:02:43,200 --> 00:02:46,720
olemme todella aiotaan rakentaa
lajitellut array oikealta

61
00:02:46,720 --> 00:02:49,100
vasemmalle, suurimmasta pienimpään.

62
00:02:49,100 --> 00:02:53,840
Olemme tehokkaasti kuplia 6,
Suurin arvo, aina loppuun.

63
00:02:53,840 --> 00:02:56,165
>> Ja jotta voimme nyt julistaa
että lajitellaan,

64
00:02:56,165 --> 00:02:59,130
ja tulevaisuudessa iterations--
läpi array again--

65
00:02:59,130 --> 00:03:01,280
meillä ei tarvitse harkita 6 enää.

66
00:03:01,280 --> 00:03:03,850
Meillä vain on otettava huomioon
lajittelemattomat elementit

67
00:03:03,850 --> 00:03:06,299
kun etsimme viereisillä paria.

68
00:03:06,299 --> 00:03:08,340
Joten olemme lopettaneet yksi
läpi kuplalajittelu.

69
00:03:08,340 --> 00:03:11,941
Joten nyt palaamme kysymykseen,
Toista, kunnes swap laskuri on 0.

70
00:03:11,941 --> 00:03:13,690
No swap laskuri
on 4, joten olemme menossa

71
00:03:13,690 --> 00:03:15,410
pitää toistaa tämän prosessin uudelleen.

72
00:03:15,410 --> 00:03:19,180
>> Aiomme palauttaa swap laskuri
0, ja näyttää jokaisen vierekkäisen parin.

73
00:03:19,180 --> 00:03:21,890
Joten aloitamme 2 ja 1-- he
epäkunnossa, joten me vaihtaa niitä

74
00:03:21,890 --> 00:03:23,620
ja lisäämme 1 swap laskuri.

75
00:03:23,620 --> 00:03:25,490
2 ja 3, he ovat kunnossa.

76
00:03:25,490 --> 00:03:27,060
Meidän ei tarvitse tehdä mitään.

77
00:03:27,060 --> 00:03:28,420
3 ja 5 ovat kunnossa.

78
00:03:28,420 --> 00:03:30,150
Meidän ei tarvitse tehdä mitään siellä.

79
00:03:30,150 --> 00:03:32,515
>> 5 ja 4, ne ovat poissa
järjestyksen, ja niin me

80
00:03:32,515 --> 00:03:35,130
täytyy vaihtaa niitä ja lisätä
1 swap laskuri.

81
00:03:35,130 --> 00:03:38,880
Ja nyt olemme siirretty 5,
seuraavaksi suurin elementti,

82
00:03:38,880 --> 00:03:40,920
loppuun lajittelemattoman osan.

83
00:03:40,920 --> 00:03:44,360
Joten voimme nyt kutsua että
osa lajiteltu osan.

84
00:03:44,360 --> 00:03:47,180
>> Nyt etsit
näyttö ja luultavasti voi kertoa,

85
00:03:47,180 --> 00:03:50,130
kuten voin, että jono
lajitellaan juuri nyt.

86
00:03:50,130 --> 00:03:51,820
Mutta emme voi todistaa, että vielä.

87
00:03:51,820 --> 00:03:54,359
Meillä ei ole takeita
että se on lajiteltu.

88
00:03:54,359 --> 00:03:56,900
Mutta tämä on silloin swap
laskuri tulee kuvaan.

89
00:03:56,900 --> 00:03:59,060
>> Joten olemme valmiiksi omille.

90
00:03:59,060 --> 00:04:00,357
Swap laskuri on 2.

91
00:04:00,357 --> 00:04:02,190
Joten aiomme toistaa
tämä prosessi uudelleen,

92
00:04:02,190 --> 00:04:04,290
Toista, kunnes swap laskuri on 0.

93
00:04:04,290 --> 00:04:05,550
Nollaa swap laskuri 0.

94
00:04:05,550 --> 00:04:06,820
Niin me nollata.

95
00:04:06,820 --> 00:04:09,810
>> Nyt näyttää jokaisen vierekkäisen parin.

96
00:04:09,810 --> 00:04:11,880
Se on kunnossa, 1 ja 2.

97
00:04:11,880 --> 00:04:13,590
2 ja 3 ovat kunnossa.

98
00:04:13,590 --> 00:04:15,010
3 ja 4 ovat kunnossa.

99
00:04:15,010 --> 00:04:19,250
Joten tässä vaiheessa, huomaa olemme valmiiksi
katsomalla jokainen vierekkäisten,

100
00:04:19,250 --> 00:04:22,530
mutta swap laskuri on edelleen 0.

101
00:04:22,530 --> 00:04:25,520
>> Jos meillä ei ole vaihtaa
kaikki elementit, sitten he

102
00:04:25,520 --> 00:04:28,340
on oltava kunnossa, mukaan
nojalla tämän prosessin.

103
00:04:28,340 --> 00:04:32,000
Ja niin tehokkuus tapaisena,
että me tietotekniikan tutkijoita rakastamme,

104
00:04:32,000 --> 00:04:35,560
on nyt voimme julistaa
koko ryhmän täytyy

105
00:04:35,560 --> 00:04:38,160
järjestellä, koska emme
täytyy vaihtaa mitään osia.

106
00:04:38,160 --> 00:04:40,380
Se on ihan kiva.

107
00:04:40,380 --> 00:04:43,260
>> Niin mitä pahimmassa tapauksessa
skenaario kanssa kuplalajittelu?

108
00:04:43,260 --> 00:04:46,240
Pahimmassa tapauksessa matriisi on
täysin päinvastaisessa järjestyksessä,

109
00:04:46,240 --> 00:04:49,870
ja niin meidän on kupla kunkin
suurten elementtien kaikki

110
00:04:49,870 --> 00:04:51,780
tavalla koko jono.

111
00:04:51,780 --> 00:04:55,350
Ja me tehokkaasti on myös
kupla kaikki pienet elementit takaisin

112
00:04:55,350 --> 00:04:57,050
koko matkan array, liian.

113
00:04:57,050 --> 00:05:01,950
Näin ollen jokainen n alkio on siirtää
poikki kaikki muut n-elementtejä.

114
00:05:01,950 --> 00:05:04,102
Niin, että pahimmassa tapauksessa.

115
00:05:04,102 --> 00:05:05,810
Parhaassa tapauksessa
skenaario kuitenkin, tämä on

116
00:05:05,810 --> 00:05:07,880
hieman erilainen valinta lajitella.

117
00:05:07,880 --> 00:05:10,040
Array on jo
lajiteltu kun menemme sisään.

118
00:05:10,040 --> 00:05:12,550
Meillä ei tarvitse tehdä mitään
swap ensimmäisellä omille.

119
00:05:12,550 --> 00:05:14,940
Joten saatamme täytyy katsoa
klo vähemmän osia, eikö?

120
00:05:14,940 --> 00:05:18,580
Meillä ei tarvitse toistaa tätä
käsitellä useita kertoja.

121
00:05:18,580 --> 00:05:19,540
>> Mitä tämä tarkoittaa?

122
00:05:19,540 --> 00:05:22,390
Niin mitä pahimmassa tapauksessa
varten kuplalajittelu, ja mitä

123
00:05:22,390 --> 00:05:25,330
paras skenaario kuplalajittelu?

124
00:05:25,330 --> 00:05:27,770
Arvasit tämän?

125
00:05:27,770 --> 00:05:32,420
Pahimmassa tapauksessa joudut kerrata
kaikissa n elementtiä n kertaa.

126
00:05:32,420 --> 00:05:34,220
Joten pahimmassa tapauksessa on n potenssiin.

127
00:05:34,220 --> 00:05:36,550
>> Jos matriisi on täysin
lajiteltua kuitenkin, sinun vain

128
00:05:36,550 --> 00:05:38,580
täytyy katsoa jokaisen
elementtien kerran.

129
00:05:38,580 --> 00:05:42,670
Ja jos swap laskuri on edelleen 0,
voit sanoa tämän taulukon lajitellaan.

130
00:05:42,670 --> 00:05:45,780
Ja niin parhaassa tapauksessa, tämä on
itse asiassa parempi kuin valinta

131
00:05:45,780 --> 00:05:49,230
sort-- se on omega n.

132
00:05:49,230 --> 00:05:50,270
>> Olen Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Tämä on CS50.

134
00:05:52,140 --> 00:05:54,382