1
00:00:00,000 --> 00:00:03,360
>> [RIPRODUZIONE DI BRANI MUSICALI]

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

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Va bene, allora
bubble sort è un algoritmo

4
00:00:06,730 --> 00:00:08,730
è possibile utilizzare per ordinare un insieme di elementi.

5
00:00:08,730 --> 00:00:10,850
Diamo uno sguardo a come funziona.

6
00:00:10,850 --> 00:00:13,240
>> L'idea di base dietro
bubble sort è questo.

7
00:00:13,240 --> 00:00:17,340
In genere vogliamo andare più alto
Elementi valutati generalmente a destra,

8
00:00:17,340 --> 00:00:20,340
e abbassare elementi valutati in generale
a sinistra, come ci aspetteremmo.

9
00:00:20,340 --> 00:00:23,256
Vogliamo che le cose inferiori di essere al
All'inizio, e le cose più elevate

10
00:00:23,256 --> 00:00:24,970
per essere alla fine.

11
00:00:24,970 --> 00:00:26,130
>> Come facciamo questo?

12
00:00:26,130 --> 00:00:28,040
Bene in codice pseudocodice,
potremmo dire, andiamo

13
00:00:28,040 --> 00:00:30,320
impostare un contatore swap per un valore diverso da zero.

14
00:00:30,320 --> 00:00:32,570
Vedremo perché lo facciamo in un secondo.

15
00:00:32,570 --> 00:00:36,090
E poi si ripete il seguente
processo fino a quando il contatore swap è 0,

16
00:00:36,090 --> 00:00:39,910
o fino a quando non facciamo swap a tutti.

17
00:00:39,910 --> 00:00:43,170
>> Azzerare il contatore swap
0 se non è già 0.

18
00:00:43,170 --> 00:00:46,420
Poi guardate ogni
coppia adiacente di elementi.

19
00:00:46,420 --> 00:00:49,550
Se questi due elementi sono
non in ordine, scambiarle,

20
00:00:49,550 --> 00:00:51,620
e aggiungere 1 al contatore di swap.

21
00:00:51,620 --> 00:00:53,870
Se stai pensando di
questo prima di visualizzarlo,

22
00:00:53,870 --> 00:00:57,471
si noti che questo si muoverà più basso
elementi valutati a sinistra

23
00:00:57,471 --> 00:01:00,720
e superiore valutati elementi alla destra,
effettivamente fare quello che vogliamo fare,

24
00:01:00,720 --> 00:01:03,940
che è spostare i gruppi
di elementi in questo modo.

25
00:01:03,940 --> 00:01:07,035
Cerchiamo di visualizzare come questo
potrebbe apparire con la nostra gamma

26
00:01:07,035 --> 00:01:10,504
che abbiamo usato per testare
questi algoritmi.

27
00:01:10,504 --> 00:01:13,420
Abbiamo un array non ordinato di nuovo qui,
indicata con tutti gli elementi

28
00:01:13,420 --> 00:01:14,840
essendo in rosso.

29
00:01:14,840 --> 00:01:17,970
E ho impostato il mio contatore di swap
ad un valore diverso da zero.

30
00:01:17,970 --> 00:01:20,610
Ho scelto arbitrariamente
negativo 1-- non è 0.

31
00:01:20,610 --> 00:01:23,840
Vogliamo ripetere questo processo
fino a quando il contatore di swap è 0.

32
00:01:23,840 --> 00:01:26,540
Questo è il motivo per cui ho impostato la mia di swap
contatore su un valore diverso da zero,

33
00:01:26,540 --> 00:01:29,400
perché altrimenti la
contatore di scambio sarebbe 0.

34
00:01:29,400 --> 00:01:31,610
Non avremmo nemmeno cominciare il
processo dell'algoritmo.

35
00:01:31,610 --> 00:01:33,610
Quindi, di nuovo, i passi are--
azzerare il contatore di scambio

36
00:01:33,610 --> 00:01:37,900
a 0, poi guardare ogni adiacente
coppia, e se sono in ordine,

37
00:01:37,900 --> 00:01:40,514
scambiarli, e aggiungere 1
al contatore swap.

38
00:01:40,514 --> 00:01:41,680
Quindi cerchiamo di iniziare questo processo.

39
00:01:41,680 --> 00:01:44,430
Quindi la prima cosa che facciamo è
abbiamo impostato il contatore di scambio a 0,

40
00:01:44,430 --> 00:01:46,660
e poi si parte alla ricerca
ad ogni coppia adiacente.

41
00:01:46,660 --> 00:01:49,140
>> Quindi per prima cosa iniziamo guardando 5 e 2.

42
00:01:49,140 --> 00:01:52,410
Vediamo che sono fuori
Ordine e così li scambiamo.

43
00:01:52,410 --> 00:01:53,830
E aggiungiamo 1 al bancone di swap.

44
00:01:53,830 --> 00:01:57,860
Così ora il nostro contatore di scambio è 1,
e 2 e 5 sono stati passati.

45
00:01:57,860 --> 00:01:59,370
Ora ripetiamo di nuovo il processo.

46
00:01:59,370 --> 00:02:03,540
>> Guardiamo alla prossima coppia adiacente,
5 e 1-- sono anche in ordine,

47
00:02:03,540 --> 00:02:06,960
così noi li scambiamo e aggiungere
1 al contatore swap.

48
00:02:06,960 --> 00:02:08,900
Poi guardiamo 5 e 3.

49
00:02:08,900 --> 00:02:13,830
Essi sono in ordine, in modo da scambiare
li e ci aggiungi 1 al bancone di swap.

50
00:02:13,830 --> 00:02:15,550
Poi guardiamo 5 e 6.

51
00:02:15,550 --> 00:02:18,630
Sono in ordine, in modo che in realtà non
hanno bisogno di scambiare nulla questa volta.

52
00:02:18,630 --> 00:02:20,250
Poi guardiamo 6 e 4.

53
00:02:20,250 --> 00:02:24,920
Sono anche fuori ordine, in modo da scambiare
li e ci aggiungi 1 al bancone di swap.

54
00:02:24,920 --> 00:02:26,230
>> Ora notate quello che è successo.

55
00:02:26,230 --> 00:02:29,514
Abbiamo spostato 6 fino alla fine.

56
00:02:29,514 --> 00:02:32,180
Quindi, in selezione tipo, se hai
visto che il video, quello che abbiamo fatto è stato

57
00:02:32,180 --> 00:02:35,290
abbiamo finito per spostare il
elementi più piccoli in edilizia

58
00:02:35,290 --> 00:02:39,640
l'array ordinato essenzialmente da
da sinistra a destra, piccolo al più grande.

59
00:02:39,640 --> 00:02:43,200
Nel caso di bubble sort, se siamo
seguendo questo particolare algoritmo,

60
00:02:43,200 --> 00:02:46,720
realmente stiamo andando a costruire
l'array ordinato da destra

61
00:02:46,720 --> 00:02:49,100
a sinistra, la più grande al più piccolo.

62
00:02:49,100 --> 00:02:53,840
Abbiamo effettivamente bolle 6, il
valore più grande, fino alla fine.

63
00:02:53,840 --> 00:02:56,165
>> E così ora possiamo dichiarare
che che è ordinato,

64
00:02:56,165 --> 00:02:59,130
e in futuro iterations--
passando attraverso l'array again--

65
00:02:59,130 --> 00:03:01,280
non dobbiamo considerare 6 più.

66
00:03:01,280 --> 00:03:03,850
Dobbiamo solo prendere in considerazione
gli elementi sottoposti a cernita

67
00:03:03,850 --> 00:03:06,299
quando stiamo guardando coppie adiacenti.

68
00:03:06,299 --> 00:03:08,340
Così abbiamo finito uno
passare attraverso bubble sort.

69
00:03:08,340 --> 00:03:11,941
Così ora torniamo alla domanda,
ripetere fino a quando il contatore di scambio è 0.

70
00:03:11,941 --> 00:03:13,690
Bene il contatore di scambio
è 4, quindi stiamo andando

71
00:03:13,690 --> 00:03:15,410
continuare a ripetere di nuovo il processo.

72
00:03:15,410 --> 00:03:19,180
>> Stiamo per azzerare il contatore di scambio
a 0, e guardare ogni coppia adiacente.

73
00:03:19,180 --> 00:03:21,890
Quindi si parte con 2 e 1-- sono
fuori uso, così li scambiamo

74
00:03:21,890 --> 00:03:23,620
e aggiungiamo 1 al bancone di swap.

75
00:03:23,620 --> 00:03:25,490
2 e 3, sono in ordine.

76
00:03:25,490 --> 00:03:27,060
Non abbiamo bisogno di fare nulla.

77
00:03:27,060 --> 00:03:28,420
3 e 5 sono in ordine.

78
00:03:28,420 --> 00:03:30,150
Non abbiamo bisogno di fare nulla.

79
00:03:30,150 --> 00:03:32,515
>> 5 e 4, sono fuori
di ordine, e così noi

80
00:03:32,515 --> 00:03:35,130
necessario per scambiarle e aggiungere
1 al contatore swap.

81
00:03:35,130 --> 00:03:38,880
E ora ci siamo spostati 5,
il successivo elemento più grande,

82
00:03:38,880 --> 00:03:40,920
alla fine della porzione indifferenziati.

83
00:03:40,920 --> 00:03:44,360
Così ora possiamo chiamare quella
parte della porzione filtrate.

84
00:03:44,360 --> 00:03:47,180
>> Ora si sta guardando la
schermo e probabilmente può dire,

85
00:03:47,180 --> 00:03:50,130
come posso, che l'array
è ordinato al momento.

86
00:03:50,130 --> 00:03:51,820
Ma non possiamo dimostrare ancora che.

87
00:03:51,820 --> 00:03:54,359
Non abbiamo una garanzia
che è ordinato.

88
00:03:54,359 --> 00:03:56,900
Ma questo è dove lo swap
contatore sta per entrare in gioco.

89
00:03:56,900 --> 00:03:59,060
>> Così abbiamo completato un passaggio.

90
00:03:59,060 --> 00:04:00,357
Il contatore swap è 2.

91
00:04:00,357 --> 00:04:02,190
Così stiamo andando a ripetere
nuovo questo processo,

92
00:04:02,190 --> 00:04:04,290
ripetere fino a quando il contatore di scambio è 0.

93
00:04:04,290 --> 00:04:05,550
Azzerare il contatore di scambio a 0.

94
00:04:05,550 --> 00:04:06,820
Quindi dovremo resettarlo.

95
00:04:06,820 --> 00:04:09,810
>> Ora guardate ogni coppia adiacente.

96
00:04:09,810 --> 00:04:11,880
Questo è in ordine, 1 e 2.

97
00:04:11,880 --> 00:04:13,590
2 e 3 sono in ordine.

98
00:04:13,590 --> 00:04:15,010
3 e 4 sono in ordine.

99
00:04:15,010 --> 00:04:19,250
Quindi a questo punto, notiamo abbiamo completato
guardando ogni coppia adiacente,

100
00:04:19,250 --> 00:04:22,530
ma il contatore di scambio è ancora 0.

101
00:04:22,530 --> 00:04:25,520
>> Se non abbiamo passare
elementi, allora

102
00:04:25,520 --> 00:04:28,340
deve essere in ordine, dal
virtù di questo processo.

103
00:04:28,340 --> 00:04:32,000
E così un rendimento di sorta,
che gli scienziati ci informatici amano,

104
00:04:32,000 --> 00:04:35,560
è ora possiamo dichiarare
l'intero array deve

105
00:04:35,560 --> 00:04:38,160
essere ordinati, perché non abbiamo fatto
avere scambiare elementi.

106
00:04:38,160 --> 00:04:40,380
Questo è abbastanza piacevole.

107
00:04:40,380 --> 00:04:43,260
>> Allora qual è il caso peggiore
scenario con bubble sort?

108
00:04:43,260 --> 00:04:46,240
Nel peggiore dei casi la matrice è
in ordine completamente inverso,

109
00:04:46,240 --> 00:04:49,870
e quindi dobbiamo bolla ogni
dei grandi elementi tutti

110
00:04:49,870 --> 00:04:51,780
il senso attraverso l'array.

111
00:04:51,780 --> 00:04:55,350
E abbiamo efficacemente anche a
bolla tutti i piccoli elementi indietro

112
00:04:55,350 --> 00:04:57,050
tutto il senso attraverso l'array, anche.

113
00:04:57,050 --> 00:05:01,950
Così ciascuno degli n elementi deve spostare
in tutti gli altri elementi n.

114
00:05:01,950 --> 00:05:04,102
Ecco, questo è lo scenario peggiore.

115
00:05:04,102 --> 00:05:05,810
Nel migliore dei casi
scenario però, questo è

116
00:05:05,810 --> 00:05:07,880
leggermente diverso da selection sort.

117
00:05:07,880 --> 00:05:10,040
La matrice è già
ordinato quando andiamo in.

118
00:05:10,040 --> 00:05:12,550
Noi non dobbiamo fare alcun
swap sul primo passaggio.

119
00:05:12,550 --> 00:05:14,940
Così potremmo avere a guardare
in minor numero di elementi, giusto?

120
00:05:14,940 --> 00:05:18,580
Noi non dobbiamo ripetere questo
elaborare un certo numero di volte.

121
00:05:18,580 --> 00:05:19,540
>> Che cosa significa?

122
00:05:19,540 --> 00:05:22,390
Quindi qual è la peggiore delle ipotesi
per bubble sort, e ciò che è

123
00:05:22,390 --> 00:05:25,330
la migliore delle ipotesi per il bubble sort?

124
00:05:25,330 --> 00:05:27,770
Hai fatto a indovinare questo?

125
00:05:27,770 --> 00:05:32,420
Nel peggiore dei casi si deve iterare
in tutti gli n elementi n volte.

126
00:05:32,420 --> 00:05:34,220
Così il caso peggiore è n quadrato.

127
00:05:34,220 --> 00:05:36,550
>> Se la matrice è perfettamente
ordinato, però, è solo

128
00:05:36,550 --> 00:05:38,580
guardare a ogni
degli elementi una volta.

129
00:05:38,580 --> 00:05:42,670
E se il contatore di scambio è ancora 0,
si può dire che questo array è ordinato.

130
00:05:42,670 --> 00:05:45,780
E così nel migliore dei casi, si tratta
in realtà meglio di selezione

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

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

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

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