1
00:00:00,000 --> 00:00:05,726
>> [Muziek]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Selection sort is een
algoritme dat, zoals je zou verwachten,

3
00:00:08,600 --> 00:00:10,470
sorteert een set van elementen.

4
00:00:10,470 --> 00:00:12,470
En algoritme recall
is een set van stap-voor-stap

5
00:00:12,470 --> 00:00:15,260
instructies voor het uitvoeren van een taak.

6
00:00:15,260 --> 00:00:17,580
>> In de selectie sorteren
basisidee is dit,

7
00:00:17,580 --> 00:00:22,080
vindt de kleinste ongesorteerd element en
toevoegen aan het einde van de gesorteerde lijst.

8
00:00:22,080 --> 00:00:26,970
Effectief wat dit doet is build
een gesorteerde lijst, één element tegelijk.

9
00:00:26,970 --> 00:00:29,800
Het af te breken om pseudocode
we dit algoritme vermelden

10
00:00:29,800 --> 00:00:34,490
als volgt, herhaal dit tot
geen ongesorteerde elementen blijven.

11
00:00:34,490 --> 00:00:38,660
Doorzoek de ongesorteerde
gegevens aan de kleinste waarde te vinden,

12
00:00:38,660 --> 00:00:44,130
dan wisselen de kleinste waarde met de
eerste element van het ongesorteerde deel.

13
00:00:44,130 --> 00:00:47,130
>> Het kan helpen om dit te visualiseren,
dus laten we eens een kijkje op deze.

14
00:00:47,130 --> 00:00:49,710
Dus dit, ik beweer, is een
ongesorteerde array en ik heb

15
00:00:49,710 --> 00:00:53,040
aangegeven dat zij door aan te geven dat alle
van de elementen zijn rood gekleurd,

16
00:00:53,040 --> 00:00:54,420
ze zijn nog niet opgelost.

17
00:00:54,420 --> 00:00:57,670
Dit is de gehele
ongesorteerde deel van de array.

18
00:00:57,670 --> 00:01:02,020
>> Dus laten we gaan door de stappen van
selectie sorteren op deze array te sorteren.

19
00:01:02,020 --> 00:01:05,296
Dus nogmaals, we gaan herhalen
tot er geen ongesorteerde elementen blijven.

20
00:01:05,296 --> 00:01:07,920
We gaan zoeken via de
gegevens aan de kleinste waarde te vinden,

21
00:01:07,920 --> 00:01:11,990
en wisselen die waarde met
eerste element van het ongesorteerde deel.

22
00:01:11,990 --> 00:01:14,380
>> Nu, nogmaals, de hele
array is de ongesorteerde deel.

23
00:01:14,380 --> 00:01:16,534
Alle rode elementen zijn ongesorteerd.

24
00:01:16,534 --> 00:01:18,700
Dus zoeken we door en
vinden we de kleinste waarde.

25
00:01:18,700 --> 00:01:20,533
We beginnen bij het begin,
gaan we naar het einde,

26
00:01:20,533 --> 00:01:23,630
vinden we de kleinste waarde één.

27
00:01:23,630 --> 00:01:24,860
Dus dat is deel één.

28
00:01:24,860 --> 00:01:29,440
En dan deel twee, wisselen die waarde met
het eerste element van het ongesorteerde deel,

29
00:01:29,440 --> 00:01:31,340
of de eerste rode element.

30
00:01:31,340 --> 00:01:34,980
>> In dit geval zou dat
vijf, dus we ruilen een en vijf.

31
00:01:34,980 --> 00:01:37,320
Als we dat doen, kunnen we
visueel te zien dat we hebben

32
00:01:37,320 --> 00:01:41,260
bewoog de kleinste gewaardeerd element
van de matrix, aan het begin.

33
00:01:41,260 --> 00:01:43,920
Effectief sorteren van dat element.

34
00:01:43,920 --> 00:01:47,520
>> En zo kunnen we wel bevestigen
en verklaren dat men, wordt gesorteerd.

35
00:01:47,520 --> 00:01:52,080
En dus zullen we de gesorteerde gedeelte geven
van ons aanbod, door te kleuren blauw.

36
00:01:52,080 --> 00:01:53,860
>> Nu zijn we gewoon opnieuw herhaal het proces.

37
00:01:53,860 --> 00:01:57,430
We zoeken in de ongesorteerde deel van
de array om het kleinste element te vinden.

38
00:01:57,430 --> 00:01:59,000
In dit geval, het is twee.

39
00:01:59,000 --> 00:02:02,100
>> We wisselen die met de eerste
element van het ongesorteerde deel.

40
00:02:02,100 --> 00:02:05,540
In dit geval twee toevallig ook
het eerste element van het ongesorteerde deel.

41
00:02:05,540 --> 00:02:08,650
Zo wisselen we twee met zichzelf,
die eigenlijk alleen maar laat twee

42
00:02:08,650 --> 00:02:11,257
waar het is, en het is opgelost.

43
00:02:11,257 --> 00:02:13,840
Voortbordurend op, zoeken we door
het kleinste element te vinden.

44
00:02:13,840 --> 00:02:15,030
Het is drie.

45
00:02:15,030 --> 00:02:17,650
We ruilen met het eerste
element, dat vijf.

46
00:02:17,650 --> 00:02:19,450
En nu drie wordt gesorteerd.

47
00:02:19,450 --> 00:02:22,440
>> We doorzoeken opnieuw, en we
vind het kleinste element is vier.

48
00:02:22,440 --> 00:02:28,070
We ruilen met het eerste element van de
ongesorteerd deel, en nu vier wordt gesorteerd.

49
00:02:28,070 --> 00:02:29,910
>> We vinden dat de vijf is
het kleinste element.

50
00:02:29,910 --> 00:02:32,900
We ruilen met het eerste
element van het ongesorteerde deel.

51
00:02:32,900 --> 00:02:34,740
En nu vijf wordt gesorteerd.

52
00:02:34,740 --> 00:02:36,660
>> En dan tot slot, onze
ongesorteerde deel bestaat

53
00:02:36,660 --> 00:02:38,576
van slechts één element,
dus we zoeken door middel van

54
00:02:38,576 --> 00:02:41,740
en wij vinden dat zes is de
kleinst, en in feite slechts element.

55
00:02:41,740 --> 00:02:44,906
En dan kunnen we stellen dat het wordt gesorteerd.

56
00:02:44,906 --> 00:02:47,530
En nu hebben we ons aanbod overgestapt
volledig wordt ongesorteerd

57
00:02:47,530 --> 00:02:52,660
rood, volledig gesorteerd
in blauw, met selectie sorteren.

58
00:02:52,660 --> 00:02:54,920
>> Dus wat is het worst case scenario hier?

59
00:02:54,920 --> 00:02:57,830
Welnu, in de absolute slechtste
geval is, moeten we kijken over

60
00:02:57,830 --> 00:03:02,170
alle elementen van de array
vindt de kleinste ongesorteerd element,

61
00:03:02,170 --> 00:03:04,750
en we moeten herhalen
Dit proces n keer.

62
00:03:04,750 --> 00:03:09,090
Eenmaal voor elk element van de array
want alleen wij in dit algoritme

63
00:03:09,090 --> 00:03:12,180
sort één element op het moment.

64
00:03:12,180 --> 00:03:13,595
>> Wat is de beste case scenario?

65
00:03:13,595 --> 00:03:15,040
Nou het is precies hetzelfde, toch?

66
00:03:15,040 --> 00:03:18,440
We hebben eigenlijk nog te doorlopen
elk element van de array

67
00:03:18,440 --> 00:03:22,040
om te bevestigen dat het,
in feite het kleinste element.

68
00:03:22,040 --> 00:03:26,760
>> Dus het ergste geval runtime, we
moet een proces n keer herhalen,

69
00:03:26,760 --> 00:03:28,960
eenmaal voor elk van de n elementen.

70
00:03:28,960 --> 00:03:31,940
En in het beste geval,
we hebben om hetzelfde te doen.

71
00:03:31,940 --> 00:03:35,340
>> Dus denken terug naar onze
computationele complexiteit toolbox,

72
00:03:35,340 --> 00:03:39,250
wat denk je dat is het ergste
Bij runtime voor de selectie sorteren?

73
00:03:39,250 --> 00:03:41,840
Wat denk je dat is de beste
Bij runtime voor de selectie sorteren?

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

75
00:03:44,760 --> 00:03:49,325
>> Hebt u raden Big O n kwadraat,
en Big Omega n kwadraat?

76
00:03:49,325 --> 00:03:49,950
Je zou gelijk hebben.

77
00:03:49,950 --> 00:03:52,490
Dit zijn in feite de
worst case en best case run

78
00:03:52,490 --> 00:03:55,100
tijden, voor de selectie sorteren.

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

80
00:03:56,260 --> 00:03:58,600
Dit is CS50.

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