1
00:00:00,000 --> 00:00:05,726
>> [RIPRODUZIONE DI BRANI MUSICALI]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: ordinamento per selezione è un
algoritmo che, come ci si potrebbe aspettare,

3
00:00:08,600 --> 00:00:10,470
ordina un insieme di elementi.

4
00:00:10,470 --> 00:00:12,470
E richiamo algoritmo
è un insieme passo-passo

5
00:00:12,470 --> 00:00:15,260
di istruzioni per il completamento di un compito.

6
00:00:15,260 --> 00:00:17,580
>> Nella selezione ordinare il
idea di base è questa,

7
00:00:17,580 --> 00:00:22,080
trovare il più piccolo elemento misti e
aggiungerlo alla fine della lista ordinata.

8
00:00:22,080 --> 00:00:26,970
In effetti ciò che fa è costruire
un elenco ordinato, un elemento alla volta.

9
00:00:26,970 --> 00:00:29,800
Scomponendola a pseudocodice
potremmo affermare questo algoritmo

10
00:00:29,800 --> 00:00:34,490
come segue, ripetere questo fino
Nessun elemento non ordinati rimangono.

11
00:00:34,490 --> 00:00:38,660
Ricerca tra il indifferenziati
i dati per trovare il più piccolo valore,

12
00:00:38,660 --> 00:00:44,130
poi scambiare il valore minimo con il
primo elemento della parte indifferenziati.

13
00:00:44,130 --> 00:00:47,130
>> Può essere utile visualizzare questo,
così diamo un'occhiata a questo.

14
00:00:47,130 --> 00:00:49,710
Quindi questo, io sostengo, è un
allineamento misti e ho

15
00:00:49,710 --> 00:00:53,040
indicato che indicando che tutti
gli elementi sono di colore rosso,

16
00:00:53,040 --> 00:00:54,420
essi non sono ancora ordinati.

17
00:00:54,420 --> 00:00:57,670
Questo è l'intero
parte indifferenziati della matrice.

18
00:00:57,670 --> 00:01:02,020
>> Quindi cerchiamo di passare attraverso le fasi di
selection sort per ordinare questo array.

19
00:01:02,020 --> 00:01:05,296
Così ancora una volta, stiamo andando ripetere
fino a quando non gli elementi non ordinati rimangono.

20
00:01:05,296 --> 00:01:07,920
Stiamo andando di ricerca attraverso il
i dati per trovare il più piccolo valore,

21
00:01:07,920 --> 00:01:11,990
e poi scambiare tale valore con il
primo elemento della parte indifferenziati.

22
00:01:11,990 --> 00:01:14,380
>> In questo momento, ancora una volta, l'intera
array è la parte non ordinata.

23
00:01:14,380 --> 00:01:16,534
Tutti gli elementi rossi sono indifferenziati.

24
00:01:16,534 --> 00:01:18,700
Così si cerca attraverso e
troviamo il valore più piccolo.

25
00:01:18,700 --> 00:01:20,533
Partiamo all'inizio,
andiamo fino alla fine,

26
00:01:20,533 --> 00:01:23,630
troviamo il valore più piccolo è, uno.

27
00:01:23,630 --> 00:01:24,860
Ecco, questo è parte uno.

28
00:01:24,860 --> 00:01:29,440
E poi la seconda parte, scambiare tale valore con
il primo elemento della parte indifferenziati,

29
00:01:29,440 --> 00:01:31,340
o il primo elemento rosso.

30
00:01:31,340 --> 00:01:34,980
>> In questo caso sarebbe
cinque, così abbiamo sostituire uno e cinque.

31
00:01:34,980 --> 00:01:37,320
Quando facciamo questo, possiamo
vediamo visivamente che abbiamo

32
00:01:37,320 --> 00:01:41,260
spostato l'elemento più piccolo valore
della matrice, per principio.

33
00:01:41,260 --> 00:01:43,920
Effettivamente l'ordinamento quell'elemento.

34
00:01:43,920 --> 00:01:47,520
>> E così possiamo davvero confermare
e affermano che uno, è ordinato.

35
00:01:47,520 --> 00:01:52,080
E così noi indichiamo la porzione ordinato
della nostra matrice, colorandola blu.

36
00:01:52,080 --> 00:01:53,860
>> Ora dobbiamo solo ripetere il processo.

37
00:01:53,860 --> 00:01:57,430
Cerchiamo attraverso la parte non ordinata di
la matrice di trovare l'elemento più piccolo.

38
00:01:57,430 --> 00:01:59,000
In questo caso, è due.

39
00:01:59,000 --> 00:02:02,100
>> Abbiamo swap con la prima
elemento della parte indifferenziati.

40
00:02:02,100 --> 00:02:05,540
In questo caso due avviene anche per essere
il primo elemento della parte indifferenziati.

41
00:02:05,540 --> 00:02:08,650
Quindi noi scambiamo due con se stesso,
che in realtà lascia solo due

42
00:02:08,650 --> 00:02:11,257
dove si trova, ed è ordinato.

43
00:02:11,257 --> 00:02:13,840
Proseguendo, si cerca attraverso
per trovare l'elemento più piccolo.

44
00:02:13,840 --> 00:02:15,030
Sono le tre.

45
00:02:15,030 --> 00:02:17,650
Ci scambiamo con il primo
elemento, che è cinque.

46
00:02:17,650 --> 00:02:19,450
E ora tre è ordinato.

47
00:02:19,450 --> 00:02:22,440
>> Cerchiamo attraverso di nuovo, e noi
trovare l'elemento più piccolo è di quattro.

48
00:02:22,440 --> 00:02:28,070
Noi scambiamo con il primo elemento della
parte indifferenziati, e ora quattro è ordinato.

49
00:02:28,070 --> 00:02:29,910
>> Troviamo che cinque è
l'elemento più piccolo.

50
00:02:29,910 --> 00:02:32,900
Ci scambiamo con il primo
elemento della parte indifferenziati.

51
00:02:32,900 --> 00:02:34,740
E ora cinque è ordinato.

52
00:02:34,740 --> 00:02:36,660
>> E poi, infine, il nostro
parte indifferenziati è costituito

53
00:02:36,660 --> 00:02:38,576
di un solo elemento,
così cerchiamo attraverso

54
00:02:38,576 --> 00:02:41,740
e troviamo che sei è il
più piccolo, e di fatto, unico elemento.

55
00:02:41,740 --> 00:02:44,906
E allora si può affermare che esso è ordinato.

56
00:02:44,906 --> 00:02:47,530
E ora abbiamo cambiato la nostra gamma
da essere completamente unsorted

57
00:02:47,530 --> 00:02:52,660
in rosso, a filtrate completamente
in blu, con ordinamento per selezione.

58
00:02:52,660 --> 00:02:54,920
>> Quindi qual è la peggiore delle ipotesi qui?

59
00:02:54,920 --> 00:02:57,830
Beh, nel peggiore in assoluto
caso, dobbiamo guardare oltre

60
00:02:57,830 --> 00:03:02,170
tutti gli elementi della matrice di
trovare il più piccolo elemento indifferenziati,

61
00:03:02,170 --> 00:03:04,750
e dobbiamo ripetere
questo processo n volte.

62
00:03:04,750 --> 00:03:09,090
Una volta per ogni elemento dell'array
perché solo in questo algoritmo,

63
00:03:09,090 --> 00:03:12,180
tipo un elemento alla volta.

64
00:03:12,180 --> 00:03:13,595
>> Qual è la migliore delle ipotesi?

65
00:03:13,595 --> 00:03:15,040
Beh, è ​​esattamente lo stesso, giusto?

66
00:03:15,040 --> 00:03:18,440
Noi in realtà fare un passo ancora attraverso
ogni singolo elemento dell'array

67
00:03:18,440 --> 00:03:22,040
al fine di confermare che si tratta,
infatti, l'elemento più piccolo.

68
00:03:22,040 --> 00:03:26,760
>> Così il runtime caso peggiore, abbiamo
ripetere un processo n volte,

69
00:03:26,760 --> 00:03:28,960
una volta per ogni di n elementi.

70
00:03:28,960 --> 00:03:31,940
E nella migliore delle ipotesi,
dobbiamo fare lo stesso.

71
00:03:31,940 --> 00:03:35,340
>> Quindi, ripensando al nostro
computazionale toolbox complessità,

72
00:03:35,340 --> 00:03:39,250
cosa ne pensi è la peggiore
caso di runtime per selezione tipo?

73
00:03:39,250 --> 00:03:41,840
Cosa ne pensi è la migliore
caso di runtime per selezione tipo?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Avete indovinato Big O di n al quadrato,
e Big Omega di n al quadrato?

76
00:03:49,325 --> 00:03:49,950
Avreste ragione.

77
00:03:49,950 --> 00:03:52,490
Quelli sono, infatti, la
caso peggiore e migliore corsa caso

78
00:03:52,490 --> 00:03:55,100
volte, per la selezione sorta.

79
00:03:55,100 --> 00:03:56,260
>> Sono Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Questo è CS50.

81
00:03:58,600 --> 00:04:00,279