1
00:00:00,000 --> 00:00:05,726
>> [Predvaja glasba]

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD: Izbor vrste je
algoritem, ki, kot bi lahko pričakovali,

3
00:00:08,600 --> 00:00:10,470
sortira niz elementov.

4
00:00:10,470 --> 00:00:12,470
In algoritem odpoklic
je korak-po-korak set

5
00:00:12,470 --> 00:00:15,260
navodil za dokončanje naloge.

6
00:00:15,260 --> 00:00:17,580
>> V izboru razvrstite
Osnovna ideja je ta,

7
00:00:17,580 --> 00:00:22,080
našli najmanjši neurejen element in
ga dodate na koncu urejenem seznamu.

8
00:00:22,080 --> 00:00:26,970
Učinkovito, kaj to počne je graditi
razporejene seznam, en element naenkrat.

9
00:00:26,970 --> 00:00:29,800
Ga zrušijo, da psevdokoda
smo lahko navede ta algoritem

10
00:00:29,800 --> 00:00:34,490
takole, ponovite dokler
Ni nesortirane elementi ostajajo.

11
00:00:34,490 --> 00:00:38,660
Iskanje po nerazvrščenih
Podatki najti najmanjšo vrednost,

12
00:00:38,660 --> 00:00:44,130
nato zamenjali najmanjšo vrednost s
Prvi element nerazvrščene dela.

13
00:00:44,130 --> 00:00:47,130
>> To lahko pomaga vizualizirati to,
tako da je lahko pogled na to.

14
00:00:47,130 --> 00:00:49,710
Torej to, da trdijo, je
razvrščeni nizi in sem

15
00:00:49,710 --> 00:00:53,040
jo označi z navedbo, da so vsi
elementov so rdeče barve,

16
00:00:53,040 --> 00:00:54,420
jih še ni urejeno.

17
00:00:54,420 --> 00:00:57,670
To je celotna
razvrščeni del matrike.

18
00:00:57,670 --> 00:01:02,020
>> Torej, pojdimo skozi korake
Izbor nekako rešiti to matriko.

19
00:01:02,020 --> 00:01:05,296
Torej še enkrat, bova ponovila
dokler ne ostane nobena nesortirane elementi.

20
00:01:05,296 --> 00:01:07,920
Mi boš iskanje po
Podatki najti najmanjšo vrednost,

21
00:01:07,920 --> 00:01:11,990
in nato zamenjali to vrednost z
Prvi element nerazvrščene dela.

22
00:01:11,990 --> 00:01:14,380
>> Zdaj, še enkrat, celotna
matrika je razvrščen del.

23
00:01:14,380 --> 00:01:16,534
Vse rdeče elementi so razvrščeni.

24
00:01:16,534 --> 00:01:18,700
Torej iščemo skozi in
najdemo najmanjšo vrednost.

25
00:01:18,700 --> 00:01:20,533
Začnemo na začetku,
gremo do konca,

26
00:01:20,533 --> 00:01:23,630
smo ugotovili, najmanjša vrednost, eden.

27
00:01:23,630 --> 00:01:24,860
Torej, to je prvi del.

28
00:01:24,860 --> 00:01:29,440
In potem drugi del, zamenjajte te vrednosti z
Prvi element nesortiranih strani

29
00:01:29,440 --> 00:01:31,340
ali prvi rdeče element.

30
00:01:31,340 --> 00:01:34,980
>> V tem primeru, da bi bila
pet, zato smo zamenjali eno in pet.

31
00:01:34,980 --> 00:01:37,320
Ko smo to naredili, smo lahko
vizualno videli, da smo jih

32
00:01:37,320 --> 00:01:41,260
preselil najmanjšo cenjen element
matrike, da se na samem začetku.

33
00:01:41,260 --> 00:01:43,920
Učinkovito razvrščanje ta element.

34
00:01:43,920 --> 00:01:47,520
>> In tako bomo lahko dejansko potrjuje
in navajajo, da eden, je razvrščen.

35
00:01:47,520 --> 00:01:52,080
In tako bomo navesti razvrščeni del
naše paleto, ki jo barvanje je modra.

36
00:01:52,080 --> 00:01:53,860
>> Zdaj moramo samo še enkrat ponoviti postopek.

37
00:01:53,860 --> 00:01:57,430
Iščemo preko navadne gospodinjske delu
array najti najmanjši element.

38
00:01:57,430 --> 00:01:59,000
V tem primeru je dva.

39
00:01:59,000 --> 00:02:02,100
>> Smo zamenjali, da s prvim
element nerazvrščene dela.

40
00:02:02,100 --> 00:02:05,540
V tem primeru sta se zgodi tudi, da je
Prvi element nerazvrščene dela.

41
00:02:05,540 --> 00:02:08,650
Tako smo zamenjali dve sama s seboj,
ki je res samo pušča dva

42
00:02:08,650 --> 00:02:11,257
kje je, in to je urejeno.

43
00:02:11,257 --> 00:02:13,840
Nadaljevanje, iščemo skozi
najti najmanjši element.

44
00:02:13,840 --> 00:02:15,030
To je tri.

45
00:02:15,030 --> 00:02:17,650
Smo jo zamenjali s prvim
Element, ki je pet.

46
00:02:17,650 --> 00:02:19,450
In zdaj tri je razvrščen.

47
00:02:19,450 --> 00:02:22,440
>> Iščemo skozi še enkrat, in mi
našli najmanjši element je štiri.

48
00:02:22,440 --> 00:02:28,070
Smo jo zamenjali s prvim elementom
nesortirani del, in zdaj je štiri razporejene.

49
00:02:28,070 --> 00:02:29,910
>> Ugotovili smo, da je pet
najmanjši element.

50
00:02:29,910 --> 00:02:32,900
Smo jo zamenjali s prvim
element nerazvrščene dela.

51
00:02:32,900 --> 00:02:34,740
In zdaj pet je razvrščen.

52
00:02:34,740 --> 00:02:36,660
>> In potem končno, naše
razvrščeni del sestoji

53
00:02:36,660 --> 00:02:38,576
z enim samim elementom
zato iščemo skozi

54
00:02:38,576 --> 00:02:41,740
in smo ugotovili, da je šest
najmanjša, in dejansko edini element.

55
00:02:41,740 --> 00:02:44,906
In potem lahko trdimo, da je to urejeno.

56
00:02:44,906 --> 00:02:47,530
In zdaj smo prešli našo paleto
ne bi popolnoma Nerazvrščene

57
00:02:47,530 --> 00:02:52,660
v rdeči barvi, v celoti razporejene
v modri barvi, z uporabo izbora vrste.

58
00:02:52,660 --> 00:02:54,920
>> Torej, kaj je najslabši možni scenarij tukaj?

59
00:02:54,920 --> 00:02:57,830
No, v absolutno najslabša
primera, moramo pogledati čez

60
00:02:57,830 --> 00:03:02,170
vseh elementih array
našli najmanjši neurejen element,

61
00:03:02,170 --> 00:03:04,750
in moramo ponoviti
Ta proces n-krat.

62
00:03:04,750 --> 00:03:09,090
Enkrat za vsak element matrike
ker le v tem algoritmu

63
00:03:09,090 --> 00:03:12,180
nekako en element v času.

64
00:03:12,180 --> 00:03:13,595
>> Kaj je najboljši scenarij?

65
00:03:13,595 --> 00:03:15,040
No, to je povsem enaka, kajne?

66
00:03:15,040 --> 00:03:18,440
Dejansko moramo vedno korak skozi
vsak element matrike

67
00:03:18,440 --> 00:03:22,040
da bi potrdili, da je,
Dejansko najmanjši element.

68
00:03:22,040 --> 00:03:26,760
>> Torej v najslabšem primeru runtime smo
morali ponoviti postopek n-krat,

69
00:03:26,760 --> 00:03:28,960
enkrat za vsak n elementov.

70
00:03:28,960 --> 00:03:31,940
In v najboljšem scenariju,
moramo, da storijo enako.

71
00:03:31,940 --> 00:03:35,340
>> Tako razmišljanje nazaj na naše
računska zahtevnost toolbox,

72
00:03:35,340 --> 00:03:39,250
kaj misliš, da je najslabša
Primer runtime za izbirni vrste?

73
00:03:39,250 --> 00:03:41,840
Kaj misliš, da je najboljša
Primer runtime za izbirni vrste?

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

75
00:03:44,760 --> 00:03:49,325
>> Ali uganete, Big O n kvadrat,
in Big Omega n kvadrat?

76
00:03:49,325 --> 00:03:49,950
Ti bi bilo prav.

77
00:03:49,950 --> 00:03:52,490
To so, v resnici,
najslabša in najboljša primera run

78
00:03:52,490 --> 00:03:55,100
čas, za izbiro vrste.

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

80
00:03:56,260 --> 00:03:58,600
To je CS50.

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