1
00:00:00,000 --> 00:00:05,726
>> [Muzika]

2
00:00:05,726 --> 00:00:08,600
DOUG Lloyd: Përzgjedhja lloj është një
algorithm që, si ju mund të presin,

3
00:00:08,600 --> 00:00:10,470
klasifikon një grup elementesh.

4
00:00:10,470 --> 00:00:12,470
Dhe algorithm risjell
është një grup hap-pas-hapi

5
00:00:12,470 --> 00:00:15,260
Udhëzimet për plotësimin e një detyre.

6
00:00:15,260 --> 00:00:17,580
>> Në përzgjedhjen lloj
Ideja themelore është kjo,

7
00:00:17,580 --> 00:00:22,080
gjeni elementin më të vogël Unsorted dhe
shtoni atë në fund të listës renditura.

8
00:00:22,080 --> 00:00:26,970
Efektivisht Çfarë kjo nuk është ndërtuar
një listë të renditura, një element në një kohë.

9
00:00:26,970 --> 00:00:29,800
Thyer atë poshtë për pseudokod
ne mund të deklarojë këtë algorithm

10
00:00:29,800 --> 00:00:34,490
si më poshtë, të përsëritur këtë deri
ka elemente Unsorted mbeten.

11
00:00:34,490 --> 00:00:38,660
Kërko përmes Unsorted
të dhënat për të gjetur vlerën më të vogël,

12
00:00:38,660 --> 00:00:44,130
pastaj të bie në ujdi vlerën më të vogël me
elementi i parë i pjesës pandara.

13
00:00:44,130 --> 00:00:47,130
>> Kjo mund të ndihmojë të kujtoj këtë,
kështu që le të marrin një vështrim në këtë.

14
00:00:47,130 --> 00:00:49,710
Pra kjo, unë luftoj, është një
array Unsorted dhe unë kam

15
00:00:49,710 --> 00:00:53,040
treguar atë duke treguar se të gjitha
nga elementet janë të ngjyrosura kuqe,

16
00:00:53,040 --> 00:00:54,420
ata nuk janë të renditura ende.

17
00:00:54,420 --> 00:00:57,670
Kjo është e gjithë
pjesë Unsorted e vektorit.

18
00:00:57,670 --> 00:01:02,020
>> Pra, le të shkojnë nëpër hapat e
Zgjedhja lloj për të zgjidhur këtë koleksion.

19
00:01:02,020 --> 00:01:05,296
Pra, përsëri, ne jemi gonna përsëritje
derisa ka elemente Unsorted mbeten.

20
00:01:05,296 --> 00:01:07,920
Ne jemi gonna të kërkuar përmes
të dhënat për të gjetur vlerën më të vogël,

21
00:01:07,920 --> 00:01:11,990
dhe pastaj të bie në ujdi se vlera me të
elementi i parë i pjesës pandara.

22
00:01:11,990 --> 00:01:14,380
>> Tani për tani, përsëri, të gjithë
array është pjesa Unsorted.

23
00:01:14,380 --> 00:01:16,534
Të gjitha elementet e kuqe janë Unsorted.

24
00:01:16,534 --> 00:01:18,700
Kështu që ne të kërkuar përmes dhe
ne gjejmë vlerën më të vogël.

25
00:01:18,700 --> 00:01:20,533
Ne të fillojë në fillim,
ne do të shkojmë deri në fund,

26
00:01:20,533 --> 00:01:23,630
ne gjejmë vlera më të vogël është, një.

27
00:01:23,630 --> 00:01:24,860
Pra, kjo është pjesa e parë.

28
00:01:24,860 --> 00:01:29,440
Dhe pastaj pjesa e dytë, bie në ujdi se vlera me
elementi i parë i pjesës pandara,

29
00:01:29,440 --> 00:01:31,340
ose elementi i parë të kuqe.

30
00:01:31,340 --> 00:01:34,980
>> Në këtë rast që do të jetë
pesë, kështu që ne bie në ujdi një dhe pesë.

31
00:01:34,980 --> 00:01:37,320
Kur e bëjmë këtë, ne mund të
vizualisht të shihni se ne kemi

32
00:01:37,320 --> 00:01:41,260
lëvizur elementin më të vogël me vlerë
e array, në fillim.

33
00:01:41,260 --> 00:01:43,920
Efektivisht klasifikim atë element.

34
00:01:43,920 --> 00:01:47,520
>> Dhe kështu që ne me të vërtetë mund të konfirmojmë
dhe shtet që një, është e renditura.

35
00:01:47,520 --> 00:01:52,080
Dhe kështu që ne do të tregojnë pjesën e renditura
e array tonë, duke e ngjyrosur blu.

36
00:01:52,080 --> 00:01:53,860
>> Tani ne vetëm përsëris procesin përsëri.

37
00:01:53,860 --> 00:01:57,430
Ne kërko nëpër pjesën e paklasifikuara të
array për të gjetur elementin më të vogël.

38
00:01:57,430 --> 00:01:59,000
Në këtë rast, është dy.

39
00:01:59,000 --> 00:02:02,100
>> Ne shkëmbim se me parë
element i pjesës pandara.

40
00:02:02,100 --> 00:02:05,540
Në këtë rast dy gjithashtu ndodh të jetë
elementi i parë i pjesës pandara.

41
00:02:05,540 --> 00:02:08,650
Pra, ne të bie në ujdi dy me vete,
e cila me të vërtetë vetëm lë dy

42
00:02:08,650 --> 00:02:11,257
ku është, dhe është e renditura.

43
00:02:11,257 --> 00:02:13,840
Duke vazhduar më, ne të kërkuar përmes
për të gjetur elementin më të vogël.

44
00:02:13,840 --> 00:02:15,030
Është e tre.

45
00:02:15,030 --> 00:02:17,650
Ne shkëmbim me parë
element, që është pesë.

46
00:02:17,650 --> 00:02:19,450
Dhe tani tre është e renditura.

47
00:02:19,450 --> 00:02:22,440
>> Ne kërkoni përmes përsëri, dhe ne
gjetur elementi më i vogël është katër.

48
00:02:22,440 --> 00:02:28,070
Ne të bie në ujdi atë me elementin e parë të
pjesë Unsorted, dhe tani katër është e renditura.

49
00:02:28,070 --> 00:02:29,910
>> Ne gjejmë se pesë është
elementi më i vogël.

50
00:02:29,910 --> 00:02:32,900
Ne shkëmbim me parë
element i pjesës pandara.

51
00:02:32,900 --> 00:02:34,740
Dhe tani pesë është e renditura.

52
00:02:34,740 --> 00:02:36,660
>> Dhe pastaj në fund, tonë
Pjesa Unsorted përbëhet

53
00:02:36,660 --> 00:02:38,576
e vetëm një element të vetëm,
kështu që ne të kërkuar nëpër

54
00:02:38,576 --> 00:02:41,740
dhe ne gjejmë se gjashtë është
më i vogël, dhe në fakt, vetëm element.

55
00:02:41,740 --> 00:02:44,906
Dhe pastaj ne mund të themi se ajo është e renditura.

56
00:02:44,906 --> 00:02:47,530
Dhe tani ne kemi ndezur koleksion tonë
nga të qenit Unsorted plotësisht

57
00:02:47,530 --> 00:02:52,660
në të kuqe, të zgjidhet plotësisht
në ngjyrë blu, duke përdorur përzgjedhjes lloj.

58
00:02:52,660 --> 00:02:54,920
>> Pra, çfarë është skenari më i keq këtu?

59
00:02:54,920 --> 00:02:57,830
Edhe në absolut më të keq
rast, ne duhet të shikojmë gjatë

60
00:02:57,830 --> 00:03:02,170
të gjitha elementet e vektorit të
gjeni elementin më të vogël Unsorted,

61
00:03:02,170 --> 00:03:04,750
dhe ne kemi për të përsëritur
ky proces n herë.

62
00:03:04,750 --> 00:03:09,090
Një herë për çdo element të vektorit
sepse ne vetëm, në këtë algorithm,

63
00:03:09,090 --> 00:03:12,180
lloj një element në kohë.

64
00:03:12,180 --> 00:03:13,595
>> Çfarë është skenari më i mirë?

65
00:03:13,595 --> 00:03:15,040
E pra kjo është saktësisht e njëjtë, e drejtë?

66
00:03:15,040 --> 00:03:18,440
Ne fakt duhet të ende hap përmes
çdo element i vetëm i vektorit

67
00:03:18,440 --> 00:03:22,040
në mënyrë që të konfirmoj që ajo është,
në fakt, elementi më i vogël.

68
00:03:22,040 --> 00:03:26,760
>> Pra rast Runtime e keqja, ne
duhet të përsëris një proces n herë,

69
00:03:26,760 --> 00:03:28,960
herë për secilin prej elementeve n.

70
00:03:28,960 --> 00:03:31,940
Dhe në rastin më të mirë,
ne duhet të bëjmë të njëjtën gjë.

71
00:03:31,940 --> 00:03:35,340
>> Pra duke menduar përsëri për tonë
Toolbox kompjuterike kompleksiteti,

72
00:03:35,340 --> 00:03:39,250
çfarë mendoni se është më e keqja
Rasti Runtime të përzgjedhjes lloj?

73
00:03:39,250 --> 00:03:41,840
Çfarë mendoni se është më e mira
Rasti Runtime të përzgjedhjes lloj?

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

75
00:03:44,760 --> 00:03:49,325
>> A ju me mend Big O i n katror,
dhe Big Omega i n katror?

76
00:03:49,325 --> 00:03:49,950
Ju do të jetë e drejtë.

77
00:03:49,950 --> 00:03:52,490
Ata janë, në fakt,
Rasti më i keq dhe rastit të drejtuar mirë

78
00:03:52,490 --> 00:03:55,100
herë, për zgjedhjen lloji.

79
00:03:55,100 --> 00:03:56,260
>> Unë jam Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Kjo është CS50.

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