1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Diamo un'occhiata a ordinamento per selezione, un algoritmo

2
00:00:09,980 --> 00:00:12,800
per prendere un elenco di numeri e ordinamento.

3
00:00:12,800 --> 00:00:15,750
Un algoritmo, lo ricordiamo, è semplicemente uno step-by-step

4
00:00:15,750 --> 00:00:18,370
procedimento per realizzare un compito.

5
00:00:18,370 --> 00:00:21,470
L'idea alla base di ordinamento per selezione è quello di dividere

6
00:00:21,470 --> 00:00:23,390
la nostra lista in due parti -

7
00:00:23,390 --> 00:00:26,810
una porzione di cernita e di una parte non ordinato.

8
00:00:26,810 --> 00:00:30,200
Ad ogni passo dell'algoritmo, un numero viene spostato dalla

9
00:00:30,200 --> 00:00:33,800
parte non ordinata alla porzione ordinato fino alla fine il

10
00:00:33,800 --> 00:00:35,880
l'intero elenco è ordinato.

11
00:00:35,880 --> 00:00:38,510
Quindi, ecco un elenco di sei numeri -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, e 15.

13
00:00:44,010 --> 00:00:47,680
In questo momento l'intero elenco è considerato ordinato.

14
00:00:47,680 --> 00:00:51,770
Anche se un numero come 16 potrebbe già essere nella sua corretta

15
00:00:51,770 --> 00:00:56,040
posizione, il nostro algoritmo non ha modo di sapere che fino a quando il

16
00:00:56,040 --> 00:00:57,980
l'intero elenco è ordinato.

17
00:00:57,980 --> 00:01:01,355
Quindi dovremo considerare ogni numero da unsorted fino ordinare

18
00:01:01,355 --> 00:01:03,800
noi stessi.

19
00:01:03,800 --> 00:01:06,890
Sappiamo che si desidera che l'elenco sia in ordine crescente.

20
00:01:06,890 --> 00:01:10,200
Quindi dobbiamo provare a costruire la parte ordinata della nostra lista

21
00:01:10,200 --> 00:01:13,280
da sinistra a destra, dal più piccolo al più grande.

22
00:01:13,280 --> 00:01:17,970
Per fare questo, abbiamo bisogno di trovare l'elemento minimo unsorted

23
00:01:17,970 --> 00:01:21,350
e messo alla fine della porzione ordinato.

24
00:01:21,350 --> 00:01:25,370
Dal momento che questo elenco non è ordinato, l'unico modo per farlo è quello di

25
00:01:25,370 --> 00:01:29,330
guardare ogni elemento nella porzione unsorted, ricordando

26
00:01:29,330 --> 00:01:32,010
elemento che è il più basso e confrontando

27
00:01:32,010 --> 00:01:33,770
ciascun elemento a questo.

28
00:01:33,770 --> 00:01:36,150
Quindi per prima cosa guardare il 23.

29
00:01:36,150 --> 00:01:38,650
Questo è il primo elemento che abbiamo visto, così ci ricorderemo

30
00:01:38,650 --> 00:01:40,050
come il minimo.

31
00:01:40,050 --> 00:01:42,320
Avanti vedremo 42.

32
00:01:42,320 --> 00:01:46,720
42 è maggiore di 23, quindi 23 è ancora il minimo.

33
00:01:46,720 --> 00:01:51,210
La prossima è il 4, che è inferiore a 23, per cui ci ricorderemo quattro

34
00:01:51,210 --> 00:01:52,880
come il nuovo minimo.

35
00:01:52,880 --> 00:01:56,380
Successivo è 16, che è più grande di 4, quindi 4

36
00:01:56,380 --> 00:01:57,980
è ancora il minimo.

37
00:01:57,980 --> 00:02:03,670
8 è maggiore di 4, e 15 è maggiore di 4, quindi 4 deve essere

38
00:02:03,670 --> 00:02:05,980
l'elemento più piccolo indifferenziati.

39
00:02:05,980 --> 00:02:09,350
Così, anche se, come gli esseri umani si può subito vedere che 4 è

40
00:02:09,350 --> 00:02:12,300
l'elemento minimo, il nostro algoritmo ha bisogno di guardare al

41
00:02:12,300 --> 00:02:15,710
ogni elemento indifferenziato, anche dopo che abbiamo trovato il 4 - il

42
00:02:15,710 --> 00:02:16,860
elemento minimo.

43
00:02:16,860 --> 00:02:19,900
Quindi, ora che abbiamo trovato l'elemento minimo, 4, ci vorrà

44
00:02:19,900 --> 00:02:23,410
per spostarlo nella porzione ordinata della lista.

45
00:02:23,410 --> 00:02:27,320
Poiché questo è il primo passo, questo significa che vogliamo mettere a 4

46
00:02:27,320 --> 00:02:29,680
all'inizio della lista.

47
00:02:29,680 --> 00:02:33,040
Adesso 23 è all'inizio della lista, così

48
00:02:33,040 --> 00:02:36,080
Barattiamo il 4 e il 23.

49
00:02:36,080 --> 00:02:38,870
Così ora la nostra lista simile a questa.

50
00:02:38,870 --> 00:02:42,710
Sappiamo che 4 deve essere nella sua posizione definitiva, perché è

51
00:02:42,710 --> 00:02:45,890
sia il più piccolo elemento e l'elemento all'inizio

52
00:02:45,890 --> 00:02:46,960
dell'elenco.

53
00:02:46,960 --> 00:02:50,650
Quindi questo significa che non abbiamo mai bisogno di muoversi di nuovo.

54
00:02:50,650 --> 00:02:53,910
Quindi cerchiamo di ripetere questo processo per aggiungere un altro elemento alla

55
00:02:53,910 --> 00:02:55,910
porzione della lista ordinata.

56
00:02:55,910 --> 00:02:58,950
Sappiamo che non abbiamo bisogno di guardare il 4, perché è

57
00:02:58,950 --> 00:03:00,000
già ordinati.

58
00:03:00,000 --> 00:03:03,540
Così possiamo iniziare dal 42, che ci ricorderemo come il

59
00:03:03,540 --> 00:03:05,290
elemento minimo.

60
00:03:05,290 --> 00:03:08,700
Così la prossima vedremo il 23, che è inferiore a 42, in modo da

61
00:03:08,700 --> 00:03:11,620
ricordate 23 è il nuovo minimo.

62
00:03:11,620 --> 00:03:14,870
Quindi, vediamo la 16, che è inferiore a 23, così

63
00:03:14,870 --> 00:03:16,800
16 è il nuovo minimo.

64
00:03:16,800 --> 00:03:19,720
Ora guardiamo la 8 che è inferiore a 16, in modo da

65
00:03:19,720 --> 00:03:21,130
8 è il nuovo minimo.

66
00:03:21,130 --> 00:03:25,900
E infine 8 è minore di 15, quindi sappiamo che 8 è un minimo

67
00:03:25,900 --> 00:03:27,780
elemento indifferenziati.

68
00:03:27,780 --> 00:03:30,660
Questo significa che dobbiamo aggiungere 8 al ordinati

69
00:03:30,660 --> 00:03:32,450
porzione della lista.

70
00:03:32,450 --> 00:03:35,990
In questo momento 4 è l'unico elemento selezionato, quindi vogliamo mettere

71
00:03:35,990 --> 00:03:38,410
l'8 vicino al 4.

72
00:03:38,410 --> 00:03:41,920
Poiché 42 è il primo elemento nella porzione non ordinata

73
00:03:41,920 --> 00:03:47,260
lista, dobbiamo provare a scambiare il 42 e l'8.

74
00:03:47,260 --> 00:03:49,680
Così ora la nostra lista simile a questa.

75
00:03:49,680 --> 00:03:53,830
4 e 8 rappresentano la porzione della lista ordinata, e la

76
00:03:53,830 --> 00:03:56,440
numeri rimanenti rappresentano il unsorted

77
00:03:56,440 --> 00:03:58,260
porzione della lista.

78
00:03:58,260 --> 00:04:00,630
Quindi cerchiamo di continuare con un'altra iterazione.

79
00:04:00,630 --> 00:04:03,850
Si comincia con 23 questa volta, dal momento che non c'è bisogno di guardare

80
00:04:03,850 --> 00:04:05,770
il 4 e l'8 più perché hanno

81
00:04:05,770 --> 00:04:07,660
già stati ordinati.

82
00:04:07,660 --> 00:04:10,270
16 è inferiore a 23, per cui ci ricorderemo

83
00:04:10,270 --> 00:04:12,070
16 come nuovo minimo.

84
00:04:12,070 --> 00:04:18,149
16 è minore di 42, ma 15 è inferiore a 16, quindi 15 deve essere

85
00:04:18,149 --> 00:04:20,480
l'elemento minimo indifferenziati.

86
00:04:20,480 --> 00:04:24,580
Quindi ora vogliamo scambiare la 15 e la 23 a

87
00:04:24,580 --> 00:04:26,310
ci danno questa lista.

88
00:04:26,310 --> 00:04:30,500
La porzione ordinata della lista consiste di 4, 8 e 15, e

89
00:04:30,500 --> 00:04:33,210
questi elementi sono ancora ordinati.

90
00:04:33,210 --> 00:04:36,900
Ma si da il caso che l'elemento successivo indifferenziati, 16,

91
00:04:36,900 --> 00:04:38,480
è già ordinato.

92
00:04:38,480 --> 00:04:42,060
Tuttavia, non c'è modo per il nostro algoritmo di sapere che il 16

93
00:04:42,060 --> 00:04:45,230
è già nella sua posizione corretta, quindi abbiamo ancora bisogno di

94
00:04:45,230 --> 00:04:47,870
ripetere lo stesso processo.

95
00:04:47,870 --> 00:04:53,750
Così vediamo che 16 è inferiore a 42, e 16 è inferiore a 23, in modo da

96
00:04:53,750 --> 00:04:56,230
16 deve essere l'elemento minimo.

97
00:04:56,230 --> 00:04:59,010
E 'impossibile sostituire questo elemento con se stesso, in modo che possiamo

98
00:04:59,010 --> 00:05:01,780
semplicemente lasciarlo in questa posizione.

99
00:05:01,780 --> 00:05:04,660
Quindi abbiamo bisogno di un altro passaggio del nostro algoritmo.

100
00:05:04,660 --> 00:05:09,370
42 è maggiore di 23, quindi 23 deve essere

101
00:05:09,370 --> 00:05:10,970
minimo elemento indifferenziati.

102
00:05:10,970 --> 00:05:17,410
Una volta che ci scambiamo il 23 e il 42, si finisce con il nostro finale

103
00:05:17,410 --> 00:05:18,530
lista ordinata -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Sappiamo che 42 devono essere nel posto giusto dal momento che è il

106
00:05:26,830 --> 00:05:30,210
unico elemento a sinistra, e questo è per selezione.

107
00:05:30,210 --> 00:05:32,100
Passiamo ora formalizzare il nostro algoritmo con un po '

108
00:05:32,100 --> 00:05:34,540
pseudocodice.

109
00:05:34,540 --> 00:05:37,760
In linea uno, possiamo vedere che abbiamo bisogno di integrare più

110
00:05:37,760 --> 00:05:39,530
ogni elemento della lista.

111
00:05:39,530 --> 00:05:42,150
Tranne l'ultimo elemento, in quanto il 1 elemento

112
00:05:42,150 --> 00:05:44,230
lista è già ordinato.

113
00:05:44,230 --> 00:05:48,100
On line due, si considera il primo elemento della unsorted

114
00:05:48,100 --> 00:05:51,080
parte della lista per essere il minimo, come abbiamo fatto con il nostro

115
00:05:51,080 --> 00:05:53,750
esempio, così abbiamo qualcosa da confrontare.

116
00:05:53,750 --> 00:05:57,260
Linea tre inizia un secondo ciclo in cui iterare

117
00:05:57,260 --> 00:05:59,170
ogni elemento indifferenziati.

118
00:05:59,170 --> 00:06:02,150
Sappiamo che dopo i iterazioni, la parte ordinata

119
00:06:02,150 --> 00:06:05,330
della nostra lista deve avere i elementi in esso da ogni passo

120
00:06:05,330 --> 00:06:06,890
tipo un elemento.

121
00:06:06,890 --> 00:06:11,770
Quindi il primo elemento indifferenziato deve essere in posizione i più 1.

122
00:06:11,770 --> 00:06:15,440
On line quattro, si confronta l'elemento corrente al minimo

123
00:06:15,440 --> 00:06:17,750
elemento che abbiamo visto finora.

124
00:06:17,750 --> 00:06:20,560
Se l'elemento corrente è inferiore al minimo

125
00:06:20,560 --> 00:06:23,870
elemento, allora si dovrebbe ricordare l'elemento corrente come nuovo

126
00:06:23,870 --> 00:06:26,250
minimo sulla linea cinque.

127
00:06:26,250 --> 00:06:29,900
Infine, sulle linee di sei e sette, si scambiano il minimo

128
00:06:29,900 --> 00:06:33,080
elemento con il primo elemento indifferenziato, così

129
00:06:33,080 --> 00:06:36,990
aggiungerlo alla porzione della lista ordinata.

130
00:06:36,990 --> 00:06:40,030
Una volta che abbiamo un algoritmo, una domanda importante per chiedere

131
00:06:40,030 --> 00:06:43,370
noi stessi come i programmatori è quanto tempo ci vuole?

132
00:06:43,370 --> 00:06:46,970
Ecco ora la domanda quanto tempo ci vuole per questo

133
00:06:46,970 --> 00:06:50,070
algoritmo per l'esecuzione nel caso peggiore?

134
00:06:50,070 --> 00:06:51,640
Richiamo che rappresentiamo questa corsa

135
00:06:51,640 --> 00:06:55,060
tempo con grande notazione O.

136
00:06:55,060 --> 00:06:58,650
Per determinare l'elemento minimo unsorted, abbiamo

137
00:06:58,650 --> 00:07:01,880
essenzialmente dovuto confrontare ogni elemento della lista per

138
00:07:01,880 --> 00:07:04,040
ogni altro elemento della lista.

139
00:07:04,040 --> 00:07:08,430
Intuitivamente, questo suona come una O di funzionamento n quadrato.

140
00:07:08,430 --> 00:07:12,050
Guardando alla nostra pseudocodice, abbiamo anche un ciclo nidificato all'interno

141
00:07:12,050 --> 00:07:14,420
un altro loop, che suona davvero come una O

142
00:07:14,420 --> 00:07:16,480
di funzionamento n quadrato.

143
00:07:16,480 --> 00:07:19,250
Tuttavia, ricordate che non abbiamo bisogno di guardare oltre il

144
00:07:19,250 --> 00:07:23,460
intero elenco nel determinare l'elemento minimo unsorted?

145
00:07:23,460 --> 00:07:26,600
Una volta sapeva che il 4 è stato risolto, per esempio, non abbiamo

146
00:07:26,600 --> 00:07:28,170
bisogno di guardare di nuovo.

147
00:07:28,170 --> 00:07:31,020
Così fa questo basso è il tempo di esecuzione?

148
00:07:31,020 --> 00:07:34,510
Per la nostra lista di lunghezza 6, avevamo bisogno di fare cinque

149
00:07:34,510 --> 00:07:37,990
confronti per il primo elemento, per quattro confronti

150
00:07:37,990 --> 00:07:40,750
il secondo elemento, e così via.

151
00:07:40,750 --> 00:07:44,690
Ciò significa che il numero totale di passi è la somma di

152
00:07:44,690 --> 00:07:49,160
gli interi da 1 a la lunghezza della lista meno 1.

153
00:07:49,160 --> 00:07:51,005
Possiamo rappresentare questo con una sommatoria.

154
00:07:57,980 --> 00:07:59,910
Non andrà in sommatorie qui.

155
00:07:59,910 --> 00:08:04,900
Ma si scopre che questa sommatoria è uguale an volte

156
00:08:04,900 --> 00:08:07,540
n meno 1 su 2.

157
00:08:07,540 --> 00:08:14,220
O, equivalentemente, n quadrato più di 2 su 2 meno n.

158
00:08:14,220 --> 00:08:18,860
Quando si parla di runtime asintotico, questo termine n quadrato

159
00:08:18,860 --> 00:08:22,070
sta andando a dominare questo termine n.

160
00:08:22,070 --> 00:08:27,850
Quindi, ordinamento per selezione è O di n quadrato.

161
00:08:27,850 --> 00:08:31,460
Ricordiamo che nel nostro esempio, ordinamento per selezione ancora bisogno di

162
00:08:31,460 --> 00:08:33,850
verificare se un numero che è già stato risolto

163
00:08:33,850 --> 00:08:35,450
bisogno di essere spostati.

164
00:08:35,450 --> 00:08:38,929
In modo che significa che se abbiamo corso per selezione su una già

165
00:08:38,929 --> 00:08:43,070
lista ordinata, richiederebbe lo stesso numero di passi come

166
00:08:43,070 --> 00:08:46,340
sarebbe quando si esegue su un elenco del tutto indifferenziati.

167
00:08:46,340 --> 00:08:51,470
Quindi, ordinamento per selezione ha una prestazione migliore dei casi di quadrato n,

168
00:08:51,470 --> 00:08:56,820
che noi rappresentiamo con omega n quadrato.

169
00:08:56,820 --> 00:08:58,600
E questo è tutto per il selection sort.

170
00:08:58,600 --> 00:09:00,630
Solo uno dei molti algoritmi che possiamo

171
00:09:00,630 --> 00:09:02,390
utilizzare per ordinare un elenco.

172
00:09:02,390 --> 00:09:05,910
Il mio nome è Tommy, e questo è CS50.