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

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Auswahl Art ist eine
Algorithmus, der, wie man erwarten könnte,

3
00:00:08,600 --> 00:00:10,470
sortiert eine Gruppe von Elementen.

4
00:00:10,470 --> 00:00:12,470
Und Algorithmus Rückruf
ist ein Schritt-für-Schritt-Set

5
00:00:12,470 --> 00:00:15,260
von Anweisungen zur Durchführung einer Aufgabe.

6
00:00:15,260 --> 00:00:17,580
>> In der Auswahl sortieren
Grundidee ist die,

7
00:00:17,580 --> 00:00:22,080
finden Sie das kleinste unsortierte Element und
es bis zum Ende der sortierten Liste hinzuzufügen.

8
00:00:22,080 --> 00:00:26,970
Effektiv, was das bedeutet ist build
eine sortierte Liste, ein Element zu einem Zeitpunkt.

9
00:00:26,970 --> 00:00:29,800
Zerlegung, um Pseudocode
könnten wir diesen Algorithmus angeben

10
00:00:29,800 --> 00:00:34,490
wie folgt, wiederholen Sie dies, bis
keine unsortierten Elemente bleiben.

11
00:00:34,490 --> 00:00:38,660
Suchen Sie in den unsortierten
Daten auf den kleinsten Wert zu finden,

12
00:00:38,660 --> 00:00:44,130
dann tauschen Sie den kleinsten Wert mit der
erste Element der unsortierten Teil.

13
00:00:44,130 --> 00:00:47,130
>> Es kann helfen, dies zu visualisieren,
so lassen Sie uns einen Blick auf diese.

14
00:00:47,130 --> 00:00:49,710
Also das, behaupte ich, ist ein
unsortierte Array und ich habe

15
00:00:49,710 --> 00:00:53,040
angedeutet durch die anzeigt, dass alle
der Elemente sind rot,

16
00:00:53,040 --> 00:00:54,420
sie sind noch nicht sortiert.

17
00:00:54,420 --> 00:00:57,670
Dies ist die gesamte
unsortierten Teil des Arrays.

18
00:00:57,670 --> 00:01:02,020
>> Lassen Sie uns also durch die Schritte gehen
Auswahl sort, um dieses Array zu sortieren.

19
00:01:02,020 --> 00:01:05,296
Also noch einmal, wir werden wiederholen
bis keine unsortierten Elemente bleiben.

20
00:01:05,296 --> 00:01:07,920
Wir werden Suchen Sie in den
Daten auf den kleinsten Wert zu finden,

21
00:01:07,920 --> 00:01:11,990
und dann tauschen Sie diesen Wert mit der
erste Element der unsortierten Teil.

22
00:01:11,990 --> 00:01:14,380
>> Gerade jetzt, wieder die gesamte
Array ist der unsortierten Teil.

23
00:01:14,380 --> 00:01:16,534
Alle roten Elemente sind unsortiert.

24
00:01:16,534 --> 00:01:18,700
So suchen wir durch und
finden wir den kleinsten Wert.

25
00:01:18,700 --> 00:01:20,533
Wir beginnen am Anfang,
Wir gehen bis zum Ende,

26
00:01:20,533 --> 00:01:23,630
wir finden, der kleinste Wert ist, ein.

27
00:01:23,630 --> 00:01:24,860
Also das ist ein Teil.

28
00:01:24,860 --> 00:01:29,440
Und dann Teil zwei, tauschen Sie diesen Wert mit
das erste Element des unsortierten Teil,

29
00:01:29,440 --> 00:01:31,340
oder die erste rot-Element.

30
00:01:31,340 --> 00:01:34,980
>> In diesem Fall wäre das
fünf, so tauschen wir ein und fünf.

31
00:01:34,980 --> 00:01:37,320
Wenn wir das tun, können wir
visuell sehen, dass wir

32
00:01:37,320 --> 00:01:41,260
bewegt den kleinsten Wert Element
des Arrays, an den Anfang.

33
00:01:41,260 --> 00:01:43,920
Effektiv Sortier dieses Element.

34
00:01:43,920 --> 00:01:47,520
>> Und so haben wir in der Tat bestätigen,
und erklären, dass man, sortiert ist.

35
00:01:47,520 --> 00:01:52,080
Und so werden wir den Teil, sortiert anzuzeigen
der unser Angebot, indem es Färbung blau.

36
00:01:52,080 --> 00:01:53,860
>> Jetzt müssen wir nur den Vorgang wiederholen.

37
00:01:53,860 --> 00:01:57,430
Wir suchen durch die unsortierten Teil
das Array, das kleinste Element zu finden.

38
00:01:57,430 --> 00:01:59,000
In diesem Fall ist es zwei.

39
00:01:59,000 --> 00:02:02,100
>> Wir tauschen, dass mit dem ersten
Element der unsortierten Teil.

40
00:02:02,100 --> 00:02:05,540
In diesem Fall geschieht, zwei auch zu sein
das erste Element des unsortierten Teil.

41
00:02:05,540 --> 00:02:08,650
Also haben wir tauschen zwei mit sich selbst,
was eigentlich nur zwei Blätter

42
00:02:08,650 --> 00:02:11,257
wo es ist, und es ist, sortiert.

43
00:02:11,257 --> 00:02:13,840
Weiter auf, durchsuchen wir
um das kleinste Element zu finden.

44
00:02:13,840 --> 00:02:15,030
Es ist drei.

45
00:02:15,030 --> 00:02:17,650
Wir tauschen Sie es mit dem ersten
Element, das fünf ist.

46
00:02:17,650 --> 00:02:19,450
Und jetzt drei sortiert ist.

47
00:02:19,450 --> 00:02:22,440
>> Wir suchen wieder durch, und wir
Finde das kleinste Element ist vier.

48
00:02:22,440 --> 00:02:28,070
Wir tauschen es mit dem ersten Element des
unsortierten Teil, und jetzt vier sortiert ist.

49
00:02:28,070 --> 00:02:29,910
>> Wir finden, dass fünf ist
das kleinste Element.

50
00:02:29,910 --> 00:02:32,900
Wir tauschen Sie es mit dem ersten
Element der unsortierten Teil.

51
00:02:32,900 --> 00:02:34,740
Und nun fünf sortiert ist.

52
00:02:34,740 --> 00:02:36,660
>> Und dann endlich unseren
unsortierten Teil besteht

53
00:02:36,660 --> 00:02:38,576
von nur einem einzelnen Element,
so dass wir durchsuchen

54
00:02:38,576 --> 00:02:41,740
und wir finden, dass sechs der
am kleinsten, und in der Tat nur Element.

55
00:02:41,740 --> 00:02:44,906
Und dann können wir feststellen, dass es sortiert ist.

56
00:02:44,906 --> 00:02:47,530
Und jetzt haben wir unser Angebot eingeschaltet
davor komplett unsortiert

57
00:02:47,530 --> 00:02:52,660
in rot, um vollständig sortiert
in blau, mit Auswahl sort.

58
00:02:52,660 --> 00:02:54,920
>> Also, was ist das schlimmste Szenario hier?

59
00:02:54,920 --> 00:02:57,830
Nun, in der absolute worst
Fall, müssen wir schauen über

60
00:02:57,830 --> 00:03:02,170
alle Elemente des Arrays
finden Sie das kleinste unsortierte Element,

61
00:03:02,170 --> 00:03:04,750
und wir haben zu wiederholen,
dieser Vorgang n-mal.

62
00:03:04,750 --> 00:03:09,090
Einmal für jedes Element des Arrays
weil nur wir in diesem Algorithmus,

63
00:03:09,090 --> 00:03:12,180
Art ein Element zur Zeit.

64
00:03:12,180 --> 00:03:13,595
>> Was ist der beste-Case-Szenario?

65
00:03:13,595 --> 00:03:15,040
Nun, es ist genau das gleiche, oder?

66
00:03:15,040 --> 00:03:18,440
Wir haben tatsächlich immer noch durch Schritt
Jedes einzelne Element des Arrays

67
00:03:18,440 --> 00:03:22,040
um zu bestätigen, dass es sich,
in der Tat, das kleinste Element.

68
00:03:22,040 --> 00:03:26,760
>> Also das Worst-Case-Laufzeit, die wir
haben, ein Verfahren zu n-mal zu wiederholen,

69
00:03:26,760 --> 00:03:28,960
einmal für jede der n Elemente.

70
00:03:28,960 --> 00:03:31,940
Und im besten Fall,
Wir haben das gleiche zu tun.

71
00:03:31,940 --> 00:03:35,340
>> So denken zurück zu unserem
Rechenkomplexität Toolbox

72
00:03:35,340 --> 00:03:39,250
was glauben Sie, ist das Schlimmste,
Bei der Laufzeit für die Auswahl sortieren?

73
00:03:39,250 --> 00:03:41,840
Was denken Sie ist der beste
Bei der Laufzeit für die Auswahl sortieren?

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

75
00:03:44,760 --> 00:03:49,325
>> Haben Sie erraten, Big O n quadriert,
und Big Omega von n quadriert?

76
00:03:49,325 --> 00:03:49,950
Sie würden Recht haben.

77
00:03:49,950 --> 00:03:52,490
Diejenigen sind, in der Tat, die
Worst-Case und Best Case Lauf

78
00:03:52,490 --> 00:03:55,100
Zeiten, für die Auswahl sortieren.

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

80
00:03:56,260 --> 00:03:58,600
Dies ist CS50.

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