1
00:00:00,000 --> 00:00:05,726
>> [REPRODUCCIÓ DE MÚSICA]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Selecció tipus és un
algoritme que, com era d'esperar,

3
00:00:08,600 --> 00:00:10,470
ordena un conjunt d'elements.

4
00:00:10,470 --> 00:00:12,470
I algoritme de recuperació
és un conjunt pas a pas

5
00:00:12,470 --> 00:00:15,260
d'instruccions per completar una tasca.

6
00:00:15,260 --> 00:00:17,580
>> En la selecció ordenar la
idea bàsica és la següent,

7
00:00:17,580 --> 00:00:22,080
trobar l'element més petit i sense classificar
afegir al final de la llista ordenada.

8
00:00:22,080 --> 00:00:26,970
Efectivament el que això fa és construir
una llista ordenada, un element a la vegada.

9
00:00:26,970 --> 00:00:29,800
Trencant amb què pseudocodi
podríem afirmar que aquest algorisme

10
00:00:29,800 --> 00:00:34,490
la següent, repetir això fins
sense elements no classificats romanen.

11
00:00:34,490 --> 00:00:38,660
Feu una recerca entre els no seleccionats
dades per trobar el valor més petit,

12
00:00:38,660 --> 00:00:44,130
a continuació, canviar el valor més petit amb el
primer element de la part sense classificar.

13
00:00:44,130 --> 00:00:47,130
>> Es pot ajudar a visualitzar això,
així que anem a fer una ullada a això.

14
00:00:47,130 --> 00:00:49,710
Així que això, sostinc, és una
array sense classificar i tinc

15
00:00:49,710 --> 00:00:53,040
s'indica mitjançant la indicació que tots
dels elements són de color vermell,

16
00:00:53,040 --> 00:00:54,420
que encara no estan ordenats.

17
00:00:54,420 --> 00:00:57,670
Aquest és el sencer
part no seleccionada de la matriu.

18
00:00:57,670 --> 00:01:02,020
>> Així que anem a anar a través dels passos de
ordenació per selecció per ordenar aquesta matriu.

19
00:01:02,020 --> 00:01:05,296
Així que de nou, repetirem
fins que no romanen sense classificar elements.

20
00:01:05,296 --> 00:01:07,920
Buscarem a través de la
dades per trobar el valor més petit,

21
00:01:07,920 --> 00:01:11,990
i després canviar aquest valor amb el
primer element de la part sense classificar.

22
00:01:11,990 --> 00:01:14,380
>> Ara, de nou, tot el
matriu és la part sense classificar.

23
00:01:14,380 --> 00:01:16,534
Tots els elements són de color vermell sense classificar.

24
00:01:16,534 --> 00:01:18,700
Així que busquem a través i
ens trobem amb el valor més petit.

25
00:01:18,700 --> 00:01:20,533
Comencem pel principi,
anem fins al final,

26
00:01:20,533 --> 00:01:23,630
ens trobem amb el valor més petit és, un.

27
00:01:23,630 --> 00:01:24,860
Així que aquesta és la primera part.

28
00:01:24,860 --> 00:01:29,440
I després la segona part, intercanviar aquest valor amb
el primer element de la part sense classificar,

29
00:01:29,440 --> 00:01:31,340
o el primer element de vermell.

30
00:01:31,340 --> 00:01:34,980
>> En aquest cas que seria
cinc, així que intercanviem 01:05.

31
00:01:34,980 --> 00:01:37,320
Quan fem això, podem
veiem visualment que hem

32
00:01:37,320 --> 00:01:41,260
mogut l'element valorat més petit
de la matriu, al principi.

33
00:01:41,260 --> 00:01:43,920
Efectivament classificació d'aquest element.

34
00:01:43,920 --> 00:01:47,520
>> I pel que podem confirmar de fet
i l'estat que un, es classifica.

35
00:01:47,520 --> 00:01:52,080
I el que anem a indicar la part ordenats
de la nostra matriu, pintant de blau.

36
00:01:52,080 --> 00:01:53,860
>> Ara només repetim el procés de nou.

37
00:01:53,860 --> 00:01:57,430
Busquem a través de la part no seleccionada de
la matriu per trobar l'element més petit.

38
00:01:57,430 --> 00:01:59,000
En aquest cas, és dues.

39
00:01:59,000 --> 00:02:02,100
>> Intercanviem que amb la primera
element de la part sense classificar.

40
00:02:02,100 --> 00:02:05,540
En aquest cas dos també passa a ser
el primer element de la part sense classificar.

41
00:02:05,540 --> 00:02:08,650
Així que intercanviem 2 amb si mateix,
que en realitat només deixa 02:00

42
00:02:08,650 --> 00:02:11,257
on està, i està ordenada.

43
00:02:11,257 --> 00:02:13,840
Continuant, busquem a través
per trobar l'element més petit.

44
00:02:13,840 --> 00:02:15,030
Són les tres.

45
00:02:15,030 --> 00:02:17,650
Intercanviem amb el primer
element, que és cinc.

46
00:02:17,650 --> 00:02:19,450
I ara tres està ordenat.

47
00:02:19,450 --> 00:02:22,440
>> Busquem a través de nou, i ens
trobar l'element més petit és de quatre.

48
00:02:22,440 --> 00:02:28,070
Intercanviem amb el primer element de la
part sense classificar, i ara 4 es va solucionar.

49
00:02:28,070 --> 00:02:29,910
>> Trobem que 5 és
l'element més petit.

50
00:02:29,910 --> 00:02:32,900
Intercanviem amb el primer
element de la part sense classificar.

51
00:02:32,900 --> 00:02:34,740
I ara de cinc s'ordena.

52
00:02:34,740 --> 00:02:36,660
>> I després, finalment, la nostra
part sense classificar consisteix

53
00:02:36,660 --> 00:02:38,576
d'un sol element,
així de buscar a través de

54
00:02:38,576 --> 00:02:41,740
i ens trobem amb què sis és el
més petit, i de fet, únic element.

55
00:02:41,740 --> 00:02:44,906
I llavors podem afirmar que s'ordena.

56
00:02:44,906 --> 00:02:47,530
I ara hem canviat la nostra gamma
de ser completament sense classificar

57
00:02:47,530 --> 00:02:52,660
en vermell, que ordenats per complet
en blau, mitjançant la selecció de classificació.

58
00:02:52,660 --> 00:02:54,920
>> Quin és el pitjor dels casos aquí?

59
00:02:54,920 --> 00:02:57,830
Bé, en el pitjor
cas, hem de mirar per sobre de

60
00:02:57,830 --> 00:03:02,170
tots els elements de la matriu a
trobar l'element més petit sense classificar,

61
00:03:02,170 --> 00:03:04,750
i hem de repetir
aquest procés n vegades.

62
00:03:04,750 --> 00:03:09,090
Un cop per cada element de la matriu
perquè només en aquest algoritme,

63
00:03:09,090 --> 00:03:12,180
ordenar un element a la vegada.

64
00:03:12,180 --> 00:03:13,595
>> Quin és el millor dels casos?

65
00:03:13,595 --> 00:03:15,040
Bé, és exactament el mateix, no?

66
00:03:15,040 --> 00:03:18,440
De fet, tenim que segueixen pas a pas
cada element de la matriu

67
00:03:18,440 --> 00:03:22,040
per tal de confirmar que es tracta,
de fet, l'element més petit.

68
00:03:22,040 --> 00:03:26,760
>> Així el pitjor temps d'execució cas,
haver de repetir un procés n vegades,

69
00:03:26,760 --> 00:03:28,960
una vegada per a cada un de n elements.

70
00:03:28,960 --> 00:03:31,940
I en el millor dels casos,
hem de fer el mateix.

71
00:03:31,940 --> 00:03:35,340
>> Així que pensant en tornar a la nostra
caixa d'eines de la complexitat computacional,

72
00:03:35,340 --> 00:03:39,250
¿Què creus que és el pitjor
runtime cas per a la selecció d'una espècie?

73
00:03:39,250 --> 00:03:41,840
Què creus que és el millor
runtime cas per a la selecció d'una espècie?

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

75
00:03:44,760 --> 00:03:49,325
>> Sabia vostè endevina O gran de n al quadrat,
i Big Omega de n al quadrat?

76
00:03:49,325 --> 00:03:49,950
Vostè tindria raó.

77
00:03:49,950 --> 00:03:52,490
Aquells són, de fet, la
pitjor dels casos i la millor ratxa cas

78
00:03:52,490 --> 00:03:55,100
vegades, per a la selecció d'espècie.

79
00:03:55,100 --> 00:03:56,260
>> Sóc Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Això és CS50.

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