1
00:00:00,000 --> 00:00:05,726
>> [Música tocando]

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD: Selección é unha especie
algoritmo que, como podería esperar,

3
00:00:08,600 --> 00:00:10,470
Clasifica un conxunto de elementos.

4
00:00:10,470 --> 00:00:12,470
E algoritmo recordo
é un conxunto paso a paso

5
00:00:12,470 --> 00:00:15,260
de instrucións para completar unha tarefa.

6
00:00:15,260 --> 00:00:17,580
>> Na selección clasificar a
idea básica é esta:

7
00:00:17,580 --> 00:00:22,080
atopar o menor elemento sen clasificar e
engadir lo ao final da lista ordenada.

8
00:00:22,080 --> 00:00:26,970
Efectivamente o que iso fai é construír
unha lista clasificada, un elemento de cada vez.

9
00:00:26,970 --> 00:00:29,800
Rompe-lo para abaixo para pseudocódigo
podemos afirmar este algoritmo

10
00:00:29,800 --> 00:00:34,490
deste xeito, repita iso ata
non hai elementos non ordenados permanecen.

11
00:00:34,490 --> 00:00:38,660
Busca a través da indiferenciados
datos para atopar o menor valor,

12
00:00:38,660 --> 00:00:44,130
a continuación, cambiar o menor valor co
primeiro elemento da parte indiferenciados.

13
00:00:44,130 --> 00:00:47,130
>> Ela pode axudar a ver isto,
así que imos dar un ollo niso.

14
00:00:47,130 --> 00:00:49,710
Entón iso, eu afirmo, é unha
matriz sen clasificar e eu teño

15
00:00:49,710 --> 00:00:53,040
indicou que, indicando que todo
dos elementos son de cor vermella,

16
00:00:53,040 --> 00:00:54,420
eles non son clasificadas.

17
00:00:54,420 --> 00:00:57,670
Este é o enteiro
indiferenciados parte da matriz.

18
00:00:57,670 --> 00:01:02,020
>> Entón, imos percorrer os pasos de
selección clasificación para clasificar esta matriz.

19
00:01:02,020 --> 00:01:05,296
Entón, de novo, nós imos repeat
ata que non haxa elementos non ordenados permanecen.

20
00:01:05,296 --> 00:01:07,920
Nós imos busca a través da
datos para atopar o menor valor,

21
00:01:07,920 --> 00:01:11,990
e despois cambiar ese valor co
primeiro elemento da parte indiferenciados.

22
00:01:11,990 --> 00:01:14,380
>> Agora, unha vez máis, a toda
matriz é a parte indiferenciados.

23
00:01:14,380 --> 00:01:16,534
Todos os elementos vermellos son indiferenciados.

24
00:01:16,534 --> 00:01:18,700
Por iso, buscar e
atopamos o menor valor.

25
00:01:18,700 --> 00:01:20,533
Comezamos en principio,
nós imos ata o final,

26
00:01:20,533 --> 00:01:23,630
atopamos o menor valor, un.

27
00:01:23,630 --> 00:01:24,860
Entón esta é unha parte.

28
00:01:24,860 --> 00:01:29,440
E, a continuación, a parte dous, intercambiar ese valor con
o primeiro elemento da parte non clasificado,

29
00:01:29,440 --> 00:01:31,340
ou o primeiro elemento vermello.

30
00:01:31,340 --> 00:01:34,980
>> Neste caso que sería
cinco, polo tanto, cambiar un e cinco.

31
00:01:34,980 --> 00:01:37,320
Cando facemos iso, podemos
visualmente ver que temos

32
00:01:37,320 --> 00:01:41,260
moveu o elemento máis pequeno valorado
da matriz, para o inicio.

33
00:01:41,260 --> 00:01:43,920
En efecto selección ese elemento.

34
00:01:43,920 --> 00:01:47,520
>> E así podemos efectivamente confirmar
e afirman que un, está clasificada.

35
00:01:47,520 --> 00:01:52,080
E así imos indicar a porción clasificada
da nosa matriz, colorido o azul.

36
00:01:52,080 --> 00:01:53,860
>> Agora é só repetir o proceso de novo.

37
00:01:53,860 --> 00:01:57,430
Buscamos a través da parte sen clasificar de
a matriz para atopar o elemento máis pequeno.

38
00:01:57,430 --> 00:01:59,000
Neste caso, é dous.

39
00:01:59,000 --> 00:02:02,100
>> Nós que cambiar coa primeira
elemento da parte indiferenciados.

40
00:02:02,100 --> 00:02:05,540
Neste caso, dous tamén pasa a ser
o primeiro elemento da parte indiferenciados.

41
00:02:05,540 --> 00:02:08,650
Entón nós trocamos dous con si mesmo,
o que realmente deixa só dous

42
00:02:08,650 --> 00:02:11,257
onde está, e está clasificado.

43
00:02:11,257 --> 00:02:13,840
Continuando, nós buscar
para atopar o elemento máis pequeno.

44
00:02:13,840 --> 00:02:15,030
É tres.

45
00:02:15,030 --> 00:02:17,650
Nós troca-lo o primeiro
elemento, que é de cinco.

46
00:02:17,650 --> 00:02:19,450
E agora tres está clasificada.

47
00:02:19,450 --> 00:02:22,440
>> Nós investigación a través de novo, e nós
atopar o menor elemento é catro.

48
00:02:22,440 --> 00:02:28,070
Nós troca-lo o primeiro elemento da
parte sen clasificar, e agora catro está clasificada.

49
00:02:28,070 --> 00:02:29,910
>> Nós cremos que é cinco
o elemento máis pequeno.

50
00:02:29,910 --> 00:02:32,900
Nós troca-lo o primeiro
elemento da parte indiferenciados.

51
00:02:32,900 --> 00:02:34,740
E agora cinco está clasificada.

52
00:02:34,740 --> 00:02:36,660
>> E entón, finalmente, o noso
parte consiste sen clasificar

53
00:02:36,660 --> 00:02:38,576
de só un único elemento,
por iso, buscar

54
00:02:38,576 --> 00:02:41,740
e nós cremos que seis é o
menor, e de feito, único elemento.

55
00:02:41,740 --> 00:02:44,906
E entón podemos afirmar que é clasificado.

56
00:02:44,906 --> 00:02:47,530
E agora cambiamos nosa matriz
de ser completamente non separados

57
00:02:47,530 --> 00:02:52,660
en vermello, completamente clasificadas
en azul, a través da selección de clasificación.

58
00:02:52,660 --> 00:02:54,920
>> Entón, cal é o peor escenario aquí?

59
00:02:54,920 --> 00:02:57,830
Ben no peor absoluta
caso, temos que mirar por riba

60
00:02:57,830 --> 00:03:02,170
todos os elementos da matriz para
atopar o menor elemento non clasificado,

61
00:03:02,170 --> 00:03:04,750
e temos que repetir
este proceso n veces.

62
00:03:04,750 --> 00:03:09,090
Xa que para cada elemento do array
porque só neste algoritmo,

63
00:03:09,090 --> 00:03:12,180
tipo un elemento de cada vez.

64
00:03:12,180 --> 00:03:13,595
>> Cal é o mellor escenario?

65
00:03:13,595 --> 00:03:15,040
Ben, é exactamente o mesmo, non?

66
00:03:15,040 --> 00:03:18,440
En realidade, hai que seguir a percorrer
cada elemento da matriz

67
00:03:18,440 --> 00:03:22,040
a fin de confirmar que é,
En realidade, o elemento máis pequeno.

68
00:03:22,040 --> 00:03:26,760
>> Entón, o peor caso de tempo de execución, que
ten que repetir un proceso n veces,

69
00:03:26,760 --> 00:03:28,960
unha vez para cada un dos n elementos.

70
00:03:28,960 --> 00:03:31,940
E no mellor dos casos,
temos que facer o mesmo.

71
00:03:31,940 --> 00:03:35,340
>> Entón, pensando de volta ao noso
Toolbox complexidade computacional,

72
00:03:35,340 --> 00:03:39,250
o que pensas que é o peor
caso de tempo de execución para a selección tipo?

73
00:03:39,250 --> 00:03:41,840
¿Que pensas que é o mellor
caso de tempo de execución para a selección tipo?

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

75
00:03:44,760 --> 00:03:49,325
>> Será que adiviña Big O n ao cadrado,
e Big Omega n ao cadrado?

76
00:03:49,325 --> 00:03:49,950
Estaría ben.

77
00:03:49,950 --> 00:03:52,490
Estes son, en realidade, o
peor caso e mellor caso de execución

78
00:03:52,490 --> 00:03:55,100
veces, para a selección de tipo.

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

80
00:03:56,260 --> 00:03:58,600
Este é CS50.

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