1
00:00:00,000 --> 00:00:05,726
>> [MUSIK SPELA]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Urval sort är en
algoritm som, som man kan förvänta sig,

3
00:00:08,600 --> 00:00:10,470
sorterar en rad faktorer.

4
00:00:10,470 --> 00:00:12,470
Och algoritm återkallande
är ett steg-för-steg set

5
00:00:12,470 --> 00:00:15,260
instruktioner för att fylla en uppgift.

6
00:00:15,260 --> 00:00:17,580
>> I val sortera
Grundidén är detta,

7
00:00:17,580 --> 00:00:22,080
hitta minsta osorterat elementet och
lägga till det i slutet av den sorterade listan.

8
00:00:22,080 --> 00:00:26,970
Effektivt vad detta innebär är build
en sorterad lista, ett element åt gången.

9
00:00:26,970 --> 00:00:29,800
Bryta ner det till pseudokod
Vi kunde konstatera denna algoritm

10
00:00:29,800 --> 00:00:34,490
enligt följande, upprepa detta tills
inga osorterade element kvar.

11
00:00:34,490 --> 00:00:38,660
Söka igenom osorterade
data för att hitta det minsta värdet,

12
00:00:38,660 --> 00:00:44,130
sedan byta det minsta värdet med
första delen av osorterade delen.

13
00:00:44,130 --> 00:00:47,130
>> Det kan hjälpa att visualisera detta,
så låt oss ta en titt på detta.

14
00:00:47,130 --> 00:00:49,710
Så det här, jag hävdar, är en
osorterade array och jag har

15
00:00:49,710 --> 00:00:53,040
indikeras det genom att ange att alla
av elementen är färgade rött,

16
00:00:53,040 --> 00:00:54,420
de ännu inte sorteras.

17
00:00:54,420 --> 00:00:57,670
Detta är hela
osorterat del av matrisen.

18
00:00:57,670 --> 00:01:02,020
>> Så låt oss gå igenom stegen
val Sortera för att sortera arrayen.

19
00:01:02,020 --> 00:01:05,296
Så återigen, vi ska upprepa
tills inga osorterade element kvar.

20
00:01:05,296 --> 00:01:07,920
Vi ska söka igenom den
data för att hitta det minsta värdet,

21
00:01:07,920 --> 00:01:11,990
och sedan byta detta värde med
första delen av osorterade delen.

22
00:01:11,990 --> 00:01:14,380
>> Just nu, återigen, hela
array är den osorterade delen.

23
00:01:14,380 --> 00:01:16,534
Alla de röda elementen är osorterade.

24
00:01:16,534 --> 00:01:18,700
Så vi söker igenom och
Vi hittar det lägsta värdet.

25
00:01:18,700 --> 00:01:20,533
Vi börjar från början,
vi gå till slutet,

26
00:01:20,533 --> 00:01:23,630
finner vi det minsta värdet är, en.

27
00:01:23,630 --> 00:01:24,860
Så det är en del ett.

28
00:01:24,860 --> 00:01:29,440
Och då en del två, byta detta värde med
den första delen av den osorterade delen,

29
00:01:29,440 --> 00:01:31,340
eller den första röda elementet.

30
00:01:31,340 --> 00:01:34,980
>> I detta fall som skulle vara
fem, så vi byter en och fem.

31
00:01:34,980 --> 00:01:37,320
När vi gör detta, vi kan
visuellt se att vi har

32
00:01:37,320 --> 00:01:41,260
flyttade minsta värderade elementet
av arrayen, till allra första början.

33
00:01:41,260 --> 00:01:43,920
Effektivt sortera det elementet.

34
00:01:43,920 --> 00:01:47,520
>> Och så vi kan verkligen bekräfta
och påstår att man, sorteras.

35
00:01:47,520 --> 00:01:52,080
Och så ska vi ange den sorterade delen
av vårt utbud, genom att färga det blått.

36
00:01:52,080 --> 00:01:53,860
>> Nu har vi bara upprepa processen igen.

37
00:01:53,860 --> 00:01:57,430
Vi söka igenom osorterade delen av
uppsättningen för att hitta det minsta elementet.

38
00:01:57,430 --> 00:01:59,000
I det här fallet är det två.

39
00:01:59,000 --> 00:02:02,100
>> Vi byter att med den första
del av osorterade delen.

40
00:02:02,100 --> 00:02:05,540
I det här fallet två också råkar vara
den första delen av den osorterade delen.

41
00:02:05,540 --> 00:02:08,650
Så vi byta två med sig själv,
som egentligen bara lämnar två

42
00:02:08,650 --> 00:02:11,257
där det är, och det är för sortering.

43
00:02:11,257 --> 00:02:13,840
Fortsätter vi söka igenom
att hitta det minsta elementet.

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

45
00:02:15,030 --> 00:02:17,650
Vi byter den med den första
element, vilket är fem.

46
00:02:17,650 --> 00:02:19,450
Och nu tre sorteras.

47
00:02:19,450 --> 00:02:22,440
>> Vi söker igenom igen, och vi
hitta det minsta elementet är fyra.

48
00:02:22,440 --> 00:02:28,070
Vi byta det med det första elementet i
osorterat del, och nu fyra sorteras.

49
00:02:28,070 --> 00:02:29,910
>> Vi finner att fem är
det minsta elementet.

50
00:02:29,910 --> 00:02:32,900
Vi byter den med den första
del av osorterade delen.

51
00:02:32,900 --> 00:02:34,740
Och nu fem sorteras.

52
00:02:34,740 --> 00:02:36,660
>> Och sedan slutligen, vår
osorterade delen består

53
00:02:36,660 --> 00:02:38,576
på bara ett enda element,
så vi söka igenom

54
00:02:38,576 --> 00:02:41,740
och vi tycker att sex är
minsta, och i själva verket bara element.

55
00:02:41,740 --> 00:02:44,906
Och då kan vi konstatera att den sorteras.

56
00:02:44,906 --> 00:02:47,530
Och nu har vi bytte vår array
från att vara helt osorterade

57
00:02:47,530 --> 00:02:52,660
i rött, helt sorteras
i blått, med hjälp av val slag.

58
00:02:52,660 --> 00:02:54,920
>> Så vad är det värsta scenariot här?

59
00:02:54,920 --> 00:02:57,830
Väl i absolut värsta
fallet, måste vi se över

60
00:02:57,830 --> 00:03:02,170
alla element i uppsättningen till
hitta minsta osorterat elementet,

61
00:03:02,170 --> 00:03:04,750
och vi måste upprepa
denna process n gånger.

62
00:03:04,750 --> 00:03:09,090
En gång för varje element i gruppen
eftersom vi bara, i denna algoritm,

63
00:03:09,090 --> 00:03:12,180
sortera ett element vid tidpunkten.

64
00:03:12,180 --> 00:03:13,595
>> Vad är det bästa scenariot?

65
00:03:13,595 --> 00:03:15,040
Jo det är exakt samma, eller hur?

66
00:03:15,040 --> 00:03:18,440
Vi har faktiskt fortfarande gå igenom
varje enskilt element i matrisen

67
00:03:18,440 --> 00:03:22,040
för att bekräfta att det är,
i själva verket, det minsta elementet.

68
00:03:22,040 --> 00:03:26,760
>> Så värsta fall runtime, vi
måste upprepa en process n gånger,

69
00:03:26,760 --> 00:03:28,960
en gång för var och en av n element.

70
00:03:28,960 --> 00:03:31,940
Och i bästa fall,
Vi måste göra detsamma.

71
00:03:31,940 --> 00:03:35,340
>> Så tänker tillbaka till vår
beräkningskomplexitet verktygslåda,

72
00:03:35,340 --> 00:03:39,250
vad tror du är det värsta
fall runtime för val sort?

73
00:03:39,250 --> 00:03:41,840
Vad tycker du är det bästa
fall runtime för val sort?

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

75
00:03:44,760 --> 00:03:49,325
>> Har du gissa Big O n kvadrat,
och Big Omega n kvadrat?

76
00:03:49,325 --> 00:03:49,950
Du skulle bli rätt.

77
00:03:49,950 --> 00:03:52,490
De är i själva verket
värsta fall och bästa fall kör

78
00:03:52,490 --> 00:03:55,100
tider, för val sort.

79
00:03:55,100 --> 00:03:56,260
>> Jag är Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Detta är CS50.

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