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

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

3
00:00:04,522 --> 00:00:06,730
Doug LLOYD: U redu, tako da
Bubble sort je algoritam

4
00:00:06,730 --> 00:00:08,730
možete koristiti za sortiranje skup elemenata.

5
00:00:08,730 --> 00:00:10,850
Idemo pogledati kako se to radi.

6
00:00:10,850 --> 00:00:13,240
>> Dakle, osnovna ideja
Bubble sort je to.

7
00:00:13,240 --> 00:00:17,340
Mi obično žele da se presele veći
cijenjeni elementi općenito desno,

8
00:00:17,340 --> 00:00:20,340
i niže vrijednosti elemenata općenito
lijevo, kao što smo očekivali.

9
00:00:20,340 --> 00:00:23,256
Želimo niže stvari da se na
početak i viši stvari

10
00:00:23,256 --> 00:00:24,970
biti na kraju.

11
00:00:24,970 --> 00:00:26,130
>> Kako ćemo to učiniti?

12
00:00:26,130 --> 00:00:28,040
Pa u pseudokod koda,
mogli bismo reći, neka je

13
00:00:28,040 --> 00:00:30,320
set swap suprotno od ne nula vrijednosti.

14
00:00:30,320 --> 00:00:32,570
Vidjet ćemo zašto smo to učiniti u sekundi.

15
00:00:32,570 --> 00:00:36,090
A onda smo ponoviti sljedeće
Proces dok je swap brojač je 0,

16
00:00:36,090 --> 00:00:39,910
ili dok ne pravimo swap na sve.

17
00:00:39,910 --> 00:00:43,170
>> Reset swap suprotno
0, ako već nije 0.

18
00:00:43,170 --> 00:00:46,420
Onda pogledajte sve
susjedni par elemenata.

19
00:00:46,420 --> 00:00:49,550
Ako ta dva elementa
nije u redu, zamijenite ih,

20
00:00:49,550 --> 00:00:51,620
i dodati 1 do swap pulta.

21
00:00:51,620 --> 00:00:53,870
Ako razmišljate o
to prije nego što ga vizualizirati,

22
00:00:53,870 --> 00:00:57,471
primijetiti da će ovaj potez niže
cijenjena elementi lijevo

23
00:00:57,471 --> 00:01:00,720
i više cijenjena elementi desno,
učinkovito raditi ono što želimo učiniti,

24
00:01:00,720 --> 00:01:03,940
koji je premjestiti ove skupine
elemenata na taj način.

25
00:01:03,940 --> 00:01:07,035
Idemo zamišljati kako je to
može izgledati pomoću naše ponude

26
00:01:07,035 --> 00:01:10,504
koje smo koristili za testiranje
iz tih algoritama.

27
00:01:10,504 --> 00:01:13,420
Imamo nesortiranog niz opet ovdje,
naznačeno sve elemente

28
00:01:13,420 --> 00:01:14,840
da su u crvenom.

29
00:01:14,840 --> 00:01:17,970
I ja postaviti moj razmjeni brojača
na različit od nule vrijednosti.

30
00:01:17,970 --> 00:01:20,610
Ja samovoljno izabrao
negativna 1-- nije 0.

31
00:01:20,610 --> 00:01:23,840
Želimo ponoviti ovaj postupak
dok swap pulta 0.

32
00:01:23,840 --> 00:01:26,540
To je razlog zašto sam postaviti moj swapa
Brojač za neke ne nula vrijednosti,

33
00:01:26,540 --> 00:01:29,400
jer u protivnom
zamjena brojač će biti 0.

34
00:01:29,400 --> 00:01:31,610
Mi ne bi ni započinjem
Postupak algoritma.

35
00:01:31,610 --> 00:01:33,610
Pa opet, koraci are--
resetirati swap brojač

36
00:01:33,610 --> 00:01:37,900
0, a zatim pogledajte na svaki susjedni
par, a ako su iz reda,

37
00:01:37,900 --> 00:01:40,514
mijenjati ih i dodajte 1
na swapu pulta.

38
00:01:40,514 --> 00:01:41,680
Tako ćemo početi taj proces.

39
00:01:41,680 --> 00:01:44,430
Dakle, prva stvar mi je
smo postavili swap brojača na 0,

40
00:01:44,430 --> 00:01:46,660
a onda ćemo početi tražiti
na svakim uzastopnim parom.

41
00:01:46,660 --> 00:01:49,140
>> Tako smo se prvi put početi gleda na 5 i 2.

42
00:01:49,140 --> 00:01:52,410
Vidimo da su oni izvan
naručiti i tako smo ih zamijeniti.

43
00:01:52,410 --> 00:01:53,830
A mi dodajemo 1 swap pulta.

44
00:01:53,830 --> 00:01:57,860
Tako sada naša zamjena brojač je 1,
i 2 i 5 su uključen.

45
00:01:57,860 --> 00:01:59,370
Sada smo opet ponoviti postupak.

46
00:01:59,370 --> 00:02:03,540
>> Mi gledamo na sljedećem susjedni par,
5 i 1-- oni su također iz reda,

47
00:02:03,540 --> 00:02:06,960
pa smo ih mijenjati i dodavati
1 na swapu pulta.

48
00:02:06,960 --> 00:02:08,900
Onda mi gledamo na 5 i 3.

49
00:02:08,900 --> 00:02:13,830
Oni su iz reda, pa smo zamijeniti
ih i dodamo 1 do swap pulta.

50
00:02:13,830 --> 00:02:15,550
Onda mi gledamo na 5 i 6.

51
00:02:15,550 --> 00:02:18,630
Oni su u redu, tako da zapravo ne
morati mijenjati išta ovaj put.

52
00:02:18,630 --> 00:02:20,250
Onda mi gledamo na 6 i 4.

53
00:02:20,250 --> 00:02:24,920
Oni su također iz reda, pa smo zamijeniti
ih i dodamo 1 do swap pulta.

54
00:02:24,920 --> 00:02:26,230
>> Sada primijetite što se dogodilo.

55
00:02:26,230 --> 00:02:29,514
Mi smo se preselili 6 sve do kraja.

56
00:02:29,514 --> 00:02:32,180
Tako je u izbor vrste, ako ste
vidjela taj video, ono što mi je je

57
00:02:32,180 --> 00:02:35,290
smo završili pomicanjem
Najmanji elementi u zgradi

58
00:02:35,290 --> 00:02:39,640
Sortirani niz bitno od
s lijeva na desno, najmanji na najveći.

59
00:02:39,640 --> 00:02:43,200
U slučaju bubble sort, ako smo
Sljedeći ovom algoritmu,

60
00:02:43,200 --> 00:02:46,720
zapravo si idući u biti zgrada
Sortirani niz s desna

61
00:02:46,720 --> 00:02:49,100
na lijevo, najveći do najmanjih.

62
00:02:49,100 --> 00:02:53,840
Mi učinkovito u mjehurićima 6,
najveća vrijednost, sve do kraja.

63
00:02:53,840 --> 00:02:56,165
>> I tako sada možemo proglasiti
da je to riješeno,

64
00:02:56,165 --> 00:02:59,130
au budućnosti iterations--
prolazi kroz niz again--

65
00:02:59,130 --> 00:03:01,280
ne uzeti u obzir 6 više.

66
00:03:01,280 --> 00:03:03,850
Mi samo uzeti u obzir
su Nesortirani elementi

67
00:03:03,850 --> 00:03:06,299
kada gledamo susjednih parova.

68
00:03:06,299 --> 00:03:08,340
Tako smo završili jedan
prolaze kroz mjehur vrste.

69
00:03:08,340 --> 00:03:11,941
Dakle, sada se vratimo na pitanje,
ponovite sve dok je swap brojač je 0.

70
00:03:11,941 --> 00:03:13,690
Pa swap brojač
4, pa idemo

71
00:03:13,690 --> 00:03:15,410
držati taj proces ponavlja opet.

72
00:03:15,410 --> 00:03:19,180
>> Ćemo resetirati swap brojač
0, a pogledajte svaki susjedni par.

73
00:03:19,180 --> 00:03:21,890
Tako smo započeli s 2 i 1-- oni
iz reda, pa smo ih mijenjati

74
00:03:21,890 --> 00:03:23,620
a mi dodajemo 1 swap pulta.

75
00:03:23,620 --> 00:03:25,490
2 i 3, oni su u redu.

76
00:03:25,490 --> 00:03:27,060
Ne morate ništa učiniti.

77
00:03:27,060 --> 00:03:28,420
3 i 5 su u redu.

78
00:03:28,420 --> 00:03:30,150
Ne morate ništa učiniti tamo.

79
00:03:30,150 --> 00:03:32,515
>> 5 i 4, oni su se
reda, pa smo

80
00:03:32,515 --> 00:03:35,130
trebate ih mijenjati i dodavati
1 na swapu pulta.

81
00:03:35,130 --> 00:03:38,880
I sad smo se preselili 5,
sljedeći najveći element

82
00:03:38,880 --> 00:03:40,920
na kraju nerazvrstanog dijela.

83
00:03:40,920 --> 00:03:44,360
Dakle, sada možemo nazvati
dio sortirani dijela.

84
00:03:44,360 --> 00:03:47,180
>> Sada ste gledajući
zaslon i vjerojatno se može reći,

85
00:03:47,180 --> 00:03:50,130
kao što to može sam, da je niz
sortira sada.

86
00:03:50,130 --> 00:03:51,820
No, ne možemo dokazati da još.

87
00:03:51,820 --> 00:03:54,359
Nemamo jamstvo
da je to riješeno.

88
00:03:54,359 --> 00:03:56,900
No, to je mjesto gdje je swap
brojač će doći u igru.

89
00:03:56,900 --> 00:03:59,060
>> Tako smo završili sredinu.

90
00:03:59,060 --> 00:04:00,357
Swap brojač je 2.

91
00:04:00,357 --> 00:04:02,190
Tako ćemo ponoviti
taj proces opet,

92
00:04:02,190 --> 00:04:04,290
ponovite sve dok je swap brojač je 0.

93
00:04:04,290 --> 00:04:05,550
Reset swap brojača na 0.

94
00:04:05,550 --> 00:04:06,820
Tako ćemo ga resetirati.

95
00:04:06,820 --> 00:04:09,810
>> Sada pogledajte svaki susjedni par.

96
00:04:09,810 --> 00:04:11,880
To je u redu, 1 i 2.

97
00:04:11,880 --> 00:04:13,590
2 i 3 su u redu.

98
00:04:13,590 --> 00:04:15,010
3 i 4 u redu.

99
00:04:15,010 --> 00:04:19,250
Dakle, u ovom trenutku, primijetit smo završili
gledajući svaki susjedni par,

100
00:04:19,250 --> 00:04:22,530
ali swap brojač je još uvijek 0.

101
00:04:22,530 --> 00:04:25,520
>> Ako nemamo prebaciti
sve elemente, onda su

102
00:04:25,520 --> 00:04:28,340
mora biti u redu, tako
Vrlina ovog procesa.

103
00:04:28,340 --> 00:04:32,000
I tako Učinkovitost vrsta,
da smo računalni znanstvenici ljubav,

104
00:04:32,000 --> 00:04:35,560
se sada možemo proglasiti
cijeli niz mora

105
00:04:35,560 --> 00:04:38,160
biti razvrstani, jer nismo
moraju mijenjati sve elemente.

106
00:04:38,160 --> 00:04:40,380
To je prilično lijepo.

107
00:04:40,380 --> 00:04:43,260
>> Dakle, što je najgori slučaj
Scenarij s mjehur vrste?

108
00:04:43,260 --> 00:04:46,240
U najgorem slučaju, niz je
u potpunosti obrnutom redoslijedu,

109
00:04:46,240 --> 00:04:49,870
pa moramo mjehurića svaki
velikih elemenata svih

110
00:04:49,870 --> 00:04:51,780
put preko polja.

111
00:04:51,780 --> 00:04:55,350
I mi učinkovito također morati
mjehurić sve od malih elemenata natrag

112
00:04:55,350 --> 00:04:57,050
sve preko polja, previše.

113
00:04:57,050 --> 00:05:01,950
Tako svaki od n elemenata mora premjestiti
u svim drugim elementima n.

114
00:05:01,950 --> 00:05:04,102
Dakle, to je najgori mogući scenarij.

115
00:05:04,102 --> 00:05:05,810
U najboljem slučaju
scenarij ipak, ovo je

116
00:05:05,810 --> 00:05:07,880
malo drugačiji od odabira vrste.

117
00:05:07,880 --> 00:05:10,040
Niz je već
razvrstani kad idemo u.

118
00:05:10,040 --> 00:05:12,550
Nemamo da bi bilo
swaps na prvom prolazu.

119
00:05:12,550 --> 00:05:14,940
Tako bismo mogli imati da izgleda
na manje elemente, zar ne?

120
00:05:14,940 --> 00:05:18,580
Mi ne moramo ponoviti
obraditi nekoliko puta.

121
00:05:18,580 --> 00:05:19,540
>> Dakle, što to znači?

122
00:05:19,540 --> 00:05:22,390
Dakle, što je najgori mogući scenarij
za mjehur vrsta, a što je

123
00:05:22,390 --> 00:05:25,330
najbolji scenarij za mjehur vrste?

124
00:05:25,330 --> 00:05:27,770
Jeste li pogoditi ovo?

125
00:05:27,770 --> 00:05:32,420
U najgorem slučaju, morate ponoviti
preko svih n elemenata n puta.

126
00:05:32,420 --> 00:05:34,220
Tako je najgori slučaj n na kvadrat.

127
00:05:34,220 --> 00:05:36,550
>> Ako je niz savršeno
sortirati ipak, samo ti

128
00:05:36,550 --> 00:05:38,580
morati pogledati svaki
nekad elemenata.

129
00:05:38,580 --> 00:05:42,670
A ako je swap brojač je još uvijek 0,
možete reći ovo polje je riješeno.

130
00:05:42,670 --> 00:05:45,780
I tako je u najboljem slučaju, ovo je
zapravo bolji od selekcije

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

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

133
00:05:50,270 --> 00:05:52,140
Ovo je CS50.

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