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

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Dobrze, więc
Sortowanie bąbelkowe jest algorytmem

4
00:00:06,730 --> 00:00:08,730
można użyć do sortowania zestaw elementów.

5
00:00:08,730 --> 00:00:10,850
Rzućmy okiem na, jak to działa.

6
00:00:10,850 --> 00:00:13,240
>> Więc Podstawową ideą
Sortowanie bąbelkowe jest to.

7
00:00:13,240 --> 00:00:17,340
Zazwyczaj chcą przenieść wyżej
wyceniane elementy ogólnie w prawo,

8
00:00:17,340 --> 00:00:20,340
i obniżyć ogólnie cenionych elementów
w lewo, jak to się spodziewać.

9
00:00:20,340 --> 00:00:23,256
Chcemy niższe rzeczy być w
początek, a wyższe rzeczy

10
00:00:23,256 --> 00:00:24,970
się na końcu.

11
00:00:24,970 --> 00:00:26,130
>> W jaki sposób to zrobić?

12
00:00:26,130 --> 00:00:28,040
Cóż w kodzie pseudokod,
moglibyśmy powiedzieć, niech

13
00:00:28,040 --> 00:00:30,320
ustawić licznik wymiany na wartość niezerową.

14
00:00:30,320 --> 00:00:32,570
Zobaczymy, dlaczego robimy to, że w drugim.

15
00:00:32,570 --> 00:00:36,090
A potem powtórzyć następujące
Proces dopóki licznik wymiany jest 0,

16
00:00:36,090 --> 00:00:39,910
lub do czasu robimy żadnych swapów w ogóle.

17
00:00:39,910 --> 00:00:43,170
>> Wyzerować licznik wymiany do
0 jeśli nie jest już 0.

18
00:00:43,170 --> 00:00:46,420
Następnie spójrz na co
parę sąsiednich elementów.

19
00:00:46,420 --> 00:00:49,550
Jeśli te dwa elementy są
nie w porządku, ich wymiany,

20
00:00:49,550 --> 00:00:51,620
i dodać 1 do licznika wymiany.

21
00:00:51,620 --> 00:00:53,870
Jeśli myślisz o
to przed wizualizację,

22
00:00:53,870 --> 00:00:57,471
zauważysz, że będzie to przenieść niższe
wyceniane elementy w lewo

23
00:00:57,471 --> 00:01:00,720
i wyżej cenione elementy do prawej,
skutecznie robić to, co chcemy zrobić,

24
00:01:00,720 --> 00:01:03,940
co jest przenieść te grupy
elementów w ten sposób.

25
00:01:03,940 --> 00:01:07,035
Powiedzmy, wizualizować, jak to
może wyglądać przy użyciu naszą tablicę

26
00:01:07,035 --> 00:01:10,504
który zastosowano do badania
z tych algorytmów.

27
00:01:10,504 --> 00:01:13,420
Znów mamy tutaj jakiś nieposortowanej tablicy,
oznaczone wszystkie elementy

28
00:01:13,420 --> 00:01:14,840
jest w kolorze czerwonym.

29
00:01:14,840 --> 00:01:17,970
I mogę ustawić licznik wymiany
na wartość niezerową.

30
00:01:17,970 --> 00:01:20,610
I arbitralnie wybrała
negatywne 1-- to nie jest 0.

31
00:01:20,610 --> 00:01:23,840
Chcemy, aby powtórzyć ten proces
do licznika wymiany to 0.

32
00:01:23,840 --> 00:01:26,540
Dlatego też ustawić swap
Licznik jakąś wartość niezerową,

33
00:01:26,540 --> 00:01:29,400
ponieważ w przeciwnym wypadku
Licznik wymiany będzie 0.

34
00:01:29,400 --> 00:01:31,610
My nawet nie rozpocząć
Proces algorytmu.

35
00:01:31,610 --> 00:01:33,610
Więc jeszcze raz, kroki are--
wyzerować licznik wymiany

36
00:01:33,610 --> 00:01:37,900
na 0, a następnie spójrz na każde sąsiadujące
para, a jeśli są w porządku,

37
00:01:37,900 --> 00:01:40,514
zamienić je i dodać 1
do licznika wymiany.

38
00:01:40,514 --> 00:01:41,680
Warto więc rozpocząć ten proces.

39
00:01:41,680 --> 00:01:44,430
Tak więc pierwszą rzeczą, jaką możemy zrobić, to
możemy ustawić licznik wymiany na 0,

40
00:01:44,430 --> 00:01:46,660
i wtedy zacząć szukać
w każdej sąsiedniej pary.

41
00:01:46,660 --> 00:01:49,140
>> Więc najpierw zacząć patrzeć na 5 i 2.

42
00:01:49,140 --> 00:01:52,410
Widzimy, że są one z
zamówienie i tak zamienić je.

43
00:01:52,410 --> 00:01:53,830
I możemy dodać 1 do licznika wymiany.

44
00:01:53,830 --> 00:01:57,860
Więc teraz nasze przeciw wymiany to 1,
oraz 2 i 5 zostały włączone.

45
00:01:57,860 --> 00:01:59,370
Teraz ponownie powtórzyć proces.

46
00:01:59,370 --> 00:02:03,540
>> Patrzymy na następnej sąsiedniej pary,
5 i 1-- są też w porządku,

47
00:02:03,540 --> 00:02:06,960
więc zamienić je i dodaj
1 do licznika wymiany.

48
00:02:06,960 --> 00:02:08,900
Następnie patrzymy na 5 i 3.

49
00:02:08,900 --> 00:02:13,830
Są w porządku, więc zamienić
je i dodać 1 do licznika wymiany.

50
00:02:13,830 --> 00:02:15,550
Następnie patrzymy na 5 i 6.

51
00:02:15,550 --> 00:02:18,630
Są w porządku, więc w rzeczywistości nie
trzeba zamieniać cokolwiek ten czas.

52
00:02:18,630 --> 00:02:20,250
Następnie patrzymy na 6 i 4.

53
00:02:20,250 --> 00:02:24,920
Są także w porządku, więc zamienić
je i dodać 1 do licznika wymiany.

54
00:02:24,920 --> 00:02:26,230
>> Teraz zauważył, co się stało.

55
00:02:26,230 --> 00:02:29,514
Mamy przeniósł 6, aż do końca.

56
00:02:29,514 --> 00:02:32,180
Więc wybór rodzaju, jeśli już
widać, że film, co zrobiliśmy było

57
00:02:32,180 --> 00:02:35,290
Skończyło się przesunięcie
Najmniejsze elementy budynku

58
00:02:35,290 --> 00:02:39,640
posortowanej tablicy zasadniczo od
od lewej do prawej strony, najmniejszych do największych.

59
00:02:39,640 --> 00:02:43,200
W przypadku sortowanie bąbelkowe, czy jesteśmy
w następstwie tego konkretnego algorytmu,

60
00:02:43,200 --> 00:02:46,720
my rzeczywiście będzie budowa
posortowanej tablicy z prawej

61
00:02:46,720 --> 00:02:49,100
do lewej, od największej do najmniejszej.

62
00:02:49,100 --> 00:02:53,840
Mamy skutecznie przepuszcza 6,
największa wartość, aż do końca.

63
00:02:53,840 --> 00:02:56,165
>> I tak możemy zadeklarować
że jest posortowana,

64
00:02:56,165 --> 00:02:59,130
aw przyszłości iterations--
przechodzi tablicy again--

65
00:02:59,130 --> 00:03:01,280
nie mamy do rozważenia 6 więcej.

66
00:03:01,280 --> 00:03:03,850
Mamy tylko do rozważenia
nieposortowanej elementy

67
00:03:03,850 --> 00:03:06,299
kiedy patrzymy na sąsiednich par.

68
00:03:06,299 --> 00:03:08,340
Więc mamy gotowy jeden
przejść przez bubble rodzaju.

69
00:03:08,340 --> 00:03:11,941
Więc teraz wracamy do pytania,
powtarzać aż licznik wymiany jest 0.

70
00:03:11,941 --> 00:03:13,690
Cóż licznik wymiany
jest 4, więc jedziemy

71
00:03:13,690 --> 00:03:15,410
utrzymać powtarzając ten proces.

72
00:03:15,410 --> 00:03:19,180
>> Jedziemy, aby wyzerować licznik wymiany
0, i spojrzeć na każdą parą sąsiednich.

73
00:03:19,180 --> 00:03:21,890
Więc zaczynamy 2 i 1-- są
w porządku, więc możemy je zamienić

74
00:03:21,890 --> 00:03:23,620
i dodać 1 do licznika wymiany.

75
00:03:23,620 --> 00:03:25,490
2 i 3, są w porządku.

76
00:03:25,490 --> 00:03:27,060
Nie musimy nic robić.

77
00:03:27,060 --> 00:03:28,420
3 i 5 są w porządku.

78
00:03:28,420 --> 00:03:30,150
Nie musimy robić coś.

79
00:03:30,150 --> 00:03:32,515
>> 5 i 4, są z
porządku, a więc

80
00:03:32,515 --> 00:03:35,130
należy zamienić je i dodaj
1 do licznika wymiany.

81
00:03:35,130 --> 00:03:38,880
A teraz mamy przeniósł 5,
następna największa elementem,

82
00:03:38,880 --> 00:03:40,920
na końcu części sortowane.

83
00:03:40,920 --> 00:03:44,360
Więc teraz możemy nazwać
część posortowane części.

84
00:03:44,360 --> 00:03:47,180
>> Teraz jesteś patrząc na
Ekran i chyba mogę powiedzieć,

85
00:03:47,180 --> 00:03:50,130
jak mogę, że na tablicy
jest posortowana teraz.

86
00:03:50,130 --> 00:03:51,820
Ale nie możemy udowodnić, że jeszcze.

87
00:03:51,820 --> 00:03:54,359
Nie mamy gwarancji
że to jest klasyfikowane.

88
00:03:54,359 --> 00:03:56,900
Ale to jest, gdy zamiana
Licznik będzie wchodzić w grę.

89
00:03:56,900 --> 00:03:59,060
>> Więc mamy zakończone przepustkę.

90
00:03:59,060 --> 00:04:00,357
Licznik wymiany to 2.

91
00:04:00,357 --> 00:04:02,190
Tak więc mamy zamiar powtórzyć
znowu ten proces,

92
00:04:02,190 --> 00:04:04,290
powtarzać aż licznik wymiany jest 0.

93
00:04:04,290 --> 00:04:05,550
Wyzerować licznik wymiany 0.

94
00:04:05,550 --> 00:04:06,820
Więc będziemy go zresetować.

95
00:04:06,820 --> 00:04:09,810
>> Teraz spójrz na każdej sąsiedniej pary.

96
00:04:09,810 --> 00:04:11,880
To jest w kolejności 1 i 2.

97
00:04:11,880 --> 00:04:13,590
2 i 3 jest w porządku.

98
00:04:13,590 --> 00:04:15,010
3 i 4 są w porządku.

99
00:04:15,010 --> 00:04:19,250
Więc w tym momencie zauważyć, mamy zakończone
patrząc na każdej sąsiedniej pary,

100
00:04:19,250 --> 00:04:22,530
ale licznik wymiany jest wciąż 0.

101
00:04:22,530 --> 00:04:25,520
>> Jeśli nie mamy, aby przełączyć
wszelkie elementy, a potem

102
00:04:25,520 --> 00:04:28,340
muszą być w stanie, poprzez
zaletą tego procesu.

103
00:04:28,340 --> 00:04:32,000
I tak sprawność rodzaju,
że naukowcy mamy komputer miłość,

104
00:04:32,000 --> 00:04:35,560
jest teraz możemy zadeklarować
cała tablica musi

105
00:04:35,560 --> 00:04:38,160
być sortowane, bo nie
trzeba zamienić wszystkie elementy.

106
00:04:38,160 --> 00:04:40,380
To całkiem miłe.

107
00:04:40,380 --> 00:04:43,260
>> Więc co jest najgorszym przypadku
Scenariusz z bańki rodzaju?

108
00:04:43,260 --> 00:04:46,240
W najgorszym przypadku, gdy matryca jest
w zupełnie odwrotnej kolejności,

109
00:04:46,240 --> 00:04:49,870
i tak musimy bańka każdego
dużych elementów wszystkich

110
00:04:49,870 --> 00:04:51,780
sposób w całej tablicy.

111
00:04:51,780 --> 00:04:55,350
I skutecznie również do
bańka wszystkich małych elementów z powrotem

112
00:04:55,350 --> 00:04:57,050
aż poprzez tablicy, też.

113
00:04:57,050 --> 00:05:01,950
Tak więc każdy z elementów n musi poruszać
we wszystkich pozostałych elementów N.

114
00:05:01,950 --> 00:05:04,102
Więc to najgorszy scenariusz.

115
00:05:04,102 --> 00:05:05,810
W najlepszym wypadku
Scenariusz jeśli jest to

116
00:05:05,810 --> 00:05:07,880
nieznacznie różnić się od wyboru rodzaju.

117
00:05:07,880 --> 00:05:10,040
Tablica jest już
klasyfikowane, gdy idziemy w.

118
00:05:10,040 --> 00:05:12,550
Nie trzeba wprowadzać żadnych
swap na pierwszym przejeździe.

119
00:05:12,550 --> 00:05:14,940
Więc może musimy patrzeć
w mniejszej ilości elementów, prawda?

120
00:05:14,940 --> 00:05:18,580
Nie musimy to powtórzyć
przetwarzać wiele razy.

121
00:05:18,580 --> 00:05:19,540
>> Więc co to oznacza?

122
00:05:19,540 --> 00:05:22,390
Więc co jest najgorszym przypadku
dla bubble rodzaju, a co

123
00:05:22,390 --> 00:05:25,330
najlepszy scenariusz dla bubble rodzaju?

124
00:05:25,330 --> 00:05:27,770
Czy, że to?

125
00:05:27,770 --> 00:05:32,420
W najgorszym przypadku trzeba iteracji
we wszystkich elementach n n razy.

126
00:05:32,420 --> 00:05:34,220
Tak więc w najgorszym przypadku jest n do kwadratu.

127
00:05:34,220 --> 00:05:36,550
>> Jeśli tablica jest idealnie
sortowane choć, tylko ty

128
00:05:36,550 --> 00:05:38,580
patrzeć na siebie
Once elementów.

129
00:05:38,580 --> 00:05:42,670
A jeśli licznik wymiany jest nadal 0,
można powiedzieć, ta tablica jest posortowana.

130
00:05:42,670 --> 00:05:45,780
A więc w najlepszym przypadku jest
lepsza niż wybór

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

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

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

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