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

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Seleção é uma espécie
algoritmo que, como você poderia esperar,

3
00:00:08,600 --> 00:00:10,470
Classifica um conjunto de elementos.

4
00:00:10,470 --> 00:00:12,470
E algoritmo recordação
é um conjunto passo-a-passo

5
00:00:12,470 --> 00:00:15,260
de instruções para completar uma tarefa.

6
00:00:15,260 --> 00:00:17,580
>> Na seleção classificar a
idéia básica é esta:

7
00:00:17,580 --> 00:00:22,080
encontrar o menor elemento não triados e
adicioná-lo para o fim da lista ordenada.

8
00:00:22,080 --> 00:00:26,970
Efetivamente o que isso faz é construir
uma lista classificada, um elemento de cada vez.

9
00:00:26,970 --> 00:00:29,800
Quebrá-lo para baixo para pseudocódigo
podemos afirmar este algoritmo

10
00:00:29,800 --> 00:00:34,490
como se segue, repita isso até
não há elementos não ordenados permanecem.

11
00:00:34,490 --> 00:00:38,660
Pesquisa através da indiferenciados
dados para encontrar o menor valor,

12
00:00:38,660 --> 00:00:44,130
em seguida, trocar o menor valor com o
primeiro elemento da parte indiferenciados.

13
00:00:44,130 --> 00:00:47,130
>> Ela pode ajudar a visualizar isto,
por isso vamos dar uma olhada nisso.

14
00:00:47,130 --> 00:00:49,710
Então isso, eu afirmo, é uma
matriz não triados e eu tenho

15
00:00:49,710 --> 00:00:53,040
indicou que, indicando que todos
dos elementos são de cor vermelha,

16
00:00:53,040 --> 00:00:54,420
eles ainda não são classificadas.

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

18
00:00:57,670 --> 00:01:02,020
>> Então, vamos percorrer as etapas de
seleção classificação para classificar essa matriz.

19
00:01:02,020 --> 00:01:05,296
Então, novamente, nós vamos repeat
até que não haja elementos não ordenados permanecem.

20
00:01:05,296 --> 00:01:07,920
Nós vamos pesquisa através da
dados para encontrar o menor valor,

21
00:01:07,920 --> 00:01:11,990
e depois trocar esse valor com o
primeiro elemento da parte indiferenciados.

22
00:01:11,990 --> 00:01:14,380
>> Agora, mais uma vez, a toda
matriz é a parte indiferenciados.

23
00:01:14,380 --> 00:01:16,534
Todos os elementos vermelhos são indiferenciados.

24
00:01:16,534 --> 00:01:18,700
Por isso, pesquisar e
encontramos o menor valor.

25
00:01:18,700 --> 00:01:20,533
Começamos no início,
nós vamos até o fim,

26
00:01:20,533 --> 00:01:23,630
encontramos o menor valor é, um.

27
00:01:23,630 --> 00:01:24,860
Então essa é uma parte.

28
00:01:24,860 --> 00:01:29,440
E, em seguida, a parte dois, trocar esse valor com
o primeiro elemento da parte não classificado,

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

30
00:01:31,340 --> 00:01:34,980
>> Neste caso que seria
cinco, portanto, trocar um e cinco.

31
00:01:34,980 --> 00:01:37,320
Quando fazemos isso, nós podemos
visualmente ver que nós temos

32
00:01:37,320 --> 00:01:41,260
moveu o elemento mais pequeno valorizado
da matriz, para o início.

33
00:01:41,260 --> 00:01:43,920
Efectivamente triagem esse elemento.

34
00:01:43,920 --> 00:01:47,520
>> E assim podemos efectivamente confirmar
e afirmam que um, está classificada.

35
00:01:47,520 --> 00:01:52,080
E assim vamos indicar a porção classificada
de nossa matriz, colorindo o azul.

36
00:01:52,080 --> 00:01:53,860
>> Agora é só repetir o processo novamente.

37
00:01:53,860 --> 00:01:57,430
Procuramos através da parte não triados de
a matriz para encontrar o elemento mais pequeno.

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

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

40
00:02:02,100 --> 00:02:05,540
Neste caso, dois também acontece a ser
o primeiro elemento da parte indiferenciados.

41
00:02:05,540 --> 00:02:08,650
Então nós trocamos dois com si mesmo,
o que realmente deixa apenas dois

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

43
00:02:11,257 --> 00:02:13,840
Continuando, nós pesquisar
para encontrar o elemento mais pequeno.

44
00:02:13,840 --> 00:02:15,030
É três.

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

46
00:02:17,650 --> 00:02:19,450
E agora três está classificada.

47
00:02:19,450 --> 00:02:22,440
>> Nós pesquisa através de novo, e nós
encontrar o menor elemento é quatro.

48
00:02:22,440 --> 00:02:28,070
Nós trocá-lo com o primeiro elemento da
parte não triados, e agora quatro está classificada.

49
00:02:28,070 --> 00:02:29,910
>> Nós achamos que é cinco
o elemento mais pequeno.

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

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

52
00:02:34,740 --> 00:02:36,660
>> E então, finalmente, o nosso
parte consiste não triados

53
00:02:36,660 --> 00:02:38,576
de apenas um único elemento,
por isso, pesquisar

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

55
00:02:41,740 --> 00:02:44,906
E então podemos afirmar que ele é classificado.

56
00:02:44,906 --> 00:02:47,530
E agora mudamos nossa matriz
de ser completamente não separados

57
00:02:47,530 --> 00:02:52,660
em vermelho, completamente classificadas
em azul, usando a seleção de classificação.

58
00:02:52,660 --> 00:02:54,920
>> Então, qual é o pior cenário aqui?

59
00:02:54,920 --> 00:02:57,830
Bem no pior absoluta
caso, temos que olhar por cima

60
00:02:57,830 --> 00:03:02,170
todos os elementos da matriz para
encontrar o menor elemento não classificado,

61
00:03:02,170 --> 00:03:04,750
e nós temos que repetir
este processo n vezes.

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

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

64
00:03:12,180 --> 00:03:13,595
>> Qual é o melhor cenário?

65
00:03:13,595 --> 00:03:15,040
Bem, é exatamente o mesmo, certo?

66
00:03:15,040 --> 00:03:18,440
Na verdade, temos de continuar a percorrer
cada elemento da matriz

67
00:03:18,440 --> 00:03:22,040
a fim de confirmar que é,
Na verdade, o elemento mais pequeno.

68
00:03:22,040 --> 00:03:26,760
>> Então, o pior caso de tempo de execução, que
tem que repetir um processo n vezes,

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

70
00:03:28,960 --> 00:03:31,940
E na melhor das hipóteses,
nós temos que fazer o mesmo.

71
00:03:31,940 --> 00:03:35,340
>> Então, pensando de volta ao nosso
toolbox complexidade computacional,

72
00:03:35,340 --> 00:03:39,250
o que você acha que é o pior
caso de tempo de execução para a seleção tipo?

73
00:03:39,250 --> 00:03:41,840
O que você acha que é o melhor
caso de tempo de execução para a seleção tipo?

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

75
00:03:44,760 --> 00:03:49,325
>> Será que você adivinha Big O de n ao quadrado,
e Big Omega de n ao quadrado?

76
00:03:49,325 --> 00:03:49,950
Você estaria certo.

77
00:03:49,950 --> 00:03:52,490
Estes são, na verdade, o
pior caso e melhor caso de execução

78
00:03:52,490 --> 00:03:55,100
vezes, para seleção de tipo.

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

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

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