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 HARVARD UNIVERSITY]

3
00:00:04,560 --> 00:00:07,500
[DIT IS CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble Sort is een voorbeeld van een sorteer-algoritme -

5
00:00:11,730 --> 00:00:14,460
dat is, een procedure voor het sorteren van een reeks elementen in

6
00:00:14,460 --> 00:00:15,840
oplopende of aflopende volgorde.

7
00:00:15,840 --> 00:00:18,710
Bijvoorbeeld, als je wilde een array sorteren bestaande uit de getallen

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], zou een correcte implementatie van Bubble Sort terugkeer van de

9
00:00:23,060 --> 00:00:26,260
gesorteerde array [2, 3, 5, 9] in oplopende volgorde.

10
00:00:26,260 --> 00:00:28,850
Nu, ik ga uitleggen in pseudocode hoe het algoritme werkt.

11
00:00:28,850 --> 00:00:34,000
>> Laten we zeggen dat we een lijst van 5 integers sorteren - 3, 2, 9, 6 en 5.

12
00:00:34,000 --> 00:00:37,650
Het algoritme begint met te kijken naar de eerste twee elementen, 3 en 2,

13
00:00:37,650 --> 00:00:40,850
en controleren of ze uit de orde ten opzichte van elkaar.

14
00:00:40,850 --> 00:00:43,150
Ze zijn - 3 groter is dan 2.

15
00:00:43,150 --> 00:00:45,190
Om in oplopende volgorde, moeten zij omgekeerd.

16
00:00:45,190 --> 00:00:46,610
Dus, we ruilen.

17
00:00:46,610 --> 00:00:49,760
Nu is de lijst ziet er als volgt uit: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Vervolgens kijken we naar de tweede en derde elementen, 3 en 9.

19
00:00:52,450 --> 00:00:55,770
Ze zijn in de juiste volgorde ten opzichte van elkaar.

20
00:00:55,770 --> 00:00:58,800
Dat wil zeggen, 3 minder dan 9, zodat het algoritme niet verwisselen.

21
00:00:58,800 --> 00:01:01,900
Vervolgens kijken we naar 9 en 6. Ze zijn niet in orde.

22
00:01:01,900 --> 00:01:04,260
>> Dus, we moeten ze ruilen, want 9 is groter dan 6.

23
00:01:04,260 --> 00:01:08,840
Tot slot kijken we naar de laatste twee gehele getallen, 9 en 5.

24
00:01:08,840 --> 00:01:10,850
Ze zijn niet in orde, dus ze moeten worden verwisseld.

25
00:01:10,850 --> 00:01:13,360
Na de eerste volledige passage door de lijst,

26
00:01:13,360 --> 00:01:17,140
ziet het er zo uit: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Niet slecht. Het is bijna gesorteerd.

28
00:01:19,690 --> 00:01:22,450
Maar we moeten weer te lopen door de lijst om het te krijgen volledig gesorteerd.

29
00:01:22,450 --> 00:01:29,250
Twee minder dan 3, zodat we niet ruilen.

30
00:01:29,250 --> 00:01:31,700
>> Drie is minder dan 6, zodat we niet ruilen.

31
00:01:31,700 --> 00:01:35,500
Zes groter is dan 5. We verwisseld.

32
00:01:35,500 --> 00:01:38,460
Zes minder dan 9. We hebben geen ruilen.

33
00:01:38,460 --> 00:01:42,170
Na de tweede passeren, ziet het er als volgt uit: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
Laten we nu eens schrijf het in pseudocode.

35
00:01:44,680 --> 00:01:48,450
Kortom, voor elk element in de lijst, moeten we kijken

36
00:01:48,450 --> 00:01:50,060
en het element direct aan de rechterkant.

37
00:01:50,060 --> 00:01:53,420
Als ze in orde ten opzichte van elkaar - dat wil zeggen als het element aan de linkerkant

38
00:01:53,420 --> 00:01:56,810
groter is dan de een aan de rechterkant - we moeten wisselen de twee elementen.

39
00:01:56,810 --> 00:02:01,270
>> We doen dit voor elk element van de lijst, en we hebben een doorgang door.

40
00:02:01,270 --> 00:02:05,160
Nu hoeven we alleen maar de pass-through vaak genoeg doen om de lijst te garanderen

41
00:02:05,160 --> 00:02:06,480
volledig, goed gesorteerd.

42
00:02:06,480 --> 00:02:08,889
Maar hoe vaak moeten we nog door de lijst door te geven aan

43
00:02:08,889 --> 00:02:10,400
garanderen dat we klaar zijn?

44
00:02:10,400 --> 00:02:14,730
Nou, de worst-case scenario is als we een volledig backwards lijst.

45
00:02:14,730 --> 00:02:17,840
Dan neemt een aantal sluizen gelijk aan het aantal

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

47
00:02:19,730 --> 00:02:24,720
Als dit niet intuïtief zin, denken aan een eenvoudig geval - de lijst [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Dit gaat een pass-through te nemen om volledig te kunnen sorteren.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - In het slechtste geval is dat met 3 elementen achteren gesorteerd,

50
00:02:33,060 --> 00:02:34,830
het gaat om 2 iteraties te nemen om te sorteren.

51
00:02:34,830 --> 00:02:37,980
Na een iteratie is [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
De tweede levert de gesorteerde array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Dus je weet dat je nooit meer hoeft te gaan door middel van de array, in het algemeen,

54
00:02:43,350 --> 00:02:46,790
dan n-1 keer, waarbij n het aantal elementen in de array.

55
00:02:47,090 --> 00:02:50,470
Het heet Bubble Sort omdat de grootste elementen hebben de neiging om 'bubble-up'

56
00:02:50,470 --> 00:02:51,950
aan de rechterkant vrij snel.

57
00:02:51,950 --> 00:02:53,980
In feite is dit algoritme interessant gedrag.

58
00:02:53,980 --> 00:02:57,410
>> Na m iteraties door de hele array,

59
00:02:57,410 --> 00:02:59,000
de rechter m elementen zijn gegarandeerd

60
00:02:59,000 --> 00:03:01,000
worden gesorteerd op hun juiste plaats.

61
00:03:01,000 --> 00:03:02,280
Als je dit wilt zien voor jezelf,

62
00:03:02,280 --> 00:03:05,500
we kunnen proberen een volledig achterwaarts lijst [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Na een doorgang door de hele lijst,

64
00:03:08,220 --> 00:03:09,220
[Geluid van schrijven]

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
de meest rechtse element 9 is op de juiste plaats.

67
00:03:21,250 --> 00:03:24,760
Na de tweede pass-through, zal de 6 hebben 'borrelde-up' aan de

68
00:03:24,760 --> 00:03:26,220
seconden meest rechtse plaats.

69
00:03:26,220 --> 00:03:28,840
De twee elementen rechts - 6 en 9 - worden in de juiste plaatsen

70
00:03:28,840 --> 00:03:30,580
na de eerste twee sluizen.

71
00:03:30,580 --> 00:03:32,590
>> Dus, hoe kunnen we dit gebruiken om het algoritme te optimaliseren?

72
00:03:32,590 --> 00:03:34,850
Nou, na een iteratie door de array

73
00:03:34,850 --> 00:03:37,690
we eigenlijk niet nodig om de meest rechtse element controleren

74
00:03:37,690 --> 00:03:39,200
omdat we weten dat het gesorteerd.

75
00:03:39,200 --> 00:03:43,050
Na twee iteraties, weten we zeker de meest rechtse twee elementen op hun plaats zitten.

76
00:03:43,050 --> 00:03:48,260
Dus in het algemeen na k iteraties door de volledige array,

77
00:03:48,260 --> 00:03:51,550
het controleren van de laatste k elementen is overbodig omdat we weten

78
00:03:51,550 --> 00:03:52,360
ze in de juiste locatie reeds.

79
00:03:52,360 --> 00:03:54,870
>> Dus als je het sorteren van een array van n elementen,

80
00:03:54,870 --> 00:03:57,870
de eerste iteratie - u zult moeten alle elementen sorteren - de eerste n-0.

81
00:03:57,870 --> 00:04:04,170
Op de tweede iteratie, zul je moeten kijken naar alle elementen, maar de laatste -

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

83
00:04:07,090 --> 00:04:10,520
Een andere optimalisatie zou kunnen zijn om te controleren of de lijst is al gesorteerd

84
00:04:10,520 --> 00:04:11,710
na elke iteratie.

85
00:04:11,710 --> 00:04:13,900
Als het al gesorteerd, hebben we geen behoefte aan een meer iteraties te maken

86
00:04:13,900 --> 00:04:15,310
door de lijst.

87
00:04:15,310 --> 00:04:16,220
Hoe kunnen we dit doen?

88
00:04:16,220 --> 00:04:19,360
Nou, als we geen swaps te maken op een doorwerking van de lijst,

89
00:04:19,360 --> 00:04:22,350
het is duidelijk dat de lijst al was gesorteerd, omdat we niet ruilen niets.

90
00:04:22,350 --> 00:04:24,160
Dus we zeker niet nog een keer te sorteren.

91
00:04:24,160 --> 00:04:27,960
>> Misschien kunt u initialiseren een vlag variabele genaamd 'niet gesorteerd' te

92
00:04:27,960 --> 00:04:30,990
Valse en verander het naar waar als je moet alle elementen op ruilen

93
00:04:30,990 --> 00:04:32,290
een iteratie door de array.

94
00:04:32,290 --> 00:04:35,350
Of een andere soortgelijke, maak een teller om te tellen hoeveel swaps u

95
00:04:35,350 --> 00:04:37,040
op een bepaalde iteratie.

96
00:04:37,040 --> 00:04:40,040
Aan het einde van een iteratie, als je niet ruilen voor een van de elementen,

97
00:04:40,040 --> 00:04:41,780
je weet de lijst is al gesorteerd en je bent klaar.

98
00:04:41,780 --> 00:04:44,090
Bubble Sort, net als andere sortering algoritmen, kan

99
00:04:44,090 --> 00:04:46,960
getweaked om te werken voor alle elementen die een bestelling methode.

100
00:04:46,960 --> 00:04:50,610
>> Dat wil zeggen, gegeven twee elementen heb je een manier om te zeggen als de eerste

101
00:04:50,610 --> 00:04:53,770
groter dan, gelijk aan of kleiner dan de tweede.

102
00:04:53,770 --> 00:04:56,870
Bijvoorbeeld, kon u sorteren letters van het alfabet door te zeggen

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

104
00:05:00,520 --> 00:05:03,830
Of je zou kunnen sorteren dagen van de week, waar zondag is minder dan maandag

105
00:05:03,830 --> 00:05:05,110
die kleiner is dan dinsdag.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sort is geenszins een zeer efficiënt of snel sorteren algoritme.

107
00:05:09,630 --> 00:05:12,370
Het worst-case runtime is Big O van n ²

108
00:05:12,370 --> 00:05:14,810
want je moet n iteraties te maken door middel van een lijst

109
00:05:14,810 --> 00:05:18,430
controleren van alle n elementen elk pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Deze looptijd betekent dat als het aantal elementen dat je stijgt het sorteren,

111
00:05:22,730 --> 00:05:24,330
de looptijd neemt kwadratisch.

112
00:05:24,330 --> 00:05:27,330
>> Maar als efficiëntie is niet een grote zorg van uw programma

113
00:05:27,330 --> 00:05:29,550
of als je alleen het sorteren van een klein aantal elementen,

114
00:05:29,550 --> 00:05:31,660
je zou kunnen vinden Bubble Sort nuttig omdat

115
00:05:31,660 --> 00:05:33,360
het is een van de eenvoudigste sorteren algoritmen te begrijpen

116
00:05:33,360 --> 00:05:34,250
en coderen.

117
00:05:34,250 --> 00:05:37,270
Het is ook een geweldige manier om ervaring op te doen met het vertalen van een theoretische

118
00:05:37,270 --> 00:05:40,220
algoritme in feitelijk functioneren code.

119
00:05:40,220 --> 00:05:43,000
Nou, dat is Bubble Sort voor jou. Bedankt voor het kijken.

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