1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [BUBBLE SORT]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Univerzi Harvard]

3
00:00:04,560 --> 00:00:07,500
[To je CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble Sortiraj je primer algoritma za razvrščanje -

5
00:00:11,730 --> 00:00:14,460
da je postopek za razvrščanje niz elementov v

6
00:00:14,460 --> 00:00:15,840
naraščajočem ali padajočem vrstnem redu.

7
00:00:15,840 --> 00:00:18,710
Na primer, če si hotel, da razvrstite niz, sestavljen iz številk

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], bi pravilno izvajanje Razvrsti Bubble vrne

9
00:00:23,060 --> 00:00:26,260
razporejene array [2, 3, 5, 9], v naraščajočem vrstnem redu.

10
00:00:26,260 --> 00:00:28,850
Zdaj bom razložiti, psevdokod, kako algoritem deluje.

11
00:00:28,850 --> 00:00:34,000
>> Recimo, da smo sortiranje seznam celih 5 - 3, 2, 9, 6, 5.

12
00:00:34,000 --> 00:00:37,650
Algoritem začne z opazovanjem prvih dveh elementov, 3 in 2,

13
00:00:37,650 --> 00:00:40,850
in preverjanja, če si v okvari relativno druga na drugo.

14
00:00:40,850 --> 00:00:43,150
So - 3 je večja od 2.

15
00:00:43,150 --> 00:00:45,190
Če želite biti v naraščajočem vrstnem redu, bi morali biti ravno obratno.

16
00:00:45,190 --> 00:00:46,610
Torej, jih zamenjajte.

17
00:00:46,610 --> 00:00:49,760
Zdaj je seznam izgleda takole: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Nato smo si na drugi in tretji element, 3 in 9.

19
00:00:52,450 --> 00:00:55,770
Oni so v pravilnem vrstnem redu glede na drug drugega.

20
00:00:55,770 --> 00:00:58,800
To pomeni, da je manj kot 3 9, tako da algoritem ne swap njih.

21
00:00:58,800 --> 00:01:01,900
Nato si bomo ogledali 9 in 6. Oni so v okvari.

22
00:01:01,900 --> 00:01:04,260
>> Torej, jih moramo zamenjati, ker je 9 več kot 6 let.

23
00:01:04,260 --> 00:01:08,840
Na koncu pogledamo zadnjih dveh števil, 9 in 5.

24
00:01:08,840 --> 00:01:10,850
Oni so v drugačnem vrstnem redu, tako da jih je treba zamenjati.

25
00:01:10,850 --> 00:01:13,360
Po prvem prehodu skozi celoten seznam,

26
00:01:13,360 --> 00:01:17,140
izgleda takole: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Ni slabo. Skoraj je urejeno.

28
00:01:19,690 --> 00:01:22,450
Vendar moramo teči po seznamu še enkrat, da se popolnoma urejeno.

29
00:01:22,450 --> 00:01:29,250
Dva manjša od 3, zato jih ne bomo zamenjali.

30
00:01:29,250 --> 00:01:31,700
>> Tri manj kot 6, zato jih ne bomo zamenjali.

31
00:01:31,700 --> 00:01:35,500
Šest je večja od 5 mm. Smo zamenjali.

32
00:01:35,500 --> 00:01:38,460
Šest manj kot 9. Ne zamenjati.

33
00:01:38,460 --> 00:01:42,170
Po drugem prehodu skozi, izgleda takole: [2, 3, 5, 6, 9]. Popolno.

34
00:01:42,170 --> 00:01:44,680
Zdaj pa napišite ga v Psevdokoda.

35
00:01:44,680 --> 00:01:48,450
V bistvu, za vsak element na seznamu, moramo pogledati

36
00:01:48,450 --> 00:01:50,060
in element neposredno na svoje pravice.

37
00:01:50,060 --> 00:01:53,420
Če so v drugačnem vrstnem redu glede na drug drugega - to je, če je element na levi strani

38
00:01:53,420 --> 00:01:56,810
večji od tistega na desni - bi morali zamenjati oba elementa.

39
00:01:56,810 --> 00:02:01,270
>> To počnemo za vsak element seznama, in smo naredili eno dovolilnico skozi.

40
00:02:01,270 --> 00:02:05,160
Zdaj moramo le še narediti pri prehodu skozi dovolj časa, da se zagotovi seznam

41
00:02:05,160 --> 00:02:06,480
se v celoti pravilno razvrščeni.

42
00:02:06,480 --> 00:02:08,889
Ampak kolikokrat moramo skozi seznamu

43
00:02:08,889 --> 00:02:10,400
zagotoviti, da bomo končali?

44
00:02:10,400 --> 00:02:14,730
No, najslabši scenarij, če imamo popolnoma nazaj seznam.

45
00:02:14,730 --> 00:02:17,840
Potem pa je potrebno veliko prehodu za kanale enako številu

46
00:02:17,840 --> 00:02:19,730
elementov n-1.

47
00:02:19,730 --> 00:02:24,720
Če to ni smiselno, intuitivno, pomislite na preprostem primeru - seznam [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> To bo trajalo 1 pass-through za pravilno razvrstiti.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - V najslabšem primeru je, da s 3 elementi, razvrščeni nazaj,

50
00:02:33,060 --> 00:02:34,830
to bo trajalo 2 do ponovitve takega.

51
00:02:34,830 --> 00:02:37,980
Po eni iteraciji, je [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Drugi dobimo razporejene array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Torej veste, da vam nikoli ne bo šel skozi niz, na splošno,

54
00:02:43,350 --> 00:02:46,790
več kot n-1-krat, pri čemer je n število elementov v matriki.

55
00:02:47,090 --> 00:02:50,470
To se imenuje Bubble Razvrsti ker je največji elementi ponavadi "bubble-up"

56
00:02:50,470 --> 00:02:51,950
na desni precej hitro.

57
00:02:51,950 --> 00:02:53,980
V bistvu je to algoritem ima zelo zanimivo obnašanje.

58
00:02:53,980 --> 00:02:57,410
>> Po m ponovitev prek celotnega niza,

59
00:02:57,410 --> 00:02:59,000
skrajnem desnem m elementi so zagotovljena

60
00:02:59,000 --> 00:03:01,000
da se združimo v svojem pravem mestu.

61
00:03:01,000 --> 00:03:02,280
Če želite prepričati o tem,

62
00:03:02,280 --> 00:03:05,500
lahko poskusite na povsem zavoljo seznama [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Po enem prehodu skozi celoten seznam,

64
00:03:08,220 --> 00:03:09,220
[Zvok pisno]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
na skrajni desni element 9 je na ustreznem mestu.

67
00:03:21,250 --> 00:03:24,760
Po drugi pass-through bo 6 imajo "mehurčki-up" za

68
00:03:24,760 --> 00:03:26,220
2. skrajno desno mesto.

69
00:03:26,220 --> 00:03:28,840
Dva elementa na desni - 6 in 9 - bo v svojih pravih mestih

70
00:03:28,840 --> 00:03:30,580
po prvih dveh pass-kanale.

71
00:03:30,580 --> 00:03:32,590
>> Torej, kako lahko to uporabimo za optimizacijo algoritma?

72
00:03:32,590 --> 00:03:34,850
No, po eni iteraciji skozi niz

73
00:03:34,850 --> 00:03:37,690
pravzaprav ne potrebujejo, da preverite desna element

74
00:03:37,690 --> 00:03:39,200
saj vemo, da je razvrščena.

75
00:03:39,200 --> 00:03:43,050
Po dveh ponovitvah, smo prepričani, skrajno desno dva elementa sta na mestu.

76
00:03:43,050 --> 00:03:48,260
Torej, na splošno, potem kv iteracij prek celotnega niza,

77
00:03:48,260 --> 00:03:51,550
preverjanje zadnjih K elementov je odveč, saj vemo,

78
00:03:51,550 --> 00:03:52,360
oni so na pravem mestu že.

79
00:03:52,360 --> 00:03:54,870
>> Torej, če ste sortiranje niz elementov n,

80
00:03:54,870 --> 00:03:57,870
na prvi ponovitvi - boš moral rešiti vse elemente - prvi n-0.

81
00:03:57,870 --> 00:04:04,170
Po drugi ponovitvi, boste morali gledati na vse elemente razen zadnjega -

82
00:04:04,170 --> 00:04:07,090
1. n-1.

83
00:04:07,090 --> 00:04:10,520
Druga optimizacijo lahko preverite, ali je seznam že razporejene

84
00:04:10,520 --> 00:04:11,710
po vsaki ponovitvi.

85
00:04:11,710 --> 00:04:13,900
Če je že urejen, ne rabimo narediti nič več ponovitev

86
00:04:13,900 --> 00:04:15,310
po seznamu.

87
00:04:15,310 --> 00:04:16,220
Kako lahko to storimo?

88
00:04:16,220 --> 00:04:19,360
No, če ne bo nobenih zamenjav na pass-through seznama,

89
00:04:19,360 --> 00:04:22,350
je jasno, da je bil seznam že razporejene, ker nismo zamenjali ničesar.

90
00:04:22,350 --> 00:04:24,160
Zato smo zagotovo ne bi bilo treba ponovno razvrstiti.

91
00:04:24,160 --> 00:04:27,960
>> Morda bi lahko inicializacija zastave spremenljivko, imenovano "ni urejen" v

92
00:04:27,960 --> 00:04:30,990
neresnično in jo spremenite res, če imate, da bi zamenjali vse elemente

93
00:04:30,990 --> 00:04:32,290
ena ponovitev z matriko.

94
00:04:32,290 --> 00:04:35,350
Ali prav, da števec prešteti, koliko zamenjav naredite

95
00:04:35,350 --> 00:04:37,040
na katerem koli ponovitev.

96
00:04:37,040 --> 00:04:40,040
Na koncu je ponovitev, če ne bi zamenjal katerega koli od elementov,

97
00:04:40,040 --> 00:04:41,780
Veš seznam že razporejene in ste končali.

98
00:04:41,780 --> 00:04:44,090
Bubble Sortiraj, tako kot drugi algoritmi razvrščanja, je lahko

99
00:04:44,090 --> 00:04:46,960
tweaked za delo vseh elementov, ki imajo naročanje metodo.

100
00:04:46,960 --> 00:04:50,610
>> To je, glede na dva elementa, morate način, kako povedati, če prva

101
00:04:50,610 --> 00:04:53,770
, večji je enaka ali manjša od drugega.

102
00:04:53,770 --> 00:04:56,870
Na primer, lahko razvrstimo črke abecede z besedami

103
00:04:56,870 --> 00:05:00,520
da <b, b <c, itd

104
00:05:00,520 --> 00:05:03,830
Ali pa bi lahko razvrščate dni v tednu nedelja, kjer je manj kot ponedeljek

105
00:05:03,830 --> 00:05:05,110
kar je manj kot v torek.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Razvrsti nikakor ni zelo učinkovito in hitro sortiranje algoritem.

107
00:05:09,630 --> 00:05:12,370
Njegov najslabši teka je Big O n ²

108
00:05:12,370 --> 00:05:14,810
ker moraš narediti n ponovitev po seznamu

109
00:05:14,810 --> 00:05:18,430
preverjanje vseh elementov, vsak n pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
To pomeni, da čas teče, saj je število elementov, da ste sortiranje povečuje,

111
00:05:22,730 --> 00:05:24,330
čas delovanja povečuje kvadratom.

112
00:05:24,330 --> 00:05:27,330
>> Ampak, če učinkovitost ni glavna skrb vašega programa

113
00:05:27,330 --> 00:05:29,550
ali če ste le sortiranje majhno število elementov,

114
00:05:29,550 --> 00:05:31,660
boste morda našli Bubble Razvrsti koristno, saj

115
00:05:31,660 --> 00:05:33,360
to je eden od najpreprostejših algoritmov za razumevanje

116
00:05:33,360 --> 00:05:34,250
in za kodiranje.

117
00:05:34,250 --> 00:05:37,270
To je tudi odličen način, da izkušnje s prevajanjem teoretično

118
00:05:37,270 --> 00:05:40,220
Algoritem v dejansko oznako delovanja.

119
00:05:40,220 --> 00:05:43,000
No, to je Bubble Sortiraj za vas. Hvala za ogled.

120
00:05:43,000 --> 00:05:44,000
CS50.TV