1
00:00:00,000 --> 00:00:05,726
>> [Mūzikas atskaņošanai]

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD: Selection kārtošanas ir
algoritms, kas, kā jūs varētu gaidīt,

3
00:00:08,600 --> 00:00:10,470
sakārto elementu kopumu.

4
00:00:10,470 --> 00:00:12,470
Un algoritms atsaukšana
ir soli pa solim komplekts

5
00:00:12,470 --> 00:00:15,260
par norādījumiem, kā pabeigt uzdevumu.

6
00:00:15,260 --> 00:00:17,580
>> Izvēlē kārtot
Pamatideja ir tas,

7
00:00:17,580 --> 00:00:22,080
atrast mazāko nešķirotas elementu un
pievienojiet to beigām šķiroto sarakstā.

8
00:00:22,080 --> 00:00:26,970
Efektīvi Kas tas ir būvēt
sakārtoti sarakstu, viens elements laikā.

9
00:00:26,970 --> 00:00:29,800
Breaking to uz leju līdz pseudocode
mēs varētu norādīt šo algoritmu

10
00:00:29,800 --> 00:00:34,490
šādi, atkārtojiet šo darbību, līdz
Nav nešķirotas elementi paliek.

11
00:00:34,490 --> 00:00:38,660
Pārlūkot nešķiroti
datus, lai atrastu mazāko vērtību,

12
00:00:38,660 --> 00:00:44,130
Pēc tam mijmaiņas mazāko vērtību ar
no nešķirotu daļas pirmais elements.

13
00:00:44,130 --> 00:00:47,130
>> Tas var palīdzēt vizualizēt to,
tāpēc pieņemsim to apskatīt šo.

14
00:00:47,130 --> 00:00:49,710
Tātad tas, es apgalvo, ir
nešķiroti masīvs un es esmu

15
00:00:49,710 --> 00:00:53,040
norādīja to, norādot, ka visi
no elementiem, ir sarkanā krāsā,

16
00:00:53,040 --> 00:00:54,420
tie vēl nav sakārtots.

17
00:00:54,420 --> 00:00:57,670
Tas ir viss
nešķiroti daļa no masīva.

18
00:00:57,670 --> 00:01:02,020
>> So iesim cauri soļiem
atlase Kārtot, lai sakārtotu šo masīvu.

19
00:01:02,020 --> 00:01:05,296
Tātad vēlreiz, mēs esam gonna atkārtot
kamēr nav nešķirotas elementi paliek.

20
00:01:05,296 --> 00:01:07,920
Mēs esam gonna pārlūkot
datus, lai atrastu mazāko vērtību,

21
00:01:07,920 --> 00:01:11,990
un pēc tam mijmaiņas šo vērtību ar
no nešķirotu daļas pirmais elements.

22
00:01:11,990 --> 00:01:14,380
>> Tieši tagad, atkal, viss
masīvs ir nešķirotas daļa.

23
00:01:14,380 --> 00:01:16,534
Visi sarkanās elementiem nav šķirotas.

24
00:01:16,534 --> 00:01:18,700
Tātad mēs pārlūkot un
mēs atrodam mazāko vērtību.

25
00:01:18,700 --> 00:01:20,533
Sākam sākumā,
mēs iet uz beigām,

26
00:01:20,533 --> 00:01:23,630
mēs atrodam mazāko vērtību ir viens.

27
00:01:23,630 --> 00:01:24,860
Tā ka ir viena daļa.

28
00:01:24,860 --> 00:01:29,440
Un tad otrā daļa, mijmaiņas šo vērtību ar
No nešķirotu daļas pirmais elements,

29
00:01:29,440 --> 00:01:31,340
vai pirmais sarkanais elements.

30
00:01:31,340 --> 00:01:34,980
>> Šajā gadījumā, kas būtu
pieci, tāpēc mēs mijmaiņas viena līdz pieciem.

31
00:01:34,980 --> 00:01:37,320
Kad mēs to darām, mēs varam
vizuāli redzēt, ka mēs esam

32
00:01:37,320 --> 00:01:41,260
pārcēlās vismazāko vērtē elements
masīva, lai paša sākuma.

33
00:01:41,260 --> 00:01:43,920
Efektīvi šķirošanas šo elementu.

34
00:01:43,920 --> 00:01:47,520
>> Un tā mēs varam patiesi apstiprināt
un norāda, ka viens, ir sakārtots.

35
00:01:47,520 --> 00:01:52,080
Un tā mēs norāda sakārtoti daļu
Mūsu masīva, iekrāsojot to zilā krāsā.

36
00:01:52,080 --> 00:01:53,860
>> Tagad mēs vienkārši atkārtot procesu no jauna.

37
00:01:53,860 --> 00:01:57,430
Mēs meklējam caur nešķirotu daļu
masīvs atrast mazāko elementu.

38
00:01:57,430 --> 00:01:59,000
Šajā gadījumā tas ir divi.

39
00:01:59,000 --> 00:02:02,100
>> Mēs mijmaiņas ka ar pirmo
no nešķirotiem daļas elements.

40
00:02:02,100 --> 00:02:05,540
Šajā gadījumā divi arī notiek,
No nešķirotu daļas pirmais elements.

41
00:02:05,540 --> 00:02:08,650
Tātad mēs mijmaiņas divas ar sevi,
kas patiešām ir tikai atstāj divus

42
00:02:08,650 --> 00:02:11,257
kur tas ir, un tas ir sakārtoti.

43
00:02:11,257 --> 00:02:13,840
Turpinot tālāk, mēs pārlūkot
atrast mazāko elementu.

44
00:02:13,840 --> 00:02:15,030
Tas ir trīs.

45
00:02:15,030 --> 00:02:17,650
Mēs apmainīt to ar pirmo
elements, kas ir pieci.

46
00:02:17,650 --> 00:02:19,450
Un tagad trīs ir sakārtots.

47
00:02:19,450 --> 00:02:22,440
>> Mēs pārlūkot atkal, un mēs
atrast mazākais elements ir četri.

48
00:02:22,440 --> 00:02:28,070
Mēs apmainīt to ar pirmā elementa
nešķiroti daļa, un tagad četri ir sakārtots.

49
00:02:28,070 --> 00:02:29,910
>> Mēs uzskatām, ka ir pieci
mazākais elements.

50
00:02:29,910 --> 00:02:32,900
Mēs apmainīt to ar pirmo
no nešķirotiem daļas elements.

51
00:02:32,900 --> 00:02:34,740
Un tagad pieci ir sakārtots.

52
00:02:34,740 --> 00:02:36,660
>> Un tad visbeidzot, mūsu
nešķiroti daļu veido

53
00:02:36,660 --> 00:02:38,576
par tikai vienu elementu,
tāpēc mēs pārlūkot

54
00:02:38,576 --> 00:02:41,740
un mēs redzam, ka seši ir
mazākais, un faktiski vienīgais elements.

55
00:02:41,740 --> 00:02:44,906
Un tad mēs varam apgalvot, ka tas ir sakārtots.

56
00:02:44,906 --> 00:02:47,530
Un tagad mēs esam pārgājuši mūsu masīvs
tiek pilnīgi Nesašķirotas

57
00:02:47,530 --> 00:02:52,660
sarkanā krāsā, lai pilnībā sakārtots
zilā krāsā, izmantojot atlases veida.

58
00:02:52,660 --> 00:02:54,920
>> Tātad, kas ir sliktākais scenārijs šeit?

59
00:02:54,920 --> 00:02:57,830
Nu absolūti sliktākais
gadījumā, mums ir jāskatās pāri

60
00:02:57,830 --> 00:03:02,170
visu elementu masīva līdz
atrast mazāko nešķirotas elementu,

61
00:03:02,170 --> 00:03:04,750
un mums ir jāatkārto
šis process n reizes.

62
00:03:04,750 --> 00:03:09,090
Pēc tam, kad katram masīva elementa
jo mēs tikai, šajā algoritmu,

63
00:03:09,090 --> 00:03:12,180
kārtot viens elements laikā.

64
00:03:12,180 --> 00:03:13,595
>> Kāds ir labākais scenārijs?

65
00:03:13,595 --> 00:03:15,040
Nu tas ir tieši tas pats, vai ne?

66
00:03:15,040 --> 00:03:18,440
Mums tiešām ir vēl soli pa
katru elementu masīva

67
00:03:18,440 --> 00:03:22,040
lai apstiprinātu to, ka tas ir,
patiesībā, mazākais elements.

68
00:03:22,040 --> 00:03:26,760
>> Tātad sliktākajā gadījumā runtime, mēs
atkārtot procesu n reizes,

69
00:03:26,760 --> 00:03:28,960
vienreiz par katru no n elementiem.

70
00:03:28,960 --> 00:03:31,940
Un labākajā gadījumā,
mums ir jādara tas pats.

71
00:03:31,940 --> 00:03:35,340
>> Tātad domāšana atpakaļ uz mūsu
skaitļošanas sarežģītība toolbox,

72
00:03:35,340 --> 00:03:39,250
Ko jūs domājat, ir vissliktākais
Lieta runtime uz atlases veida?

73
00:03:39,250 --> 00:03:41,840
Kas, Jūsuprāt, ir labākais
Lieta runtime uz atlases veida?

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

75
00:03:44,760 --> 00:03:49,325
>> Vai jūs uzminēt Big O no n brusas,
un Big Omega n kvadrātā?

76
00:03:49,325 --> 00:03:49,950
Tu būsi taisnība.

77
00:03:49,950 --> 00:03:52,490
Tie ir, faktiski,
sliktākajā gadījumā un labākajā gadījumā palaist

78
00:03:52,490 --> 00:03:55,100
reizes, lai atlases veida.

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

80
00:03:56,260 --> 00:03:58,600
Tas ir CS50.

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