1
00:00:00,000 --> 00:00:05,726
>> [Musik spiller]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: valg Sorter er en
algoritme, der, som man kunne forvente,

3
00:00:08,600 --> 00:00:10,470
sorterer et sæt af elementer.

4
00:00:10,470 --> 00:00:12,470
Og algoritme tilbagekaldelse
er en trin-for-trin sæt

5
00:00:12,470 --> 00:00:15,260
af instruktioner til at fuldføre en opgave.

6
00:00:15,260 --> 00:00:17,580
>> I udvælgelsen sortere
grundlæggende idé er det,

7
00:00:17,580 --> 00:00:22,080
finde den mindste usorteret element og
føje den til slutningen af ​​den sorterede liste.

8
00:00:22,080 --> 00:00:26,970
Effektivt, hvad det betyder er build
en sorteret liste, et element ad gangen.

9
00:00:26,970 --> 00:00:29,800
Bryde det ned til pseudokode
vi kunne anføre denne algoritme

10
00:00:29,800 --> 00:00:34,490
som følger, gentag dette indtil
ingen usorterede elementer tilbage.

11
00:00:34,490 --> 00:00:38,660
Søg gennem usorterede
data for at finde den mindste værdi,

12
00:00:38,660 --> 00:00:44,130
derefter bytte den mindste værdi med den
første del af usorteret del.

13
00:00:44,130 --> 00:00:47,130
>> Det kan hjælpe til at visualisere denne,
så lad os tage et kig på dette.

14
00:00:47,130 --> 00:00:49,710
Så dette, jeg hævder, er en
usorteret array og jeg har

15
00:00:49,710 --> 00:00:53,040
angivet, at den ved at angive, at alle
af elementerne er farvet rødt,

16
00:00:53,040 --> 00:00:54,420
de ikke allerede er sorteret.

17
00:00:54,420 --> 00:00:57,670
Dette er hele
usorteret del af array'et.

18
00:00:57,670 --> 00:01:02,020
>> Så lad os gå gennem trinene
valg Sorter for at sortere dette array.

19
00:01:02,020 --> 00:01:05,296
Så igen, vi skal gentage
indtil der ikke usorterede elementer tilbage.

20
00:01:05,296 --> 00:01:07,920
Vi skal søge gennem
data for at finde den mindste værdi,

21
00:01:07,920 --> 00:01:11,990
og derefter bytte denne værdi med
første del af usorteret del.

22
00:01:11,990 --> 00:01:14,380
>> Lige nu, igen, at hele
array er den usorterede del.

23
00:01:14,380 --> 00:01:16,534
Alle de røde elementer er usorteret.

24
00:01:16,534 --> 00:01:18,700
Så vi søge gennem og
vi finder den mindste værdi.

25
00:01:18,700 --> 00:01:20,533
Vi starter i begyndelsen,
vi gå til slutningen,

26
00:01:20,533 --> 00:01:23,630
vi finder den mindste værdi, en.

27
00:01:23,630 --> 00:01:24,860
Så det er første del.

28
00:01:24,860 --> 00:01:29,440
Og så del to, bytte denne værdi med
det første element i den usorterede del,

29
00:01:29,440 --> 00:01:31,340
eller det første røde element.

30
00:01:31,340 --> 00:01:34,980
>> I dette tilfælde ville det være
fem, så vi bytte et og fem.

31
00:01:34,980 --> 00:01:37,320
Når vi gør det, vi kan
visuelt se, at vi har

32
00:01:37,320 --> 00:01:41,260
flyttede mindste værdsat element
af array, til begyndelsen.

33
00:01:41,260 --> 00:01:43,920
Effektivt sortering dette element.

34
00:01:43,920 --> 00:01:47,520
>> Og så kan vi faktisk bekræfte
og præcisere, at én, sorteres.

35
00:01:47,520 --> 00:01:52,080
Og så vil vi angive den sorteres del
vores array, ved at farve det blå.

36
00:01:52,080 --> 00:01:53,860
>> Nu skal vi bare gentage processen igen.

37
00:01:53,860 --> 00:01:57,430
Vi søger gennem usorterede del af
array for at finde det mindste element.

38
00:01:57,430 --> 00:01:59,000
I dette tilfælde er det to.

39
00:01:59,000 --> 00:02:02,100
>> Vi bytter at med den første
element i usorteret del.

40
00:02:02,100 --> 00:02:05,540
I dette tilfælde to også sker for at være
det første element af usorteret del.

41
00:02:05,540 --> 00:02:08,650
Så vi bytte to med sig selv,
som virkelig bare efterlader to

42
00:02:08,650 --> 00:02:11,257
hvor det er, og det er sorteret.

43
00:02:11,257 --> 00:02:13,840
Fortsætter på, søge vi gennem
at finde det mindste element.

44
00:02:13,840 --> 00:02:15,030
Det er tre.

45
00:02:15,030 --> 00:02:17,650
Vi bytter det med den første
element, som er fem.

46
00:02:17,650 --> 00:02:19,450
Og nu tre sorteres.

47
00:02:19,450 --> 00:02:22,440
>> Vi søge gennem igen, og vi
finde det mindste element er fire.

48
00:02:22,440 --> 00:02:28,070
Vi bytter det med det første element i den
usorteret side og nu fire sorteres.

49
00:02:28,070 --> 00:02:29,910
>> Vi finder, at fem er
det mindste element.

50
00:02:29,910 --> 00:02:32,900
Vi bytter det med den første
element i usorteret del.

51
00:02:32,900 --> 00:02:34,740
Og nu fem sorteres.

52
00:02:34,740 --> 00:02:36,660
>> Og derefter endelig vores
usorteret del består

53
00:02:36,660 --> 00:02:38,576
af blot et enkelt element,
så vi søge gennem

54
00:02:38,576 --> 00:02:41,740
og vi finder, at seks er
mindste, og i virkeligheden, eneste element.

55
00:02:41,740 --> 00:02:44,906
Og så kan vi konstatere, at det er sorteret.

56
00:02:44,906 --> 00:02:47,530
Og nu har vi skiftet vores matrix
fra at være helt usorterede

57
00:02:47,530 --> 00:02:52,660
i rødt, helt sorteres
i blå, ved hjælp af udvælgelse slags.

58
00:02:52,660 --> 00:02:54,920
>> Så hvad er den værst tænkelige scenarie her?

59
00:02:54,920 --> 00:02:57,830
Godt i absolut værste
tilfælde har vi at kigge over

60
00:02:57,830 --> 00:03:02,170
alle elementerne i arrayet til
finde den mindste usorterede element,

61
00:03:02,170 --> 00:03:04,750
og vi er nødt til at gentage
denne proces n gange.

62
00:03:04,750 --> 00:03:09,090
Én gang for hvert element i arrayet
fordi kun vi, i denne algoritme,

63
00:03:09,090 --> 00:03:12,180
Sorter ét element ad gangen.

64
00:03:12,180 --> 00:03:13,595
>> Hvad er den bedste tænkelige scenarie?

65
00:03:13,595 --> 00:03:15,040
Jamen det er præcis det samme, ikke?

66
00:03:15,040 --> 00:03:18,440
Vi har faktisk stadig gå gennem
hvert enkelt element af arrayet

67
00:03:18,440 --> 00:03:22,040
med henblik på at bekræfte, at det er,
faktisk det mindste element.

68
00:03:22,040 --> 00:03:26,760
>> Så værste fald runtime, vi
nødt til at gentage en proces n gange,

69
00:03:26,760 --> 00:03:28,960
en gang for hver af n elementer.

70
00:03:28,960 --> 00:03:31,940
Og i bedste fald,
vi er nødt til at gøre det samme.

71
00:03:31,940 --> 00:03:35,340
>> Så tænker tilbage til vores
beregningsmæssige kompleksitet værktøjskasse,

72
00:03:35,340 --> 00:03:39,250
hvad tror du er den værste
tilfælde runtime til valg Sorter?

73
00:03:39,250 --> 00:03:41,840
Hvad tror du er den bedste
tilfælde runtime til valg Sorter?

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

75
00:03:44,760 --> 00:03:49,325
>> Vidste du gætte Big O n kvadreret,
og Big Omega n kvadreret?

76
00:03:49,325 --> 00:03:49,950
Du ville have ret.

77
00:03:49,950 --> 00:03:52,490
Det er, i virkeligheden,
værste fald og bedste fald køre

78
00:03:52,490 --> 00:03:55,100
gange, for udvælgelse slags.

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

80
00:03:56,260 --> 00:03:58,600
Det er CS50.

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