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

2
00:00:02,840 --> 00:00:04,560
[JACKSON Steinkamp Harvard University]

3
00:00:04,560 --> 00:00:07,500
[Jest to CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Sortuj Bubble jest przykładem algorytmu sortowania -

5
00:00:11,730 --> 00:00:14,460
to jest procedura sortowania zestawu elementów w

6
00:00:14,460 --> 00:00:15,840
rosnąco lub malejąco.

7
00:00:15,840 --> 00:00:18,710
Na przykład, jeśli chcesz posortować tablicę składającą się z liczb

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], prawidłowe wdrażanie Sortuj Bubble wróci

9
00:00:23,060 --> 00:00:26,260
posortowana tablica [2, 3, 5, 9] w porządku rosnącym.

10
00:00:26,260 --> 00:00:28,850
Teraz mam zamiar wyjaśnić w Pseudokod jak algorytm działa.

11
00:00:28,850 --> 00:00:34,000
>> Powiedzmy, że mamy do sortowania listy 5 liczb - 3, 2, 9, 6, i 5.

12
00:00:34,000 --> 00:00:37,650
Algorytm rozpoczyna od na dwóch pierwszych elementów, 3 i 2,

13
00:00:37,650 --> 00:00:40,850
i sprawdza, czy są one w porządku w stosunku do siebie.

14
00:00:40,850 --> 00:00:43,150
Są - 3 jest większy niż 2,.

15
00:00:43,150 --> 00:00:45,190
Żeby być w porządku rosnącym, powinny być odwrotnie.

16
00:00:45,190 --> 00:00:46,610
Tak więc zamienić je.

17
00:00:46,610 --> 00:00:49,760
Teraz lista wygląda następująco: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Następnie patrzymy na drugim i trzecim elementów, 3 i 9.

19
00:00:52,450 --> 00:00:55,770
Są w odpowiedniej kolejności względem siebie.

20
00:00:55,770 --> 00:00:58,800
Oznacza to, że jest mniejsza niż 3 9 tak algorytm nie zamiany.

21
00:00:58,800 --> 00:01:01,900
Następnie patrzymy na 9 i 6. Są w porządku.

22
00:01:01,900 --> 00:01:04,260
>> Tak więc, musimy zamienić je, ponieważ 9 jest większa niż 6.

23
00:01:04,260 --> 00:01:08,840
Wreszcie, patrzymy na ostatnich dwóch liczb, 9 i 5.

24
00:01:08,840 --> 00:01:10,850
Oni są w porządku, więc muszą zostać zamienione.

25
00:01:10,850 --> 00:01:13,360
Po pierwszym przebiegu przez pełnej listy

26
00:01:13,360 --> 00:01:17,140
wygląda to tak: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nie jest źle. To prawie posortowane.

28
00:01:19,690 --> 00:01:22,450
Ale musimy uruchomić listę ponownie, aby ją całkowicie posortowane.

29
00:01:22,450 --> 00:01:29,250
Dwa to mniej niż 3, więc nie zamienić je.

30
00:01:29,250 --> 00:01:31,700
>> Trzy jest mniejsza niż 6, więc nie zamiany.

31
00:01:31,700 --> 00:01:35,500
Sześć jest większa niż 5 mm. Mamy zamienione.

32
00:01:35,500 --> 00:01:38,460
Sześć jest mniejsza od 9. Nie zamieniać.

33
00:01:38,460 --> 00:01:42,170
Po drugim przejściu przez, wygląda to tak: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
A teraz piszę to w Pseudokod.

35
00:01:44,680 --> 00:01:48,450
Zasadniczo, dla każdego elementu na liście, musimy na to patrzeć

36
00:01:48,450 --> 00:01:50,060
a elementem bezpośrednio po prawej stronie.

37
00:01:50,060 --> 00:01:53,420
Jeśli są one w porządku w odniesieniu do siebie - to jest, gdy element na lewo

38
00:01:53,420 --> 00:01:56,810
jest większa niż na prawo - należy zamienić dwa elementy.

39
00:01:56,810 --> 00:02:01,270
>> Robimy to dla każdego elementu na liście, a zrobiliśmy jeden przejść.

40
00:02:01,270 --> 00:02:05,160
Teraz musimy zrobić przełożenia tyle razy, aby zapewnić listę

41
00:02:05,160 --> 00:02:06,480
jest w pełni, prawidłowo posortowane.

42
00:02:06,480 --> 00:02:08,889
Ale ile razy mamy przejść przez liście

43
00:02:08,889 --> 00:02:10,400
Gwarantujemy, że skończyliśmy?

44
00:02:10,400 --> 00:02:14,730
Cóż, najgorszy scenariusz jest, jeśli mamy całkowicie wsteczną listę.

45
00:02:14,730 --> 00:02:17,840
Następnie bierze szereg przejazdu throughs równą liczbie

46
00:02:17,840 --> 00:02:19,730
elementów n-1.

47
00:02:19,730 --> 00:02:24,720
Jeśli to nie ma sensu, intuicyjnie, myślę o prostym przypadku - list [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> To zajmie jeden pass-through do sortowania poprawnie.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - w najgorszym przypadku jest to, że z 3 elementów posortowane tyłu

50
00:02:33,060 --> 00:02:34,830
to zajmie 2 iteracji do sortowania.

51
00:02:34,830 --> 00:02:37,980
Po jednej iteracji, to [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Drugi szereg plony posortowane [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Więc wiesz, że nigdy nie musiał przejść przez tablicę, w ogóle,

54
00:02:43,350 --> 00:02:46,790
więcej niż 1 razy N-, w którym n jest liczbą elementów w tablicy.

55
00:02:47,090 --> 00:02:50,470
To się nazywa Sortuj Bubble ponieważ największe elementy mają tendencję do "bubble-up '

56
00:02:50,470 --> 00:02:51,950
w prawo dość szybko.

57
00:02:51,950 --> 00:02:53,980
W rzeczywistości, to algorytm jest bardzo interesujące zachowanie.

58
00:02:53,980 --> 00:02:57,410
>> Po m iteracjach dzięki całej tablicy,

59
00:02:57,410 --> 00:02:59,000
skrajnej prawej elementy m są gwarantowane

60
00:02:59,000 --> 00:03:01,000
być posortowane w ich właściwym miejscu.

61
00:03:01,000 --> 00:03:02,280
Jeśli chcesz zobaczyć na własne oczy,

62
00:03:02,280 --> 00:03:05,500
możemy spróbować go na zupełnie wstecznej liście [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Po jednym przejściu przez całą listę,

64
00:03:08,220 --> 00:03:09,220
[Dźwięk pisania]

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
prawej stronie elementu 9 jest na swoim miejscu.

67
00:03:21,250 --> 00:03:24,760
Po drugim pass-through, 6 będzie miał "przepuszcza się" do

68
00:03:24,760 --> 00:03:26,220
sekund prawej stronie miejsce.

69
00:03:26,220 --> 00:03:28,840
Te dwa elementy na prawo - 6 i 9 - będzie w ich właściwych miejscach

70
00:03:28,840 --> 00:03:30,580
po pierwszych dwóch obwodnic-through.

71
00:03:30,580 --> 00:03:32,590
>> Tak, jak możemy to wykorzystać do optymalizacji algorytmu?

72
00:03:32,590 --> 00:03:34,850
Cóż, po jednej iteracji przez tablicę

73
00:03:34,850 --> 00:03:37,690
nie faktycznie trzeba sprawdzić element, po prawej stronie,

74
00:03:37,690 --> 00:03:39,200
ponieważ wiemy, że jest posortowane.

75
00:03:39,200 --> 00:03:43,050
Po dwóch iteracji, wiemy na pewno, po prawej stronie, dwa elementy są na swoim miejscu.

76
00:03:43,050 --> 00:03:48,260
Tak więc, ogólnie, po iteracji k do pełnej tablicy

77
00:03:48,260 --> 00:03:51,550
Sprawdzanie ostatnio k elementów jest zbędna, ponieważ wiemy

78
00:03:51,550 --> 00:03:52,360
są one w odpowiednim miejscu już.

79
00:03:52,360 --> 00:03:54,870
>> Więc jeśli jesteś sortowania tablicy n elementów,

80
00:03:54,870 --> 00:03:57,870
w pierwszej iteracji - you'll sortowania mają wszystkie elementy - pierwszy N-0.

81
00:03:57,870 --> 00:04:04,170
Na drugiej iteracji, trzeba patrzeć na wszystkie elementy, ale ostatni -

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

83
00:04:07,090 --> 00:04:10,520
Kolejna optymalizacja może być sprawdzenie, czy lista jest już posortowana

84
00:04:10,520 --> 00:04:11,710
po każdej iteracji.

85
00:04:11,710 --> 00:04:13,900
Jeśli jest już posortowane, nie musimy tworzyć kolejnych iteracji

86
00:04:13,900 --> 00:04:15,310
listę.

87
00:04:15,310 --> 00:04:16,220
W jaki sposób możemy to zrobić?

88
00:04:16,220 --> 00:04:19,360
Cóż, jeśli nie podejmiemy żadnych swapów na przełożenia na liście,

89
00:04:19,360 --> 00:04:22,350
to jasne, że lista została już posortowane, bo nie wymieniać wszystkiego.

90
00:04:22,350 --> 00:04:24,160
Więc na pewno nie trzeba sortować ponownie.

91
00:04:24,160 --> 00:04:27,960
>> Być może można zainicjować zmiennej flag nazwie 'nie posortowane "na

92
00:04:27,960 --> 00:04:30,990
false i zmień go na prawdziwe, jeśli masz do wymiany elementów na

93
00:04:30,990 --> 00:04:32,290
jedno powtórzenie przez tablicę.

94
00:04:32,290 --> 00:04:35,350
Lub podobnie, zrobić licznik na zliczyć swapy zrobić

95
00:04:35,350 --> 00:04:37,040
na każdej iteracji.

96
00:04:37,040 --> 00:04:40,040
Na koniec iteracji, jeżeli nie zmieniać pozycję elementów,

97
00:04:40,040 --> 00:04:41,780
wiesz, lista jest już posortowane i gotowe.

98
00:04:41,780 --> 00:04:44,090
Sortuj Bubble, podobnie jak inne algorytmy sortowania, mogą być

99
00:04:44,090 --> 00:04:46,960
manipulowane do pracy dla wszystkich elementów, które mają metodę zamawiania.

100
00:04:46,960 --> 00:04:50,610
>> Oznacza to, że biorąc pod uwagę dwa elementy, które mają sposób, aby powiedzieć, czy pierwsza

101
00:04:50,610 --> 00:04:53,770
jest większa, równa lub mniejsza od drugiej.

102
00:04:53,770 --> 00:04:56,870
Na przykład, można posortować litery alfabetu, mówiąc

103
00:04:56,870 --> 00:05:00,520
a <b, b <c, itp.

104
00:05:00,520 --> 00:05:03,830
Albo można sortować dni tygodnia, gdzie niedziela jest mniej niż w poniedziałek

105
00:05:03,830 --> 00:05:05,110
co jest mniej niż we wtorek.

106
00:05:05,110 --> 00:05:09,630
>> Sortuj Bubble nie jest wcale bardzo skuteczny lub szybki algorytm sortowania.

107
00:05:09,630 --> 00:05:12,370
Jego najgorszy czas pracy jest Big O n ²

108
00:05:12,370 --> 00:05:14,810
bo masz do iteracji n poprzez listę

109
00:05:14,810 --> 00:05:18,430
sprawdzenie wszystkich n elementów każdego pass-through, NxN = n ².

110
00:05:18,430 --> 00:05:22,730
To oznacza, że ​​czas pracy, jak liczba elementów ty sortowania wzrost,

111
00:05:22,730 --> 00:05:24,330
czas pracy zwiększa kwadratu.

112
00:05:24,330 --> 00:05:27,330
>> Ale jeśli wydajność nie jest głównym problemem programu jest

113
00:05:27,330 --> 00:05:29,550
lub jeśli jesteś tylko sortowania niewielkiej liczby elementów,

114
00:05:29,550 --> 00:05:31,660
może się okazać użyteczne, ponieważ Bubble Sort

115
00:05:31,660 --> 00:05:33,360
jest to jeden z najprostszych algorytmów sortowania, aby zrozumieć

116
00:05:33,360 --> 00:05:34,250
i kod.

117
00:05:34,250 --> 00:05:37,270
Jest to również świetny sposób, aby doświadczenie z tłumaczeniem teoretycznym

118
00:05:37,270 --> 00:05:40,220
Algorytm do rzeczywistego kodu funkcjonowania.

119
00:05:40,220 --> 00:05:43,000
Dobrze, że to sortowanie bąbelkowe dla Ciebie. Dzięki za oglądanie.

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