1
00:00:00,000 --> 00:00:05,726
>> [MIZIK jwe]

2
00:00:05,726 --> 00:00:08,600
Doug Lloyd: Seleksyon sòt se yon
algorithm ki, menm jan ou ta ka atann,

3
00:00:08,600 --> 00:00:10,470
asòti yon seri eleman.

4
00:00:10,470 --> 00:00:12,470
Epi sonje algorithm
se yon seri etap-pa-etap

5
00:00:12,470 --> 00:00:15,260
nan enstriksyon pou ranpli yon travay.

6
00:00:15,260 --> 00:00:17,580
>> Nan seleksyon sòt nan
lide debaz se sa a,

7
00:00:17,580 --> 00:00:22,080
jwenn pi piti eleman ki klase ak
ajoute li nan fen a nan lis la Ranje.

8
00:00:22,080 --> 00:00:26,970
Efektivman ki sa sa a fè se bati
yon lis Ranje, yon sèl eleman nan yon tan.

9
00:00:26,970 --> 00:00:29,800
Breaking li desann nan pseudocode
nou te ka deklare sa a algorithm

10
00:00:29,800 --> 00:00:34,490
jan sa a, repete sa a jouk
pa gen okenn eleman triye rete.

11
00:00:34,490 --> 00:00:38,660
Search nan triye nan
done sa yo jwenn valè a pi piti a,

12
00:00:38,660 --> 00:00:44,130
Lè sa a, swap valè ki pi piti a ak nan
premye eleman nan pati ki klase.

13
00:00:44,130 --> 00:00:47,130
>> Li ka ede yo visualized sa a,
kidonk kite a pran yon gade nan sa a.

14
00:00:47,130 --> 00:00:49,710
Se konsa, sa a, mwen plede, se yon
etalaj triye ak mwen te

15
00:00:49,710 --> 00:00:53,040
endike li pa endike ke tout
nan eleman yo ki gen koulè pal yo wouj,

16
00:00:53,040 --> 00:00:54,420
yo pa yo ankò Ranje.

17
00:00:54,420 --> 00:00:57,670
Sa a se tout antye nan
triye yon pati nan etalaj la.

18
00:00:57,670 --> 00:01:02,020
>> Se konsa nou ale nan etap sa yo nan
sòt seleksyon sòt etalaj sa a.

19
00:01:02,020 --> 00:01:05,296
Se konsa, ankò, nou ap pral repete
jiskaske pa gen okenn eleman triye rete.

20
00:01:05,296 --> 00:01:07,920
Nou pral rechèch nan la
done sa yo jwenn valè a pi piti a,

21
00:01:07,920 --> 00:01:11,990
ak Lè sa a swap ke valè ak nan
premye eleman nan pati ki klase.

22
00:01:11,990 --> 00:01:14,380
>> Dwa koulye a, ankò, tout la
etalaj se yon pati ki klase.

23
00:01:14,380 --> 00:01:16,534
Tout nan eleman yo wouj yo triye.

24
00:01:16,534 --> 00:01:18,700
Se konsa, nou rechèch nan ak
nou jwenn valè ki pi piti a.

25
00:01:18,700 --> 00:01:20,533
Nou kòmanse nan kòmansman an,
nou ale nan fen a,

26
00:01:20,533 --> 00:01:23,630
nou jwenn valè ki pi piti a se, yon sèl.

27
00:01:23,630 --> 00:01:24,860
Se konsa, sa a, se yon pati yon sèl.

28
00:01:24,860 --> 00:01:29,440
Lè sa a, yon pati de, swap ke valè ak
eleman an premye nan pati a klase,

29
00:01:29,440 --> 00:01:31,340
oswa premye eleman nan wouj.

30
00:01:31,340 --> 00:01:34,980
>> Nan ka sa a ki ta ka
senk, se konsa nou boukante yon sèl ak senk.

31
00:01:34,980 --> 00:01:37,320
Lè nou fè sa, nou kapab
vizyèlman wè ke nou te

32
00:01:37,320 --> 00:01:41,260
deplase pi piti eleman nan valè
nan etalaj la, nan konmansman an anpil.

33
00:01:41,260 --> 00:01:43,920
Efektivman klasman ki eleman.

34
00:01:43,920 --> 00:01:47,520
>> Se konsa, nou ka tout bon konfime
ak eta ke yon moun, se Ranje.

35
00:01:47,520 --> 00:01:52,080
Se konsa, nou pral endike pòsyon nan Ranje
nan etalaj nou an, pa koloran li ble.

36
00:01:52,080 --> 00:01:53,860
>> Koulye a, nou jis repete pwosesis la ankò.

37
00:01:53,860 --> 00:01:57,430
Nou rechèch nan pati ki klase nan
etalaj la jwenn eleman ki pi piti a.

38
00:01:57,430 --> 00:01:59,000
Nan ka sa a, li nan de.

39
00:01:59,000 --> 00:02:02,100
>> Nou swap ke ak premye a
eleman nan pati ki klase.

40
00:02:02,100 --> 00:02:05,540
Nan ka sa a de tou k ap pase yo dwe
eleman an premye nan pati ki klase.

41
00:02:05,540 --> 00:02:08,650
Se konsa, nou swap de ak tèt li,
ki reyèlman jis kite de

42
00:02:08,650 --> 00:02:11,257
kote li se, ak sa yo Ranje.

43
00:02:11,257 --> 00:02:13,840
Kontinye sou li a, nou rechèch nan
jwenn eleman ki pi piti a.

44
00:02:13,840 --> 00:02:15,030
Li nan twa.

45
00:02:15,030 --> 00:02:17,650
Nou swap l 'ak premye a
eleman, ki se senk.

46
00:02:17,650 --> 00:02:19,450
Epi, koulye a twa se Klase.

47
00:02:19,450 --> 00:02:22,440
>> Nou rechèch nan ankò, epi nou
jwenn eleman ki pi piti a se kat.

48
00:02:22,440 --> 00:02:28,070
Nou swap l 'ak eleman an premye nan nan
triye pati, e kounye a, kat se Klase.

49
00:02:28,070 --> 00:02:29,910
>> Nou jwenn ke senk se
eleman nan pi piti a.

50
00:02:29,910 --> 00:02:32,900
Nou swap l 'ak premye a
eleman nan pati ki klase.

51
00:02:32,900 --> 00:02:34,740
Epi, koulye a senk se Klase.

52
00:02:34,740 --> 00:02:36,660
>> Lè sa a, anfen, nou an
triye pati konsiste

53
00:02:36,660 --> 00:02:38,576
nan jis yon eleman sèl,
se konsa nou rechèch nan

54
00:02:38,576 --> 00:02:41,740
epi nou jwenn ke sis se nan
pi piti a, ak nan reyalite, se sèlman eleman.

55
00:02:41,740 --> 00:02:44,906
Lè sa a, nou ka deklare ke li se Klase.

56
00:02:44,906 --> 00:02:47,530
Epi, koulye a nou te chanje etalaj nou an
nan men yo te konplètman triye

57
00:02:47,530 --> 00:02:52,660
nan wouj, konplètman Ranje
nan ble, lè l sèvi avèk sòt seleksyon.

58
00:02:52,660 --> 00:02:54,920
>> Se konsa, sa ki nan senaryo a ka pi move isit la?

59
00:02:54,920 --> 00:02:57,830
Byen nan pi move a absoli
ka, nou dwe gade sou

60
00:02:57,830 --> 00:03:02,170
tout nan eleman yo nan etalaj la yo
jwenn pi piti eleman nan klase,

61
00:03:02,170 --> 00:03:04,750
e nou gen yo repete
pwosesis N fwa sa a.

62
00:03:04,750 --> 00:03:09,090
Yon fwa pou chak eleman nan etalaj la
paske nou sèlman, nan sa a algorithm,

63
00:03:09,090 --> 00:03:12,180
sòt yon sèl eleman nan tan.

64
00:03:12,180 --> 00:03:13,595
>> Ki sa ki nan senaryo a ka pi bon?

65
00:03:13,595 --> 00:03:15,040
Oke li nan ekzakteman menm bagay la, dwa?

66
00:03:15,040 --> 00:03:18,440
Nou gen aktyèlman toujou etap nan
chak eleman sèl nan etalaj la

67
00:03:18,440 --> 00:03:22,040
yo nan lòd yo konfime ke li se,
an reyalite, eleman ki pi piti a.

68
00:03:22,040 --> 00:03:26,760
>> Se konsa, ègzekutabl a ka pi mal, nou
gen repete yon pwosesis N fwa,

69
00:03:26,760 --> 00:03:28,960
yon fwa pou chak nan eleman n.

70
00:03:28,960 --> 00:03:31,940
Ak nan senaryo a ka pi bon,
nou dwe fè menm bagay la.

71
00:03:31,940 --> 00:03:35,340
>> Se konsa, panse tounen nan nou an
enfòmatik bwat zouti konpleksite,

72
00:03:35,340 --> 00:03:39,250
ki sa ou panse se pi move a
ègzekutabl ka pou sòt seleksyon?

73
00:03:39,250 --> 00:03:41,840
Ki sa ou panse ki pi bon an
ègzekutabl ka pou sòt seleksyon?

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

75
00:03:44,760 --> 00:03:49,325
>> Èske w te devine Big O nan n okib,
ak Big Omega nan n okib?

76
00:03:49,325 --> 00:03:49,950
Ou ta dwe gen dwa.

77
00:03:49,950 --> 00:03:52,490
Moun sa yo se, an reyalite, nan
pi move ka ak pi bon ka kouri

78
00:03:52,490 --> 00:03:55,100
fwa, pou sòt seleksyon.

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

80
00:03:56,260 --> 00:03:58,600
Sa a se CS50.

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