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
>> [Música tocando]

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

3
00:00:04,522 --> 00:00:06,730
Doug LLOYD: Todo ben, entón
bubble sort é un algoritmo

4
00:00:06,730 --> 00:00:08,730
pode usar para clasificar un conxunto de elementos.

5
00:00:08,730 --> 00:00:10,850
Imos dar un ollo a como funciona.

6
00:00:10,850 --> 00:00:13,240
>> Así, a idea básica por tras
bubble sort é este.

7
00:00:13,240 --> 00:00:17,340
Nós xeralmente queren mover superior
elementos valorados xeralmente cara á dereita,

8
00:00:17,340 --> 00:00:20,340
e diminuír elementos valorados en xeral
á esquerda, como sería de esperar.

9
00:00:20,340 --> 00:00:23,256
Queremos que as cousas máis baixas para estar en
o principio, e as cousas máis elevadas

10
00:00:23,256 --> 00:00:24,970
ser ao final.

11
00:00:24,970 --> 00:00:26,130
>> Como podemos facer isto?

12
00:00:26,130 --> 00:00:28,040
Ben no código pseudocódigo,
poderiamos dicir, imos

13
00:00:28,040 --> 00:00:30,320
definir un contador de intercambio para un valor distinto de cero.

14
00:00:30,320 --> 00:00:32,570
A ver por que facemos isto nun segundo.

15
00:00:32,570 --> 00:00:36,090
E, despois, repetir o seguinte
proceso ata que o contador de intercambio é 0,

16
00:00:36,090 --> 00:00:39,910
ou ata que non facemos swaps en todo.

17
00:00:39,910 --> 00:00:43,170
>> Reinicie o contador de intercambio para
0 se non é xa 0.

18
00:00:43,170 --> 00:00:46,420
A continuación, ollar para cada
par adxacente de elementos.

19
00:00:46,420 --> 00:00:49,550
Se estes dous elementos son
non en orde, troca-los,

20
00:00:49,550 --> 00:00:51,620
e engadir 1 ao contador de intercambio.

21
00:00:51,620 --> 00:00:53,870
Se está a pensar en
que antes de vela,

22
00:00:53,870 --> 00:00:57,471
notar que este pode mover máis baixo
elementos valiosos á esquerda

23
00:00:57,471 --> 00:01:00,720
e elementos para a dereita valorado superior,
efectivamente facendo o que queremos facer,

24
00:01:00,720 --> 00:01:03,940
que é mover eses grupos
de elementos en que xeito.

25
00:01:03,940 --> 00:01:07,035
Imos ver como este
pode parecer a través da nosa gama

26
00:01:07,035 --> 00:01:10,504
que foi utilizado para probar
estes algoritmos.

27
00:01:10,504 --> 00:01:13,420
Temos unha matriz unsorted aquí de novo,
indicado por todos os elementos

28
00:01:13,420 --> 00:01:14,840
sendo a vermello.

29
00:01:14,840 --> 00:01:17,970
E eu que o meu contador de intercambio
para un valor distinto de cero.

30
00:01:17,970 --> 00:01:20,610
Eu escollín arbitrariamente
1-- negativo non é 0.

31
00:01:20,610 --> 00:01:23,840
Queremos repetir este proceso
ata que o contador de intercambio é 0.

32
00:01:23,840 --> 00:01:26,540
É por iso que eu definir a miña cambio
contador para un valor distinto de cero,

33
00:01:26,540 --> 00:01:29,400
porque se non o
contador de intercambio sería 0.

34
00:01:29,400 --> 00:01:31,610
Nós nin sequera comezar a
proceso do algoritmo.

35
00:01:31,610 --> 00:01:33,610
Entón, de novo, os pasos é--
axustar o temporizador de intercambio

36
00:01:33,610 --> 00:01:37,900
a 0, a continuación, ollar para cada lado
par, e no caso de que están fóra de orde,

37
00:01:37,900 --> 00:01:40,514
trocalos e engadir 1
para o contador de intercambio.

38
00:01:40,514 --> 00:01:41,680
Entón, imos comezar este proceso.

39
00:01:41,680 --> 00:01:44,430
Entón o primeiro que facemos é
imos definir o contador de intercambio a 0,

40
00:01:44,430 --> 00:01:46,660
e, despois, comezar a ollar
en cada par adxacente.

41
00:01:46,660 --> 00:01:49,140
>> Así que comezamos a mirar para 5 e 2.

42
00:01:49,140 --> 00:01:52,410
Vemos que están fóra de
orde e para que trocalos.

43
00:01:52,410 --> 00:01:53,830
E nós engadimos 1 ao contador intercambio.

44
00:01:53,830 --> 00:01:57,860
Polo tanto, agora o noso contador de intercambio é un,
e 2 e 5 foron trocados.

45
00:01:57,860 --> 00:01:59,370
Agora imos repetir o proceso de novo.

46
00:01:59,370 --> 00:02:03,540
>> Nós miramos para a próxima par adxacente,
5 e 1-- son tamén fóra de orde,

47
00:02:03,540 --> 00:02:06,960
así que trocalos e engadir
1 ao balcón intercambio.

48
00:02:06,960 --> 00:02:08,900
Entón, miramos para 5 e 3.

49
00:02:08,900 --> 00:02:13,830
Eles están fóra de orde, polo que trocar
eles e nós engadimos 1 ao contador intercambio.

50
00:02:13,830 --> 00:02:15,550
Entón, miramos para 5 e 6.

51
00:02:15,550 --> 00:02:18,630
Eles están en orde, polo que, en realidade, non
Debe cambiar calquera cousa neste momento.

52
00:02:18,630 --> 00:02:20,250
Entón, miramos para 6 e 4.

53
00:02:20,250 --> 00:02:24,920
Eles están fóra de orde, polo que trocar
eles e nós engadimos 1 ao contador intercambio.

54
00:02:24,920 --> 00:02:26,230
>> Agora, teña en conta o que pasou.

55
00:02:26,230 --> 00:02:29,514
Nós movemos 6 todo o camiño ata o final.

56
00:02:29,514 --> 00:02:32,180
Entón, na selección tipo, se ten
visto que o vídeo, o que fixemos foi

57
00:02:32,180 --> 00:02:35,290
acabamos cambiando a
menores elementos en construción

58
00:02:35,290 --> 00:02:39,640
a matriz clasificada esencialmente da
esquerda a dereita, menor ao maior.

59
00:02:39,640 --> 00:02:43,200
No caso de bubble sort, se estamos
seguindo este algoritmo en particular,

60
00:02:43,200 --> 00:02:46,720
imos realmente a ser a construción de
a matriz clasificada da dereita

61
00:02:46,720 --> 00:02:49,100
á esquerda, maior a menor.

62
00:02:49,100 --> 00:02:53,840
Temos efectivamente borbulhar 6, a
O maior valor, todo o camiño ata o final.

63
00:02:53,840 --> 00:02:56,165
>> E así podemos agora declarar
que é ordenada,

64
00:02:56,165 --> 00:02:59,130
e no futuro iterations--
pasando a matriz novamente--

65
00:02:59,130 --> 00:03:01,280
non hai que considerar 6 anymore.

66
00:03:01,280 --> 00:03:03,850
Nós só temos que considerar
os elementos sen clasificar

67
00:03:03,850 --> 00:03:06,299
cando nós estamos mirando para pares adxacentes.

68
00:03:06,299 --> 00:03:08,340
Entón, temos que rematar unha
pasar por bubble sort.

69
00:03:08,340 --> 00:03:11,941
Entón agora imos voltar á cuestión,
repetir ata que o contador de intercambio é 0.

70
00:03:11,941 --> 00:03:13,690
Ben, o contador de intercambio
é 4, entón imos

71
00:03:13,690 --> 00:03:15,410
para continuar a repetir este proceso de novo.

72
00:03:15,410 --> 00:03:19,180
>> Estamos indo para axustar o temporizador de intercambio
a 0, e ollar para cada par adxacente.

73
00:03:19,180 --> 00:03:21,890
Entón, imos comezar con dous e son 1--
fóra de orde, de xeito que trocalos

74
00:03:21,890 --> 00:03:23,620
e nós engadimos 1 ao contador intercambio.

75
00:03:23,620 --> 00:03:25,490
2 e 3, están en orde.

76
00:03:25,490 --> 00:03:27,060
Non necesitamos facer nada.

77
00:03:27,060 --> 00:03:28,420
3 e 5 están en orde.

78
00:03:28,420 --> 00:03:30,150
Non necesitamos facer nada alí.

79
00:03:30,150 --> 00:03:32,515
>> 5 e 4, están fóra
de orde, e por iso,

80
00:03:32,515 --> 00:03:35,130
Debe trocalos e engadir
1 ao balcón intercambio.

81
00:03:35,130 --> 00:03:38,880
E agora nós movemo 5,
o segundo elemento,

82
00:03:38,880 --> 00:03:40,920
para o fin da porción sen clasificar.

83
00:03:40,920 --> 00:03:44,360
Entón agora podemos chamar
parte da porción clasificada.

84
00:03:44,360 --> 00:03:47,180
>> Agora está mirando para o
pantalla e probablemente pode dicir,

85
00:03:47,180 --> 00:03:50,130
como pode I, que a matriz
se clasifica no momento.

86
00:03:50,130 --> 00:03:51,820
Pero non podemos probalo aínda.

87
00:03:51,820 --> 00:03:54,359
Non temos unha garantía
que está clasificado.

88
00:03:54,359 --> 00:03:56,900
Pero é aí onde o intercambio
contador vai entrar en xogo.

89
00:03:56,900 --> 00:03:59,060
>> Entón, nós completados un pase.

90
00:03:59,060 --> 00:04:00,357
O contador de intercambio é de 2.

91
00:04:00,357 --> 00:04:02,190
Entón, nós estamos indo a repetir
este proceso novo,

92
00:04:02,190 --> 00:04:04,290
repetir ata que o contador de intercambio é 0.

93
00:04:04,290 --> 00:04:05,550
Reinicie o contador de intercambio a 0.

94
00:04:05,550 --> 00:04:06,820
Entón, imos axustar-la.

95
00:04:06,820 --> 00:04:09,810
>> Agora mire para cada par adxacente.

96
00:04:09,810 --> 00:04:11,880
Isto é en orde, 1 e 2.

97
00:04:11,880 --> 00:04:13,590
2 e 3 están en orde.

98
00:04:13,590 --> 00:04:15,010
3 e 4 están en orde.

99
00:04:15,010 --> 00:04:19,250
Polo tanto, neste punto, observe nós completados
mirando para cada par adxacente,

100
00:04:19,250 --> 00:04:22,530
pero o contador de intercambio que é 0.

101
00:04:22,530 --> 00:04:25,520
>> Se non temos que cambiar
calquera elementos, a continuación, eles

102
00:04:25,520 --> 00:04:28,340
deben estar en orde, por
virtude deste proceso.

103
00:04:28,340 --> 00:04:32,000
E así unha eficiencia de tipos,
que os científicos da computación que amamos,

104
00:04:32,000 --> 00:04:35,560
agora podemos declarar
toda a matriz debe

105
00:04:35,560 --> 00:04:38,160
son ordenados, porque non
ter que cambiar todos os elementos.

106
00:04:38,160 --> 00:04:40,380
Iso é moi bo.

107
00:04:40,380 --> 00:04:43,260
>> Entón, cal é o peor caso
escenario con bubble sort?

108
00:04:43,260 --> 00:04:46,240
No peor caso, a matriz é
a fin completamente inversa,

109
00:04:46,240 --> 00:04:49,870
e por iso temos que burbulla cada
dos grandes elementos todos

110
00:04:49,870 --> 00:04:51,780
a maneira a través da matriz.

111
00:04:51,780 --> 00:04:55,350
E nós tamén temos que efectivamente
burbulla todos os pequenos elementos de volta

112
00:04:55,350 --> 00:04:57,050
en toda a extensión da matriz, tamén.

113
00:04:57,050 --> 00:05:01,950
Así, cada un dos elementos n debe moverse
entre todos os outros elementos n.

114
00:05:01,950 --> 00:05:04,102
Entón ese é o peor escenario posible.

115
00:05:04,102 --> 00:05:05,810
No mellor dos casos
escenario, con todo, este é

116
00:05:05,810 --> 00:05:07,880
lixeiramente diferente da selección de clasificación.

117
00:05:07,880 --> 00:05:10,040
A matriz é xa
clasificadas cando imos.

118
00:05:10,040 --> 00:05:12,550
Non hai que facer calquera
swaps sobre a primeira pasaxe.

119
00:05:12,550 --> 00:05:14,940
Por iso, pode ter que ollar
polo menos elementos, non?

120
00:05:14,940 --> 00:05:18,580
Non temos que repetir este
procesar un certo número de veces.

121
00:05:18,580 --> 00:05:19,540
>> Entón, o que significa isto?

122
00:05:19,540 --> 00:05:22,390
Entón, cal é o peor escenario
para bubble sort, eo que é

123
00:05:22,390 --> 00:05:25,330
o mellor escenario para bubble sort?

124
00:05:25,330 --> 00:05:27,770
Vostede creo que iso?

125
00:05:27,770 --> 00:05:32,420
No peor dos casos ten que facer unha iteración
en todos os elementos n veces n.

126
00:05:32,420 --> 00:05:34,220
Así, o peor caso é n ao cadrado.

127
00:05:34,220 --> 00:05:36,550
>> Se a matriz é perfectamente
ordenada, porén, só

128
00:05:36,550 --> 00:05:38,580
Ten que mirar para cada
os elementos dunha vez.

129
00:05:38,580 --> 00:05:42,670
E se o contador de intercambio que é 0,
pode dicir que esta matriz é clasificada.

130
00:05:42,670 --> 00:05:45,780
E así, no mellor dos casos, é dicir
realmente mellor que a selección

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

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

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

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