1
00:00:00,000 --> 00:00:05,726
>> [MUSIC nagpe-play]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: sort Selection ay isang
algorithm na, bilang maaari mong asahan,

3
00:00:08,600 --> 00:00:10,470
masama ang isang hanay ng mga elemento.

4
00:00:10,470 --> 00:00:12,470
At algorithm recall
ay isang step-by-step na set

5
00:00:12,470 --> 00:00:15,260
ng mga tagubilin para sa pagkumpleto ng isang gawain.

6
00:00:15,260 --> 00:00:17,580
>> Sa pagpili ayusin ang
pangunahing ideya ay ito,

7
00:00:17,580 --> 00:00:22,080
hanapin ang pinakamaliit unsorted elemento at
idagdag ito sa dulo ng pinagsunod-sunod na listahan.

8
00:00:22,080 --> 00:00:26,970
Mabisa kung ano ang nagagawa nito ay build
isang pinagsunod-sunod na listahan, ang isang elemento sa isang pagkakataon.

9
00:00:26,970 --> 00:00:29,800
Paghiwa-hiwalayin ito down sa pseudocode
maaari naming estado algorithm na ito

10
00:00:29,800 --> 00:00:34,490
ang mga sumusunod, ulitin ito hanggang
mananatiling walang unsorted elemento.

11
00:00:34,490 --> 00:00:38,660
Maghanap sa pamamagitan ng unsorted
data upang mahanap ang pinakamaliit na halaga,

12
00:00:38,660 --> 00:00:44,130
pagkatapos ay palitan ang pinakamaliit na halaga sa
unang elemento ng unsorted bahagi.

13
00:00:44,130 --> 00:00:47,130
>> Ito ay maaaring makatulong upang maisalarawan ito,
kaya tumagal ng isang pagtingin sa ito ipaalam.

14
00:00:47,130 --> 00:00:49,710
Kaya ito, iginigiit ko, ay isang
unsorted array at na ako

15
00:00:49,710 --> 00:00:53,040
ipinahiwatig ito sa pamamagitan ng na nagpapahiwatig na ang lahat
ng mga elemento ay kulay pula,

16
00:00:53,040 --> 00:00:54,420
ang mga ito ay hindi pa nakaayos.

17
00:00:54,420 --> 00:00:57,670
Ito ang buong
unsorted bahagi ng array.

18
00:00:57,670 --> 00:01:02,020
>> Kaya sabihin pumunta sa pamamagitan ng mga hakbang ng
pagpili-uuri-uri-uriin ang array.

19
00:01:02,020 --> 00:01:05,296
Kaya muli, hindi namin gonna ulitin
hanggang mananatiling walang unsorted elemento.

20
00:01:05,296 --> 00:01:07,920
Humihingi kami ng gonna paghahanap sa pamamagitan ng
data upang mahanap ang pinakamaliit na halaga,

21
00:01:07,920 --> 00:01:11,990
at pagkatapos ay magpalitan na halaga sa mga
unang elemento ng unsorted bahagi.

22
00:01:11,990 --> 00:01:14,380
>> Sa ngayon, muli, ang buong
array ay ang unsorted bahagi.

23
00:01:14,380 --> 00:01:16,534
Ang lahat ng mga pulang mga elemento ay unsorted.

24
00:01:16,534 --> 00:01:18,700
Kaya kami sa paghahanap sa pamamagitan ng at
nakita namin na ang pinakamaliit na halaga.

25
00:01:18,700 --> 00:01:20,533
Simulan namin sa simula,
pumunta kami sa dulo,

26
00:01:20,533 --> 00:01:23,630
nakita namin na ang pinakamaliit na halaga ay, isa.

27
00:01:23,630 --> 00:01:24,860
Kaya na ang bahagi ng isa.

28
00:01:24,860 --> 00:01:29,440
At pagkatapos ay ang dalawang bahagi, magpalit na halaga sa
ang unang elemento ng unsorted bahagi,

29
00:01:29,440 --> 00:01:31,340
o ang unang red elemento.

30
00:01:31,340 --> 00:01:34,980
>> Sa kasong ito na magiging
limang, para magpalit kami ng isa at lima.

31
00:01:34,980 --> 00:01:37,320
Kapag ginagawa namin ito, maaari naming
biswal makita na hindi namin

32
00:01:37,320 --> 00:01:41,260
inilipat ang pinakamaliit na nagkakahalaga element
ng array, sa napaka-simula.

33
00:01:41,260 --> 00:01:43,920
Epektibong pag-uuri na sangkap.

34
00:01:43,920 --> 00:01:47,520
>> At upang maaari naming katunayan magkaibigan
at estado na ang isa, ay pinagsunod-sunod.

35
00:01:47,520 --> 00:01:52,080
At kaya makikita ipahiwatig namin ang pinagsunod-sunod na bahagi
ng aming array, sa pamamagitan ng pangkulay ito asul.

36
00:01:52,080 --> 00:01:53,860
>> Ngayon kami ulitin lamang ang proseso muli.

37
00:01:53,860 --> 00:01:57,430
Kami ng paghahanap sa pamamagitan ng unsorted bahagi ng
array upang mahanap ang pinakamaliit na elemento.

38
00:01:57,430 --> 00:01:59,000
Sa kasong ito, ito ay dalawa.

39
00:01:59,000 --> 00:02:02,100
>> Swap kami na sa unang
elemento ng unsorted bahagi.

40
00:02:02,100 --> 00:02:05,540
Sa kasong ito dalawang din ang mangyayari sa
ang unang elemento ng unsorted bahagi.

41
00:02:05,540 --> 00:02:08,650
So magpalit kami ng dalawang sa kanyang sarili,
na kung saan ay talagang lamang dahon ng dalawang

42
00:02:08,650 --> 00:02:11,257
kung saan ito, at ito ay nakaayos.

43
00:02:11,257 --> 00:02:13,840
Ang pagpapatuloy sa, aming paghahanap sa pamamagitan ng
upang mahanap ang pinakamaliit na elemento.

44
00:02:13,840 --> 00:02:15,030
Ito ay tatlong.

45
00:02:15,030 --> 00:02:17,650
Swap namin ito sa unang
elemento, na kung saan ay limang.

46
00:02:17,650 --> 00:02:19,450
At ngayon tatlong ay pinagsunod-sunod.

47
00:02:19,450 --> 00:02:22,440
>> Kami ng paghahanap sa pamamagitan ng muli, at kami
hanapin ang pinakamaliit na elemento ay apat.

48
00:02:22,440 --> 00:02:28,070
Swap namin ito sa unang elemento ng
unsorted bahagi, at ngayon ay may apat na pinagsunod-sunod.

49
00:02:28,070 --> 00:02:29,910
>> Nakita namin na limang ay
ang pinakamaliit na elemento.

50
00:02:29,910 --> 00:02:32,900
Swap namin ito sa unang
elemento ng unsorted bahagi.

51
00:02:32,900 --> 00:02:34,740
At ngayon limang ay pinagsunod-sunod.

52
00:02:34,740 --> 00:02:36,660
>> At pagkatapos ay sa wakas, ang aming
Binubuo unsorted bahagi

53
00:02:36,660 --> 00:02:38,576
na lamang ng isang solong elemento,
kaya kami sa paghahanap sa pamamagitan ng

54
00:02:38,576 --> 00:02:41,740
at nakita namin na anim ay ang
pinakamaliit, at sa katunayan, lamang ang element.

55
00:02:41,740 --> 00:02:44,906
At pagkatapos ay maaari naming estado na ito ay pinagsunod-sunod.

56
00:02:44,906 --> 00:02:47,530
At ngayon inililipat namin ang aming array
mula sa pagiging lubos unsorted

57
00:02:47,530 --> 00:02:52,660
sa pula, sa ganap na pinagsunod-sunod
sa asul, gamit pagpili-uuri.

58
00:02:52,660 --> 00:02:54,920
>> Kaya kung ano ang pinakamasama kaso sitwasyon dito?

59
00:02:54,920 --> 00:02:57,830
Well sa ganap na pinakamasama
kaso, mayroon kaming upang tumingin sa paglipas ng

60
00:02:57,830 --> 00:03:02,170
ang lahat ng elemento ng array na
hanapin ang pinakamaliit unsorted elemento,

61
00:03:02,170 --> 00:03:04,750
at kami ay may sa ulitin
ang proseso na ito n ulit.

62
00:03:04,750 --> 00:03:09,090
Kapag para sa bawat elemento ng array
dahil tayo lamang, sa algorithm na ito,

63
00:03:09,090 --> 00:03:12,180
sort ang isang elemento sa oras.

64
00:03:12,180 --> 00:03:13,595
>> Ano ang pinakamahusay na kaso sitwasyon?

65
00:03:13,595 --> 00:03:15,040
Well ito ay eksaktong pareho, di ba?

66
00:03:15,040 --> 00:03:18,440
Kami ay talagang may upang pa rin magbasa-basa sa
bawat isang elemento ng array

67
00:03:18,440 --> 00:03:22,040
upang kumpirmahin na ito ay,
sa katunayan, ang pinakamaliit na elemento.

68
00:03:22,040 --> 00:03:26,760
>> Kaya ang pinakamasama kaso runtime, namin
kailangang ulitin ang isang proseso n beses,

69
00:03:26,760 --> 00:03:28,960
isang beses para sa bawat isa n elemento.

70
00:03:28,960 --> 00:03:31,940
At sa pinakamahusay na kaso sitwasyon,
kami ay may sa gawin ang parehong.

71
00:03:31,940 --> 00:03:35,340
>> Kaya nag-iisip bumalik sa aming
computational kumplikado toolbox,

72
00:03:35,340 --> 00:03:39,250
ano sa tingin mo ay ang pinakamasama
kaso runtime para sa pagpili ng uri?

73
00:03:39,250 --> 00:03:41,840
Ano ang tingin mo ay ang pinakamahusay na
kaso runtime para sa pagpili ng uri?

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

75
00:03:44,760 --> 00:03:49,325
>> Hulaan mo ba Big O ng n squared,
at Big Omega ng n nakalapat?

76
00:03:49,325 --> 00:03:49,950
Gusto mong maging tama.

77
00:03:49,950 --> 00:03:52,490
Yaong mga, sa katunayan, ang
pinakamasama kaso at pinakamahusay na run case

78
00:03:52,490 --> 00:03:55,100
beses, para sa pagpili-uuri.

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

80
00:03:56,260 --> 00:03:58,600
Ito ay CS50.

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