1
00:00:00,000 --> 00:00:05,726
>> [Prehrávanie hudby]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Selection sort je
algoritmus, ktorý, ako sa dalo očakávať,

3
00:00:08,600 --> 00:00:10,470
triedi súbor prvkov.

4
00:00:10,470 --> 00:00:12,470
A algoritmus odvolanie
je krok-za-krokom set

5
00:00:12,470 --> 00:00:15,260
inštrukcií pre dokončenie úlohy.

6
00:00:15,260 --> 00:00:17,580
>> Pri výbere Roztieďte
Základná myšlienka je to,

7
00:00:17,580 --> 00:00:22,080
nájsť najmenší netriedeného prvok a
pridať do konca triedeného zoznamu.

8
00:00:22,080 --> 00:00:26,970
Účinne, čo to robí, je build
zoradeným zoznam, jeden prvok naraz.

9
00:00:26,970 --> 00:00:29,800
Rozobrať to k pseudokódu
sme mohli konštatovať tento algoritmus

10
00:00:29,800 --> 00:00:34,490
takto, opakujte, kým
žiadne netriedené prvky zostávajú.

11
00:00:34,490 --> 00:00:38,660
Prostredníctvom netriedeného vyhľadávanie
Údaje nájsť najmenšiu hodnotu,

12
00:00:38,660 --> 00:00:44,130
potom vymení najmenšiu hodnotu s
Prvý prvok netriedeného časti.

13
00:00:44,130 --> 00:00:47,130
>> To môže pomôcť vizualizovať to,
takže sa poďme pozrieť na to.

14
00:00:47,130 --> 00:00:49,710
Takže to, tvrdím, je
netriedený poľa a ja som

15
00:00:49,710 --> 00:00:53,040
indikované to tým, že všetky uvedením
prvky sú v červenej farbe,

16
00:00:53,040 --> 00:00:54,420
nie sú dosiaľ zoradené.

17
00:00:54,420 --> 00:00:57,670
Toto je úplná
netriedený súčasťou poľa.

18
00:00:57,670 --> 00:01:02,020
>> Takže poďme prejsť krokmi
výber triediť triediť tohto poľa.

19
00:01:02,020 --> 00:01:05,296
Takže znova, budeme opakovať
do žiadnej netriedené prvky zostávajú.

20
00:01:05,296 --> 00:01:07,920
Budeme prehľadávať
Údaje nájsť najmenšiu hodnotu,

21
00:01:07,920 --> 00:01:11,990
a potom sa vymení túto hodnotu s
Prvý prvok netriedeného časti.

22
00:01:11,990 --> 00:01:14,380
>> Práve teraz, znovu, celý
pole je netriedeného časť.

23
00:01:14,380 --> 00:01:16,534
Všetky červenými prvkami sú netriedený.

24
00:01:16,534 --> 00:01:18,700
Tak sme prehľadávať a
nájdeme najmenšiu hodnotu.

25
00:01:18,700 --> 00:01:20,533
Začneme na začiatku,
ideme až do konca,

26
00:01:20,533 --> 00:01:23,630
nájdeme najmenšia hodnota je jedna.

27
00:01:23,630 --> 00:01:24,860
Takže to je prvá časť.

28
00:01:24,860 --> 00:01:29,440
A potom druhá časť, vymeniť túto hodnotu
prvý prvok netriedeného časti,

29
00:01:29,440 --> 00:01:31,340
alebo prvý červený prvok.

30
00:01:31,340 --> 00:01:34,980
>> V tomto prípade, že by bolo
päť, takže sme sa vymeniť jedno a päť.

31
00:01:34,980 --> 00:01:37,320
Keď to urobíme, môžeme
vizuálne vidieť, že máme

32
00:01:37,320 --> 00:01:41,260
pohyboval najmenšie hodnote prvku
matice, na samom počiatku.

33
00:01:41,260 --> 00:01:43,920
Účinne triedenie tento prvok.

34
00:01:43,920 --> 00:01:47,520
>> A tak môžeme skutočne potvrdiť,
a uvádza, že jeden, je triediť.

35
00:01:47,520 --> 00:01:52,080
A tak budeme uvádzať zoradené časť
nášho poľa, sfarbením to modré.

36
00:01:52,080 --> 00:01:53,860
>> Teraz už len opakovať postup.

37
00:01:53,860 --> 00:01:57,430
Hľadáme cez netriedeného časť
pole nájsť najmenší prvok.

38
00:01:57,430 --> 00:01:59,000
V tomto prípade je to dva.

39
00:01:59,000 --> 00:02:02,100
>> Sme vymeniť, že s prvým
prvok netriedeného časti.

40
00:02:02,100 --> 00:02:05,540
V tomto prípade dvoch je zhodou okolností tiež
prvý prvok netriedeného časti.

41
00:02:05,540 --> 00:02:08,650
Tak sme vymeniť dva so sebou samým,
ktorá naozaj len dva listy

42
00:02:08,650 --> 00:02:11,257
tam, kde je, a to zoradené.

43
00:02:11,257 --> 00:02:13,840
Pokračovanie na, sme prehľadávať
nájsť najmenší prvok.

44
00:02:13,840 --> 00:02:15,030
Je to tri.

45
00:02:15,030 --> 00:02:17,650
Sme vymeniť ju s prvým
prvok, ktorý je päť.

46
00:02:17,650 --> 00:02:19,450
A teraz tri je zoradený.

47
00:02:19,450 --> 00:02:22,440
>> Hľadáme ešte raz, a my
nájsť najmenší prvok je štyri.

48
00:02:22,440 --> 00:02:28,070
My ju vymeniť s prvým prvkom z
netriedený časť, a teraz štyrmi je triedený.

49
00:02:28,070 --> 00:02:29,910
>> Zistili sme, že päť je
najmenší prvok.

50
00:02:29,910 --> 00:02:32,900
Sme vymeniť ju s prvým
prvok netriedeného časti.

51
00:02:32,900 --> 00:02:34,740
A teraz sa päť zoradené.

52
00:02:34,740 --> 00:02:36,660
>> A potom konečne, naša
netriedený časť tvorí

53
00:02:36,660 --> 00:02:38,576
púheho jedného prvku,
tak sme prehľadávať

54
00:02:38,576 --> 00:02:41,740
a zistíme, že šesť je
najmenšie, a v skutočnosti, jediným prvkom.

55
00:02:41,740 --> 00:02:44,906
A potom môžeme konštatovať, že je triedený.

56
00:02:44,906 --> 00:02:47,530
A teraz sme zapnutý našu ponuku
od bytia úplne nevytriedené

57
00:02:47,530 --> 00:02:52,660
v červenej farbe, úplne zoradená
v modrej, s použitím výberom Triediť.

58
00:02:52,660 --> 00:02:54,920
>> Takže to, čo je tu ten najhorší možný scenár?

59
00:02:54,920 --> 00:02:57,830
No v absolútne najhoršie
prípad, musíme sa pozerať cez

60
00:02:57,830 --> 00:03:02,170
všetky prvky poľa na
nájsť najmenší netriedeného prvok,

61
00:03:02,170 --> 00:03:04,750
a musíme zopakovať
tento proces n-krát.

62
00:03:04,750 --> 00:03:09,090
Raz pre každý prvok matice
pretože len my, v tomto algoritmu,

63
00:03:09,090 --> 00:03:12,180
triediť jeden prvok v čase.

64
00:03:12,180 --> 00:03:13,595
>> Aký je najlepší scenár?

65
00:03:13,595 --> 00:03:15,040
No to je presne to isté, že jo?

66
00:03:15,040 --> 00:03:18,440
Vlastne sme musieť stále prechádzať
každý prvok poľa

67
00:03:18,440 --> 00:03:22,040
aby bolo možné potvrdiť, že to je,
v skutočnosti, že najmenší prvok.

68
00:03:22,040 --> 00:03:26,760
>> Takže najhorší prípad runtime, my
musieť opakovať proces n-krát,

69
00:03:26,760 --> 00:03:28,960
raz pre každý z n elementy.

70
00:03:28,960 --> 00:03:31,940
A v najlepšom prípade,
musíme urobiť to isté.

71
00:03:31,940 --> 00:03:35,340
>> Tak spomínal na náš
výpočtovej zložitosť toolbox,

72
00:03:35,340 --> 00:03:39,250
čo si myslíte, že je to najhoršie
puzdro runtime pre výber druhu?

73
00:03:39,250 --> 00:03:41,840
Čo si myslíte, že je najlepší
puzdro runtime pre výber druhu?

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

75
00:03:44,760 --> 00:03:49,325
>> Vedeli ste asi veľký O z n na druhú,
a Big Omega n na druhú?

76
00:03:49,325 --> 00:03:49,950
Vy by ste mať pravdu.

77
00:03:49,950 --> 00:03:52,490
To sú, v skutočnosti,
najhorší prípad a najlepší prípad beh

78
00:03:52,490 --> 00:03:55,100
časy, pre výber druhu.

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

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

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