1
00:00:00,000 --> 00:00:05,726
 [SKAN MŪZIKA]

2
00:00:05,726 --> 00:00:08,098
DAGS LOIDS: atlases kārtošana ir
algoritms, kas, kā jūs varētu 

3
00:00:08,098 --> 00:00:10,470
sagaidīt, sakārto elementu kopu. 

4
00:00:10,470 --> 00:00:12,865
Un algoritma atsaukšana ir
norādījumu kopums uzdevuma izpildei soli 

5
00:00:12,865 --> 00:00:15,260
pa solim. 

6
00:00:15,260 --> 00:00:18,670
Atlases kārtošanas pamatideja ir
šāda – atrodiet mazāko nesakārtotu 

7
00:00:18,670 --> 00:00:22,080
elementu un pievienojiet to
sakārtota saraksta beigās. 

8
00:00:22,080 --> 00:00:26,970
Tas efektīvi veido sakārtotu
sarakstu, pa vienam elementam.

9
00:00:26,970 --> 00:00:30,730
Sadalot to līdz pseidokodam, mēs
varētu norādīt šo algoritmu šādi – 

10
00:00:30,730 --> 00:00:34,490
atkārtojiet to, līdz vairs nav
nesakārtotu elementu. 

11
00:00:34,490 --> 00:00:39,310
Meklējiet nesakārtotos datos, lai
atrastu mazāko vērtību, pēc tam 

12
00:00:39,310 --> 00:00:44,130
samainiet mazāko vērtību ar
nesakārtotas daļas pirmo elementu. 

13
00:00:44,130 --> 00:00:47,130
 Tas var palīdzēt to iztēloties,
tāpēc apskatīsim to.

14
00:00:47,130 --> 00:00:49,560
Tātad, es uzskatu, ka tas ir
nesakārtotsmasīvs, un es to norādīju, 

15
00:00:49,560 --> 00:00:51,990
norādot, ka visi elementi ir
iekrāsoti sarkanā krāsā, tie vēl nav 

16
00:00:51,990 --> 00:00:54,420
sakārtoti. 

17
00:00:54,420 --> 00:00:57,670
Šī ir visa nesakārtotamasīva daļa.

18
00:00:57,670 --> 00:01:02,020
 Tātad, veiksim atlases kārtošanas
darbības, lai sakārtotu šo masīvu.

19
00:01:02,020 --> 00:01:05,296
Tad atkal, mēs atkārtosim, līdz
nepaliks nesakārtoti elementi.

20
00:01:05,296 --> 00:01:08,643
Mēs meklēsim datos, lai atrastu
mazāko vērtību, un pēc tam apmainīsim 

21
00:01:08,643 --> 00:01:11,990
šo vērtību ar pirmo nesakārtotas
daļas elementu. 

22
00:01:11,990 --> 00:01:14,380
 Šobrīd atkal viss masīvs ir
nesakārtots.

23
00:01:14,380 --> 00:01:16,534
Visi sarkanie elementi ir
nesakārtoti.

24
00:01:16,534 --> 00:01:18,700
Tāpēc mēs meklējam un atrodam
mazāko vērtību.

25
00:01:18,700 --> 00:01:21,165
Mēs sākam no sākuma, ejam līdz
beigām, atrodam, ka mazākā vērtība ir 

26
00:01:21,165 --> 00:01:23,630
viens. 

27
00:01:23,630 --> 00:01:24,860
Tātad tā ir pirmā daļa.

28
00:01:24,860 --> 00:01:28,100
Un pēc tam otrā daļa, nomainiet šo
vērtību ar pirmo nesakārtotas 

29
00:01:28,100 --> 00:01:31,340
daļas elementu vai pirmo sarkanu
elementu. 

30
00:01:31,340 --> 00:01:34,980
 Šajā gadījumā tie būtu pieci,
tāpēc mēs samainām vienu ar pieci.

31
00:01:34,980 --> 00:01:38,120
Kad mēs to darām, mēs varam redzēt,
ka esam pārvietojuši vismazāko 

32
00:01:38,120 --> 00:01:41,260
masīva elementu uz pašu sākumu. 

33
00:01:41,260 --> 00:01:43,920
Efektīvi sakārtojam šo elementu.

34
00:01:43,920 --> 00:01:45,720
Un tāpēc mēs patiešām varam
apstiprināt un apgalvot, ka viens ir 

35
00:01:45,720 --> 00:01:47,520
sakārtots. 

36
00:01:47,520 --> 00:01:49,800
Un tāpēc mēs norādīsim mūsu masīva
sakārtotu daļu, iekrāsojot to zilā 

37
00:01:49,800 --> 00:01:52,080
krāsā. 

38
00:01:52,080 --> 00:01:53,860
 Tagad mēs vienkārši atkārtojam
procesu vēlreiz.

39
00:01:53,860 --> 00:01:57,430
Mēs meklējam masīva nesakārtotā
daļā, lai atrastu mazāko elementu.

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

41
00:01:59,000 --> 00:02:02,100
 Mēs to nomainām arnesakārtotas
daļas pirmo elementu.

42
00:02:02,100 --> 00:02:05,540
Šajā gadījumā divi arī ir pirmais
nesakārtotas daļas elements.

43
00:02:05,540 --> 00:02:08,398
Tāpēc mēs apmainām divi ar divi,
kas faktiski tikai atstāj elementu 

44
00:02:08,398 --> 00:02:11,257
divi, kur tas ir, un tas tiek
sakārtots. 

45
00:02:11,257 --> 00:02:13,840
Turpinot, mēs meklējam, lai atrastu
mazāko elementu.

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

47
00:02:15,030 --> 00:02:17,650
Mēs to apmainām ar pirmo elementu,
kas ir pieci.

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

49
00:02:19,450 --> 00:02:22,440
 Mēs pārmeklējam vēlreiz, un
atklājam, ka mazākais elements ir četri.

50
00:02:22,440 --> 00:02:25,255
Mēs to apmainām ar pirmo
nesakārtotas daļas elementu, un tagad 

51
00:02:25,255 --> 00:02:28,070
elements četri ir sakārtots. 

52
00:02:28,070 --> 00:02:29,910
 Mēs atklājam, ka pieci ir mazākais
elements.

53
00:02:29,910 --> 00:02:32,900
Mēs to samainām ar nešķirotās daļas
pirmo elementu.

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

55
00:02:34,740 --> 00:02:37,073
Un visbeidzot, mūsu nesakārtota
daļa sastāv tikai no viena elementa, 

56
00:02:37,073 --> 00:02:39,406
tāpēc mēs pārmeklējam un atklājam,
ka seši ir mazākais un faktiski 

57
00:02:39,406 --> 00:02:41,740
vienīgais elements. 

58
00:02:41,740 --> 00:02:44,906
Un tad mēs varam paziņot, ka tas ir
sakārtots.

59
00:02:44,906 --> 00:02:47,490
Un tagad mēs esam pārveidojuši savu
masīvu no pilnīgi nesakārtota 

60
00:02:47,490 --> 00:02:50,075
sarkanā krāsā uz pilnībā sakārtotu
zilā krāsā, izmantojot atlases 

61
00:02:50,075 --> 00:02:52,660
kārtošanu. 

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

63
00:02:54,920 --> 00:02:58,196
Absolūti sliktākajā gadījumā mums
ir jāpārskata visi masīva elementi, 

64
00:02:58,196 --> 00:03:01,473
lai atrastu mazāko nesakārtotu
elementu, un mums šis process ir 

65
00:03:01,473 --> 00:03:04,750
jāatkārto n reizes. 

66
00:03:04,750 --> 00:03:08,465
Vienu reizi katram masīva
elementam, jo šajā algoritmā mēs vienlaikus 

67
00:03:08,465 --> 00:03:12,180
kārtojam tikai vienu elementu. 

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

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

70
00:03:15,040 --> 00:03:18,540
Mums faktiski joprojām ir jāiet
cauri katram masīva elementam, lai 

71
00:03:18,540 --> 00:03:22,040
pārliecinātos, ka tas patiesībā ir
mazākais elements. 

72
00:03:22,040 --> 00:03:25,500
Tātad vissliktākajā gadījumā mums
ir jāatkārto process n reizes, 

73
00:03:25,500 --> 00:03:28,960
vienu reizi katram n elementam. 

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

75
00:03:31,940 --> 00:03:35,595
Tātad, atskatoties uz mūsu
skaitļošanas sarežģītības rīklodziņu, 

76
00:03:35,595 --> 00:03:39,250
kāds, jūsuprāt, ir sliktākais
atlases kārtošanas izpildlaiks? 

77
00:03:39,250 --> 00:03:41,840
Kāds, jūsuprāt, ir labākais atlases
kārtošanas izpildlaiks?

78
00:03:44,760 --> 00:03:49,325
 Vai domājāt par lielo O no n
kvadrātā un lielo Omega no n kvadrātā?

79
00:03:49,325 --> 00:03:49,950
Tad Jums būtu taisnība.

80
00:03:49,950 --> 00:03:52,525
Patiesībā tie ir atlases kārtošanas
izpildlaiki sliktākajā un 

81
00:03:52,525 --> 00:03:55,100
labākajā gadījumos. 

82
00:03:55,100 --> 00:03:56,260
 Es esmu Dags Loids.

83
00:03:56,260 --> 00:03:58,600
Šis ir CS50.