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
[QUESTO E 'CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Ordine bolla è un esempio di un algoritmo di ordinamento -

5
00:00:11,730 --> 00:00:14,460
cioè, una procedura per l'ordinamento di un insieme di elementi in

6
00:00:14,460 --> 00:00:15,840
ordine crescente o decrescente.

7
00:00:15,840 --> 00:00:18,710
Per esempio, se si vuole ordinare un array costituito dai numeri

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], la corretta attuazione del Bubble Sort restituisce il

9
00:00:23,060 --> 00:00:26,260
array ordinato [2, 3, 5, 9], in ordine crescente.

10
00:00:26,260 --> 00:00:28,850
Ora, ho intenzione di spiegare in pseudocodice come funziona l'algoritmo.

11
00:00:28,850 --> 00:00:34,000
>> Diciamo che stiamo ordinamento di una lista di 5 numeri interi - 3, 2, 9, 6, e 5.

12
00:00:34,000 --> 00:00:37,650
L'algoritmo inizia esaminando i primi due elementi, 3 e 2,

13
00:00:37,650 --> 00:00:40,850
e controllando se sono fuori ordine rispetto all'altra.

14
00:00:40,850 --> 00:00:43,150
Sono - 3 è maggiore di 2.

15
00:00:43,150 --> 00:00:45,190
Per essere in ordine crescente, che dovrebbe essere il contrario.

16
00:00:45,190 --> 00:00:46,610
Quindi, li scambiare.

17
00:00:46,610 --> 00:00:49,760
Ora la lista è simile al seguente: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Quindi, guardiamo gli elementi secondo e il terzo, 3 e 9.

19
00:00:52,450 --> 00:00:55,770
Sono nell'ordine corretto rispetto all'altro.

20
00:00:55,770 --> 00:00:58,800
Cioè, 3 è inferiore a 9 quindi l'algoritmo non sostituirle.

21
00:00:58,800 --> 00:01:01,900
Quindi, guardiamo alle 9 e 6. Sono fuori uso.

22
00:01:01,900 --> 00:01:04,260
>> Quindi, abbiamo bisogno di scambiare loro, perché 9 è maggiore di 6.

23
00:01:04,260 --> 00:01:08,840
Infine, guardiamo gli ultimi due numeri interi, 9 e 5.

24
00:01:08,840 --> 00:01:10,850
Sono fuori di ordine, quindi devono essere scambiati.

25
00:01:10,850 --> 00:01:13,360
Dopo il primo passaggio completa l'elenco,

26
00:01:13,360 --> 00:01:17,140
che appare così: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Non male. E 'quasi ordinato.

28
00:01:19,690 --> 00:01:22,450
Ma abbiamo bisogno di scorrere la lista di nuovo per farlo completamente ordinato.

29
00:01:22,450 --> 00:01:29,250
Due è inferiore a 3, quindi non li scambiare.

30
00:01:29,250 --> 00:01:31,700
>> Tre è inferiore a 6, in modo da non li scambiare.

31
00:01:31,700 --> 00:01:35,500
Sei è maggiore di 5. Ci scambiammo.

32
00:01:35,500 --> 00:01:38,460
Sei è inferiore a 9. Noi non scambiare.

33
00:01:38,460 --> 00:01:42,170
Dopo il secondo passaggio, che appare così: [2, 3, 5, 6, 9]. Perfetto.

34
00:01:42,170 --> 00:01:44,680
Ora, cerchiamo di scrivere in pseudocodice.

35
00:01:44,680 --> 00:01:48,450
In sostanza, per ogni elemento della lista, abbiamo bisogno di vedere le cose

36
00:01:48,450 --> 00:01:50,060
e l'elemento direttamente alla sua destra.

37
00:01:50,060 --> 00:01:53,420
Se essi non sono in ordine rispetto all'altra - cioè, se l'elemento a sinistra

38
00:01:53,420 --> 00:01:56,810
è maggiore di quella di destra - dobbiamo scambiare i due elementi.

39
00:01:56,810 --> 00:02:01,270
>> Lo facciamo per ogni elemento della lista, e abbiamo fatto un solo passaggio attraverso.

40
00:02:01,270 --> 00:02:05,160
Ora non ci resta che fare il pass-through di volte sufficiente a garantire la lista

41
00:02:05,160 --> 00:02:06,480
è completamente, opportunamente ordinati.

42
00:02:06,480 --> 00:02:08,889
Ma quante volte dobbiamo passare attraverso l'elenco per

43
00:02:08,889 --> 00:02:10,400
garantire che abbiamo finito?

44
00:02:10,400 --> 00:02:14,730
Beh, la peggiore delle ipotesi è che se abbiamo una lista completamente all'indietro.

45
00:02:14,730 --> 00:02:17,840
Poi prende un numero di pass-through pari al numero

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

47
00:02:19,730 --> 00:02:24,720
Se questo non ha senso intuitivo, pensare ad un semplice caso - l'elenco [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Si tratta di andare a prendere un pass-through per ordinare correttamente.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Il caso peggiore è che con 3 elementi ordinati al contrario,

50
00:02:33,060 --> 00:02:34,830
sta andando a prendere 2 iterazioni da ordinare.

51
00:02:34,830 --> 00:02:37,980
Dopo una iterazione, è [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Le rese secondo l'array ordinato [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Quindi sai che non deve passare attraverso la matrice, in generale,

54
00:02:43,350 --> 00:02:46,790
più di n-1 volte, dove n è il numero di elementi nella matrice.

55
00:02:47,090 --> 00:02:50,470
Si chiama Bubble Sort, perché gli elementi più grandi tendono a 'bubble-up'

56
00:02:50,470 --> 00:02:51,950
a destra abbastanza rapidamente.

57
00:02:51,950 --> 00:02:53,980
In realtà, questo algoritmo ha un comportamento molto interessante.

58
00:02:53,980 --> 00:02:57,410
>> Dopo m iterazioni attraverso l'intero array,

59
00:02:57,410 --> 00:02:59,000
gli elementi più a destra m sono garantiti

60
00:02:59,000 --> 00:03:01,000
da ordinare nella loro posizione corretta.

61
00:03:01,000 --> 00:03:02,280
Se volete vedere questo per te,

62
00:03:02,280 --> 00:03:05,500
siamo in grado di provare in un elenco completamente all'indietro [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Dopo un passaggio attraverso l'intero elenco,

64
00:03:08,220 --> 00:03:09,220
[Suono di scrittura]

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
l'elemento più a destra 9 è al suo posto.

67
00:03:21,250 --> 00:03:24,760
Dopo la seconda pass-through, il 6 avra 'bollito-up' al

68
00:03:24,760 --> 00:03:26,220
secondo posto più a destra.

69
00:03:26,220 --> 00:03:28,840
I due elementi a destra - 6 e 9 - sarà nelle loro posizioni corrette

70
00:03:28,840 --> 00:03:30,580
dopo i primi due pass-through.

71
00:03:30,580 --> 00:03:32,590
>> Quindi, come possiamo usare questo per ottimizzare l'algoritmo?

72
00:03:32,590 --> 00:03:34,850
Bene, dopo un'iterazione attraverso l'array

73
00:03:34,850 --> 00:03:37,690
in realtà non è necessario per controllare l'elemento più a destra

74
00:03:37,690 --> 00:03:39,200
perché sappiamo che è ordinato.

75
00:03:39,200 --> 00:03:43,050
Dopo due iterazioni, sappiamo per certo più a destra i due elementi sono in atto.

76
00:03:43,050 --> 00:03:48,260
Quindi, in generale, dopo k iterazioni attraverso la matrice completa,

77
00:03:48,260 --> 00:03:51,550
controllo degli elementi k ultimi è ridondante poiché sappiamo

78
00:03:51,550 --> 00:03:52,360
sono nella posizione corretta già.

79
00:03:52,360 --> 00:03:54,870
>> Quindi, se siete ordinamento di un array di n elementi,

80
00:03:54,870 --> 00:03:57,870
alla prima iterazione - hai dovuto ordinare tutti gli elementi - il primo n-0.

81
00:03:57,870 --> 00:04:04,170
Nella seconda iterazione, si dovrà esaminare tutti gli elementi, ma l'ultima -

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

83
00:04:07,090 --> 00:04:10,520
Un'altra ottimizzazione potrebbe essere quello di verificare se la lista è già ordinato

84
00:04:10,520 --> 00:04:11,710
dopo ogni iterazione.

85
00:04:11,710 --> 00:04:13,900
Se è già ordinato, non abbiamo bisogno di fare più iterazioni

86
00:04:13,900 --> 00:04:15,310
l'elenco.

87
00:04:15,310 --> 00:04:16,220
Come possiamo fare questo?

88
00:04:16,220 --> 00:04:19,360
Beh, se non si fa nessun swap su un pass-through della lista,

89
00:04:19,360 --> 00:04:22,350
è chiaro che l'elenco è stato già ordinato perché non scambiare nulla.

90
00:04:22,350 --> 00:04:24,160
Quindi sicuramente non c'è bisogno di ordinare di nuovo.

91
00:04:24,160 --> 00:04:27,960
>> Forse si potrebbe inizializzare una variabile flag definito 'non ordinati' per

92
00:04:27,960 --> 00:04:30,990
false e cambia a true se si deve scambiare qualsiasi altro elemento

93
00:04:30,990 --> 00:04:32,290
un'iterazione attraverso l'array.

94
00:04:32,290 --> 00:04:35,350
Oppure allo stesso modo, fare un contatore per contare il numero di operazioni di swap si fanno

95
00:04:35,350 --> 00:04:37,040
su ogni iterazione determinato.

96
00:04:37,040 --> 00:04:40,040
Al termine di una iterazione, se non scambiare qualsiasi degli elementi,

97
00:04:40,040 --> 00:04:41,780
si conosce la lista è già ordinato e il gioco è fatto.

98
00:04:41,780 --> 00:04:44,090
Bubble Sort, come altri algoritmi di ordinamento, può essere

99
00:04:44,090 --> 00:04:46,960
ottimizzato per lavorare per tutti gli elementi che hanno un metodo di ordinamento.

100
00:04:46,960 --> 00:04:50,610
>> In altre parole, dati due elementi si dispone di un modo per dire se il primo

101
00:04:50,610 --> 00:04:53,770
è maggiore, uguale o minore della seconda.

102
00:04:53,770 --> 00:04:56,870
Ad esempio, è possibile ordinare le lettere dell'alfabeto dicendo

103
00:04:56,870 --> 00:05:00,520
che a <b, b <c, ecc

104
00:05:00,520 --> 00:05:03,830
Oppure si potrebbe ordinare i giorni della settimana in cui Domenica è inferiore a Lunedi

105
00:05:03,830 --> 00:05:05,110
che è inferiore Martedì.

106
00:05:05,110 --> 00:05:09,630
>> Ordina Bubble non è affatto un algoritmo di ordinamento molto efficiente e veloce.

107
00:05:09,630 --> 00:05:12,370
Il caso peggiore di runtime è Big O di n ²

108
00:05:12,370 --> 00:05:14,810
perché si deve fare n iterazioni attraverso un elenco

109
00:05:14,810 --> 00:05:18,430
controllare tutti gli elementi n ogni pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Questa fase di esecuzione significa che il numero di elementi che stai ordinamento aumenta,

111
00:05:22,730 --> 00:05:24,330
il tempo di esecuzione aumenta quadraticamente.

112
00:05:24,330 --> 00:05:27,330
>> Ma se l'efficienza non è una preoccupazione importante del vostro programma

113
00:05:27,330 --> 00:05:29,550
o se siete solo ordinare un piccolo numero di elementi,

114
00:05:29,550 --> 00:05:31,660
si potrebbe trovare Bubble Sort utile perché

115
00:05:31,660 --> 00:05:33,360
è uno dei più semplici algoritmi di ordinamento per capire

116
00:05:33,360 --> 00:05:34,250
e per codice.

117
00:05:34,250 --> 00:05:37,270
E 'anche un ottimo modo per ottenere esperienza con traduzione di un teorico

118
00:05:37,270 --> 00:05:40,220
algoritmo in codice reale funzionamento.

119
00:05:40,220 --> 00:05:43,000
Beh, e 'Bubble Sort per voi. Grazie per la visione.

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