1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
1
00:00:00,000 --> 00:00:03,360
>> [MUSIK SPELA]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Okej, så
bubbelsortering är en algoritm

4
00:00:06,730 --> 00:00:08,730
du kan använda för att sortera en rad faktorer.

5
00:00:08,730 --> 00:00:10,850
Låt oss ta en titt på hur det fungerar.

6
00:00:10,850 --> 00:00:13,240
>> Så grundidén bakom
bubbelsortering är detta.

7
00:00:13,240 --> 00:00:17,340
Vi vill i allmänhet att röra sig högre
värderade element i allmänhet till höger,

8
00:00:17,340 --> 00:00:20,340
och lägre värderade element i allmänhet
till vänster, som vi skulle förvänta oss.

9
00:00:20,340 --> 00:00:23,256
Vi vill att lägre saker att vara på
början, och de högre saker

10
00:00:23,256 --> 00:00:24,970
att vara i slutet.

11
00:00:24,970 --> 00:00:26,130
>> Hur gör vi detta?

12
00:00:26,130 --> 00:00:28,040
Väl i pseudokod kod,
Vi kan säga, låt oss

13
00:00:28,040 --> 00:00:30,320
ange en swap mot en icke-noll.

14
00:00:30,320 --> 00:00:32,570
Vi får se varför vi gör det i en sekund.

15
00:00:32,570 --> 00:00:36,090
Och då är vi upprepa följande
processen tills swap räknaren är 0,

16
00:00:36,090 --> 00:00:39,910
eller tills vi gör inga swappar alls.

17
00:00:39,910 --> 00:00:43,170
>> Återställ swap mot
0 om den inte redan är 0.

18
00:00:43,170 --> 00:00:46,420
Så titta på varje
intilliggande par av element.

19
00:00:46,420 --> 00:00:49,550
Om dessa två element är
inte är i ordning, byta dem,

20
00:00:49,550 --> 00:00:51,620
och tillsätt en på växlingsräknaren.

21
00:00:51,620 --> 00:00:53,870
Om du funderar på
detta innan du visualisera det,

22
00:00:53,870 --> 00:00:57,471
märka att detta kommer att flytta lägre
värderade element till vänster

23
00:00:57,471 --> 00:01:00,720
och högre värderade element till höger,
effektivt gör vad vi vill göra,

24
00:01:00,720 --> 00:01:03,940
vilket är flytta dessa grupper
element på detta sätt.

25
00:01:03,940 --> 00:01:07,035
Låt oss visualisera hur detta
kan se med hjälp av vår array

26
00:01:07,035 --> 00:01:10,504
som vi använde för att testa
ut dessa algoritmer.

27
00:01:10,504 --> 00:01:13,420
Vi har en osorterad array här igen,
indikeras av alla elementen

28
00:01:13,420 --> 00:01:14,840
vara i rött.

29
00:01:14,840 --> 00:01:17,970
Och jag ställer min swap disk
till ett värde skilt från noll.

30
00:01:17,970 --> 00:01:20,610
Jag godtyckligt valde
negativt 1-- det är inte 0.

31
00:01:20,610 --> 00:01:23,840
Vi vill upprepa denna process
tills swap räknaren är 0.

32
00:01:23,840 --> 00:01:26,540
Detta är anledningen till att jag in min swap
mot vissa icke-nollvärde,

33
00:01:26,540 --> 00:01:29,400
eftersom annars
swap disk skulle vara 0.

34
00:01:29,400 --> 00:01:31,610
Vi skulle inte ens börja
förfarandet enligt algoritmen.

35
00:01:31,610 --> 00:01:33,610
Så återigen, stegen är--
återställa swap räknaren

36
00:01:33,610 --> 00:01:37,900
0, sedan titta på varje intilliggande
par, och om de är i ordning,

37
00:01:37,900 --> 00:01:40,514
byta dem, och tillsätt 1
till swap räknaren.

38
00:01:40,514 --> 00:01:41,680
Så låt oss börja den här processen.

39
00:01:41,680 --> 00:01:44,430
Så det första vi gör är
vi sätter swap mot 0,

40
00:01:44,430 --> 00:01:46,660
och sedan börjar vi ser
vid varje angränsande par.

41
00:01:46,660 --> 00:01:49,140
>> Så vi först börja titta på 5 och 2.

42
00:01:49,140 --> 00:01:52,410
Vi ser att de är ute ur
ordning och så vi byta dem.

43
00:01:52,410 --> 00:01:53,830
Och vi lägger 1 till swap räknaren.

44
00:01:53,830 --> 00:01:57,860
Så nu vår swap disk är en,
och 2 och 5 har kopplats.

45
00:01:57,860 --> 00:01:59,370
Nu är vi upprepa processen igen.

46
00:01:59,370 --> 00:02:03,540
>> Vi tittar på nästa intilliggande par,
5 och 1-- de är också i ordning,

47
00:02:03,540 --> 00:02:06,960
så vi byta dem och lägg
1 till swap räknaren.

48
00:02:06,960 --> 00:02:08,900
Sedan tittar vi på 5 och 3.

49
00:02:08,900 --> 00:02:13,830
De är i ordning, så vi byta
dem och vi lägger en till swap räknaren.

50
00:02:13,830 --> 00:02:15,550
Sedan tittar vi på 5 och 6.

51
00:02:15,550 --> 00:02:18,630
De är i ordning, så vi egentligen inte
behöver byta något den här gången.

52
00:02:18,630 --> 00:02:20,250
Sedan tittar vi på 6 och 4.

53
00:02:20,250 --> 00:02:24,920
De är också i ordning, så vi byta
dem och vi lägger en till swap räknaren.

54
00:02:24,920 --> 00:02:26,230
>> Nu märker vad som har hänt.

55
00:02:26,230 --> 00:02:29,514
Vi har flyttat 6 hela vägen till slutet.

56
00:02:29,514 --> 00:02:32,180
Så i valet sort, om du har
sett att video, vad vi gjorde var

57
00:02:32,180 --> 00:02:35,290
Vi hamnade flytta
minsta element i byggnaden

58
00:02:35,290 --> 00:02:39,640
den sorterade arrayen huvudsakligen från
från vänster till höger, minsta till största.

59
00:02:39,640 --> 00:02:43,200
I fallet med bubbelsortering, om vi är
följer efter denna särskilda algoritm,

60
00:02:43,200 --> 00:02:46,720
vi faktiskt kommer att bygga
den sorterade arrayen från höger

61
00:02:46,720 --> 00:02:49,100
till vänster, största till minsta.

62
00:02:49,100 --> 00:02:53,840
Vi har faktiskt bubblade 6, den
största värde, hela vägen till slutet.

63
00:02:53,840 --> 00:02:56,165
>> Och så vi kan nu förklara
att detta är sorterad,

64
00:02:56,165 --> 00:02:59,130
och i framtiden iterations--
går igenom arrayen igen--

65
00:02:59,130 --> 00:03:01,280
Vi behöver inte tänka på sex längre.

66
00:03:01,280 --> 00:03:03,850
Vi behöver bara tänka på
de osorterade element

67
00:03:03,850 --> 00:03:06,299
När vi tittar på angränsande par.

68
00:03:06,299 --> 00:03:08,340
Så vi har avslutat ett
passera genom bubbelsortering.

69
00:03:08,340 --> 00:03:11,941
Så nu går vi tillbaka till frågan,
Upprepa tills swap räknaren är 0.

70
00:03:11,941 --> 00:03:13,690
Tja swap räknaren
är 4, så vi tänker

71
00:03:13,690 --> 00:03:15,410
att fortsätta att upprepa denna process igen.

72
00:03:15,410 --> 00:03:19,180
>> Vi kommer att återställa swap räknaren
till 0, och titta på varje intilliggande par.

73
00:03:19,180 --> 00:03:21,890
Så vi börjar med två och 1-- de är
i ordning, så vi byta dem

74
00:03:21,890 --> 00:03:23,620
och vi lägger en till swap räknaren.

75
00:03:23,620 --> 00:03:25,490
2 och 3, de är i ordning.

76
00:03:25,490 --> 00:03:27,060
Vi behöver inte göra någonting.

77
00:03:27,060 --> 00:03:28,420
3 och 5 är i ordning.

78
00:03:28,420 --> 00:03:30,150
Vi behöver inte göra något där.

79
00:03:30,150 --> 00:03:32,515
>> 5 och 4, de är ute
av ordning, och så vi

80
00:03:32,515 --> 00:03:35,130
måste byta dem och lägg
1 till swap räknaren.

81
00:03:35,130 --> 00:03:38,880
Och nu har vi flyttat 5,
den näst största elementet,

82
00:03:38,880 --> 00:03:40,920
till slutet av osorterade delen.

83
00:03:40,920 --> 00:03:44,360
Så kan vi nu kallar det
en del av det sorterade partiet.

84
00:03:44,360 --> 00:03:47,180
>> Nu är du tittar på den
skärm och förmodligen kan berätta,

85
00:03:47,180 --> 00:03:50,130
som kan jag, att uppsättningen
sorteras just nu.

86
00:03:50,130 --> 00:03:51,820
Men vi kan inte bevisa det ännu.

87
00:03:51,820 --> 00:03:54,359
Vi har inte en garanti
att det är för sortering.

88
00:03:54,359 --> 00:03:56,900
Men det är där swap
disk kommer att träda i funktion.

89
00:03:56,900 --> 00:03:59,060
>> Så vi har avslutat ett pass.

90
00:03:59,060 --> 00:04:00,357
Swapräknaren är 2.

91
00:04:00,357 --> 00:04:02,190
Så vi kommer att upprepa
denna process igen,

92
00:04:02,190 --> 00:04:04,290
Upprepa tills swap räknaren är 0.

93
00:04:04,290 --> 00:04:05,550
Återställ swap mot 0.

94
00:04:05,550 --> 00:04:06,820
Så vi kommer att återställa den.

95
00:04:06,820 --> 00:04:09,810
>> Nu tittar på varje angränsande par.

96
00:04:09,810 --> 00:04:11,880
Det är i sin ordning, 1 och 2.

97
00:04:11,880 --> 00:04:13,590
2 och 3 är i ordning.

98
00:04:13,590 --> 00:04:15,010
3 och 4 är i ordning.

99
00:04:15,010 --> 00:04:19,250
Så på denna punkt, märker vi har slutfört
titta på varje angränsande par,

100
00:04:19,250 --> 00:04:22,530
men swap räknaren är fortfarande 0.

101
00:04:22,530 --> 00:04:25,520
>> Om vi ​​inte behöver växla
några element, då de

102
00:04:25,520 --> 00:04:28,340
måste vara i ordning, genom
kraft av denna process.

103
00:04:28,340 --> 00:04:32,000
Och så en effektivitet av olika slag,
att vi datavetare älskar,

104
00:04:32,000 --> 00:04:35,560
är vi nu deklarera
hela gruppen måste

105
00:04:35,560 --> 00:04:38,160
sorteras, eftersom vi inte
måste byta några delar.

106
00:04:38,160 --> 00:04:40,380
Det är ganska trevligt.

107
00:04:40,380 --> 00:04:43,260
>> Så vad är det värsta fallet
scenario med bubbelsortering?

108
00:04:43,260 --> 00:04:46,240
I värsta fall arrayen är
i helt omvänd ordning,

109
00:04:46,240 --> 00:04:49,870
och så vi måste bubbla varje
av de stora elementen alla

110
00:04:49,870 --> 00:04:51,780
vägen över arrayen.

111
00:04:51,780 --> 00:04:55,350
Och vi effektivt även behöva
bubbla alla de små elementen tillbaka

112
00:04:55,350 --> 00:04:57,050
hela vägen över arrayen, också.

113
00:04:57,050 --> 00:05:01,950
Så vart och ett av de n elementen måste flytta
över alla de andra n element.

114
00:05:01,950 --> 00:05:04,102
Så det är det värsta scenariot.

115
00:05:04,102 --> 00:05:05,810
I bästa fall
scenario är dock detta

116
00:05:05,810 --> 00:05:07,880
skiljer sig något från val slag.

117
00:05:07,880 --> 00:05:10,040
Matrisen är redan
sorterade när vi går in.

118
00:05:10,040 --> 00:05:12,550
Vi behöver inte göra några
swappar på det första passet.

119
00:05:12,550 --> 00:05:14,940
Så vi kanske måste se
på färre element, eller hur?

120
00:05:14,940 --> 00:05:18,580
Vi behöver inte upprepa denna
bearbeta ett antal gånger under.

121
00:05:18,580 --> 00:05:19,540
>> Så vad betyder det?

122
00:05:19,540 --> 00:05:22,390
Så vad är det värsta scenariot
för bubbelsortering, och vad som är

123
00:05:22,390 --> 00:05:25,330
det bästa scenariot för bubbelsortering?

124
00:05:25,330 --> 00:05:27,770
Har du gissa det?

125
00:05:27,770 --> 00:05:32,420
I värsta fall måste man iterera
i alla de n elementen n gånger.

126
00:05:32,420 --> 00:05:34,220
Så det värsta fallet är n i kvadrat.

127
00:05:34,220 --> 00:05:36,550
>> Om arrayen är perfekt
sorterade men bara du

128
00:05:36,550 --> 00:05:38,580
måste titta på varje
av elementen gång.

129
00:05:38,580 --> 00:05:42,670
Och om växlingsräknaren fortfarande är 0,
du kan säga detta arrayen sorteras.

130
00:05:42,670 --> 00:05:45,780
Och så i bästa fall, är detta
faktiskt bättre än val

131
00:05:45,780 --> 00:05:49,230
sort-- det är omega n.

132
00:05:49,230 --> 00:05:50,270
>> Jag är Doug Lloyd.

133
00:05:50,270 --> 00:05:52,140
Detta är CS50.

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