1
00:00:00,000 --> 00:00:05,726
>> [Přehrávání hudby]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Selection sort je
algoritmus, který, jak se dalo očekávat,

3
00:00:08,600 --> 00:00:10,470
třídí soubor prvků.

4
00:00:10,470 --> 00:00:12,470
A algoritmus odvolání
je krok-za-krokem set

5
00:00:12,470 --> 00:00:15,260
instrukcí pro dokončení úkolu.

6
00:00:15,260 --> 00:00:17,580
>> Při výběru setřiďte
Základní myšlenka je to,

7
00:00:17,580 --> 00:00:22,080
najít nejmenší netříděného prvek a
přidat do konce tříděného seznamu.

8
00:00:22,080 --> 00:00:26,970
Účinně, co to dělá, je build
seřazeným seznam, jeden prvek najednou.

9
00:00:26,970 --> 00:00:29,800
Rozebrat to k pseudokódu
jsme mohli konstatovat tento algoritmus

10
00:00:29,800 --> 00:00:34,490
takto, opakujte, dokud
žádné netříděné prvky zůstávají.

11
00:00:34,490 --> 00:00:38,660
Prostřednictvím netříděného vyhledávání
Údaje najít nejmenší hodnotu,

12
00:00:38,660 --> 00:00:44,130
pak vymění nejmenší hodnotu s
První prvek netříděného části.

13
00:00:44,130 --> 00:00:47,130
>> To může pomoci vizualizovat to,
takže se pojďme podívat na to.

14
00:00:47,130 --> 00:00:49,710
Takže to, tvrdím, je
netříděný pole a já jsem

15
00:00:49,710 --> 00:00:53,040
indikováno to tím, že všechny uvedením
prvky jsou v červené barvě,

16
00:00:53,040 --> 00:00:54,420
nejsou dosud seřazeny.

17
00:00:54,420 --> 00:00:57,670
Toto je úplná
netříděný součástí pole.

18
00:00:57,670 --> 00:01:02,020
>> Takže pojďme projít kroky
výběr třídit třídit tohoto pole.

19
00:01:02,020 --> 00:01:05,296
Takže znovu, budeme opakovat
do žádné netříděné prvky zůstávají.

20
00:01:05,296 --> 00:01:07,920
Budeme prohledávat
Údaje najít nejmenší hodnotu,

21
00:01:07,920 --> 00:01:11,990
a pak se vymění tuto hodnotu s
První prvek netříděného části.

22
00:01:11,990 --> 00:01:14,380
>> Právě teď, znovu, celý
pole je netříděného část.

23
00:01:14,380 --> 00:01:16,534
Všechny červenými prvky jsou netříděný.

24
00:01:16,534 --> 00:01:18,700
Tak jsme prohledávat a
najdeme nejmenší hodnotu.

25
00:01:18,700 --> 00:01:20,533
Začneme na začátku,
jdeme až do konce,

26
00:01:20,533 --> 00:01:23,630
najdeme nejmenší hodnota je jedna.

27
00:01:23,630 --> 00:01:24,860
Takže to je první část.

28
00:01:24,860 --> 00:01:29,440
A pak druhá část, vyměnit tuto hodnotu
první prvek netříděného části,

29
00:01:29,440 --> 00:01:31,340
nebo první červený prvek.

30
00:01:31,340 --> 00:01:34,980
>> V tomto případě, že by bylo
pět, takže jsme se vyměnit jedno a pět.

31
00:01:34,980 --> 00:01:37,320
Když to uděláme, můžeme
vizuálně vidět, že máme

32
00:01:37,320 --> 00:01:41,260
pohyboval nejmenší hodnotě prvku
matice, na samém počátku.

33
00:01:41,260 --> 00:01:43,920
Účinně třídění tento prvek.

34
00:01:43,920 --> 00:01:47,520
>> A tak můžeme skutečně potvrdit,
a uvádí, že jeden, je třídit.

35
00:01:47,520 --> 00:01:52,080
A tak budeme uvádět seřazené část
našeho pole, zbarvením to modré.

36
00:01:52,080 --> 00:01:53,860
>> Teď už jen opakovat postup.

37
00:01:53,860 --> 00:01:57,430
Hledáme přes netříděného část
pole najít nejmenší prvek.

38
00:01:57,430 --> 00:01:59,000
V tomto případě je to dva.

39
00:01:59,000 --> 00:02:02,100
>> Jsme vyměnit, že s prvním
prvek netříděného části.

40
00:02:02,100 --> 00:02:05,540
V tomto případě dvou je shodou okolností také
první prvek netříděného části.

41
00:02:05,540 --> 00:02:08,650
Tak jsme vyměnit dva se sebou samým,
která opravdu jen dva listy

42
00:02:08,650 --> 00:02:11,257
tam, kde je, a to seřazeny.

43
00:02:11,257 --> 00:02:13,840
Pokračování na, jsme prohledávat
najít nejmenší prvek.

44
00:02:13,840 --> 00:02:15,030
Je to tři.

45
00:02:15,030 --> 00:02:17,650
Jsme vyměnit ji s prvním
prvek, který je pět.

46
00:02:17,650 --> 00:02:19,450
A teď tři je seřazen.

47
00:02:19,450 --> 00:02:22,440
>> Hledáme ještě jednou, a my
najít nejmenší prvek je čtyři.

48
00:02:22,440 --> 00:02:28,070
My ji vyměnit s prvním prvkem z
netříděný část, a teď čtyřmi je tříděn.

49
00:02:28,070 --> 00:02:29,910
>> Zjistili jsme, že pět je
nejmenší prvek.

50
00:02:29,910 --> 00:02:32,900
Jsme vyměnit ji s prvním
prvek netříděného části.

51
00:02:32,900 --> 00:02:34,740
A teď se pět seřazeny.

52
00:02:34,740 --> 00:02:36,660
>> A pak konečně, naše
netříděný část tvoří

53
00:02:36,660 --> 00:02:38,576
pouhého jednoho prvku,
tak jsme prohledávat

54
00:02:38,576 --> 00:02:41,740
a zjistíme, že šest je
nejmenší, a ve skutečnosti, jediným prvkem.

55
00:02:41,740 --> 00:02:44,906
A pak můžeme konstatovat, že je tříděn.

56
00:02:44,906 --> 00:02:47,530
A teď jsme zapnutý naší nabídku
od bytí úplně nevytříděné

57
00:02:47,530 --> 00:02:52,660
v červené barvě, zcela seřazena
v modré, s použitím výběrem Třídit.

58
00:02:52,660 --> 00:02:54,920
>> Takže to, co je tady ten nejhorší možný scénář?

59
00:02:54,920 --> 00:02:57,830
No v absolutně nejhorší
případ, musíme se dívat přes

60
00:02:57,830 --> 00:03:02,170
všechny prvky pole na
najít nejmenší netříděného prvek,

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

62
00:03:04,750 --> 00:03:09,090
Jednou pro každý prvek matice
protože jen my, v tomto algoritmu,

63
00:03:09,090 --> 00:03:12,180
třídit jeden prvek v čase.

64
00:03:12,180 --> 00:03:13,595
>> Jaký je nejlepší scénář?

65
00:03:13,595 --> 00:03:15,040
No to je přesně to samé, že jo?

66
00:03:15,040 --> 00:03:18,440
Vlastně jsme muset stále procházet
každý prvek pole

67
00:03:18,440 --> 00:03:22,040
aby bylo možné potvrdit, že to je,
ve skutečnosti, že nejmenší prvek.

68
00:03:22,040 --> 00:03:26,760
>> Takže nejhorší případ runtime, my
muset opakovat proces n-krát,

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

70
00:03:28,960 --> 00:03:31,940
A v nejlepším případě,
musíme udělat totéž.

71
00:03:31,940 --> 00:03:35,340
>> Tak vzpomínal na náš
výpočetní složitost toolbox,

72
00:03:35,340 --> 00:03:39,250
co si myslíte, že je to nejhorší
pouzdro runtime pro výběr druhu?

73
00:03:39,250 --> 00:03:41,840
Co si myslíte, že je nejlepší
pouzdro runtime pro výběr druhu?

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

75
00:03:44,760 --> 00:03:49,325
>> Věděli jste asi velký O z n na druhou,
a Big Omega n na druhou?

76
00:03:49,325 --> 00:03:49,950
Vy byste mít pravdu.

77
00:03:49,950 --> 00:03:52,490
To jsou, ve skutečnosti,
nejhorší případ a nejlepší případ běh

78
00:03:52,490 --> 00:03:55,100
časy, pro výběr druhu.

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

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

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