1
00:00:00,000 --> 00:00:02,826
>> [Musikwiedergabe]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: So Insertion Sort ist ein weiterer
Algorithmus, den wir verwenden können, um ein Array zu sortieren.

4
00:00:09,370 --> 00:00:12,350
Die Idee hinter diesem Algorithmus
ist es, Ihre sortiertes Array zu bauen

5
00:00:12,350 --> 00:00:19,670
an Ort und Stelle, Schaltelemente aus
die Art und Weise, wie Sie gehen, Raum zu machen.

6
00:00:19,670 --> 00:00:22,240
Das ist etwas anders
von der Auswahl sortieren oder Blase

7
00:00:22,240 --> 00:00:25,460
Sortieren, zum Beispiel, wo
wir die Anpassung der Standorte,

8
00:00:25,460 --> 00:00:26,910
wo wir machen Swaps.

9
00:00:26,910 --> 00:00:29,760
>> In diesem Fall, was wir eigentlich
Dabei ist Gleitelemente

10
00:00:29,760 --> 00:00:31,390
über, aus dem Weg.

11
00:00:31,390 --> 00:00:34,030
Wie funktioniert dieser Algorithmus
arbeiten in Pseudocode?

12
00:00:34,030 --> 00:00:37,646
Nun lassen Sie uns einfach sagen, dass die willkürlich
erste Element des Array sortiert.

13
00:00:37,646 --> 00:00:38,770
Wir bauen sie an Ort und Stelle.

14
00:00:38,770 --> 00:00:42,660
>> Wir gonna ein Element zu gehen zu einem Zeitpunkt, und
bauen, und so das erste, was sehen wir,

15
00:00:42,660 --> 00:00:43,890
ist ein Ein-Element-Array.

16
00:00:43,890 --> 00:00:47,720
Und per Definition ein One
Elementanordnung sortiert.

17
00:00:47,720 --> 00:00:50,850
>> Dann werden wir diesen Vorgang wiederholen until--
wir werden den folgenden Prozess wiederholen

18
00:00:50,850 --> 00:00:52,900
bis alle Elemente sortiert werden.

19
00:00:52,900 --> 00:00:57,770
Sehen Sie in der nächsten unsortierte Element und
legen Sie sie in der sortierten Teil,

20
00:00:57,770 --> 00:01:01,209
indem die erforderliche Anzahl
Elemente aus dem Weg.

21
00:01:01,209 --> 00:01:03,750
Hoffentlich Visualisierung
wird Ihnen helfen, genau sehen, was ist

22
00:01:03,750 --> 00:01:05,980
los mit Insertion Sort.

23
00:01:05,980 --> 00:01:08,010
>> Also noch einmal, hier ist unsere
gesamten unsortierten Array,

24
00:01:08,010 --> 00:01:10,970
alle Elemente in rot angezeigt.

25
00:01:10,970 --> 00:01:13,320
Und lassen Sie uns folgen Sie den
Schritte unserer Pseudocode.

26
00:01:13,320 --> 00:01:16,970
Das erste, was wir tun, ist, wir als die
das erste Element des Arrays, sortiert.

27
00:01:16,970 --> 00:01:20,920
Also sind wir nur gonna sagen
fünf, du bist jetzt sortiert.

28
00:01:20,920 --> 00:01:24,570
>> Dann freuen wir bei der nächsten
unsortierten Element des Arrays

29
00:01:24,570 --> 00:01:27,610
und wir möchten, dass zum Einfügen
in die sortierte Abschnitt,

30
00:01:27,610 --> 00:01:29,750
indem Elemente über.

31
00:01:29,750 --> 00:01:33,470
So dass zwei der nächste unsortierten
Element des Arrays.

32
00:01:33,470 --> 00:01:36,250
Klar ist es, bevor das angehört
fünf, also was wir tun

33
00:01:36,250 --> 00:01:41,580
ist eine Art halten zwei beiseite für eine zweite,
verlagern fünf vorbei, und dann legen Sie zwei

34
00:01:41,580 --> 00:01:43,210
vor fünf, wo man gehen sollte.

35
00:01:43,210 --> 00:01:45,280
Und jetzt können wir sagen, dass zwei sortiert ist.

36
00:01:45,280 --> 00:01:48,400
>> So wie Sie sehen können, bisher haben wir nur
sah zwei Elemente des Arrays.

37
00:01:48,400 --> 00:01:50,600
Wir haben nicht die gesuchte
Ruhe überhaupt, aber wir haben

38
00:01:50,600 --> 00:01:54,582
habe diese beiden Elemente sortiert nach
Weg des Schaltmechanismus.

39
00:01:54,582 --> 00:01:56,410
>> So dass wir den Prozess zu wiederholen.

40
00:01:56,410 --> 00:01:58,850
Sehen Sie in der nächsten unsortierten
Element, das ist eine.

41
00:01:58,850 --> 00:02:04,010
Lassen Sie uns zu halten, dass abgesehen für eine zweite,
verschieben alles vorbei, und legte eine

42
00:02:04,010 --> 00:02:05,570
wo es gehen sollte.

43
00:02:05,570 --> 00:02:08,110
>> Auch noch, immer nur haben wir
sah ein, zwei und fünf.

44
00:02:08,110 --> 00:02:12,480
Wir wissen nicht, was noch kommt,
aber wir haben diese drei Elemente sortiert.

45
00:02:12,480 --> 00:02:16,030
>> Weiter unsortierte Element
drei, so dass wir es beiseite stellen.

46
00:02:16,030 --> 00:02:18,200
Wir werden über verschieben, was wir
müssen die, diesmal

47
00:02:18,200 --> 00:02:21,820
ist nicht alles wie in der vorherigen
zwei Fälle, es ist nur die Fünf.

48
00:02:21,820 --> 00:02:25,440
Und dann werden wir drei in kleben,
zwischen den beiden und der fünf.

49
00:02:25,440 --> 00:02:27,849
>> Six ist der nächste unsortierten
Element mit dem Array.

50
00:02:27,849 --> 00:02:31,140
Und in der Tat sechs größer als fünf ist, so dass
wir brauchen noch nicht einmal, um jede Swapping zu tun.

51
00:02:31,140 --> 00:02:35,710
Wir können nur tack sechs rechts auf
das Ende der sortierten Abschnitt.

52
00:02:35,710 --> 00:02:38,270
>> Schließlich ist die vier
letzten unsortierte Element.

53
00:02:38,270 --> 00:02:42,060
So werden wir es beiseite, verschieben über
die Elemente, die wir brauchen, um zu verschieben über,

54
00:02:42,060 --> 00:02:43,780
und setzen Sie dann vier, wo es hingehört.

55
00:02:43,780 --> 00:02:46,400
Und jetzt schauen, haben wir sort
aller Elemente.

56
00:02:46,400 --> 00:02:48,150
Beachten Sie, mit Einlege
Sortieren, haben wir nicht

57
00:02:48,150 --> 00:02:50,240
hin und her über das Feld zu gehen.

58
00:02:50,240 --> 00:02:54,720
Wir waren nur über das Feld
eine Zeit, und wir verschoben Dinge

59
00:02:54,720 --> 00:02:59,870
dass wir schon begegnet, um
um Platz für die neuen Elemente bilden.

60
00:02:59,870 --> 00:03:02,820
>> Also, was ist der schlimmste Fall
Szenario mit Insertion Sort?

61
00:03:02,820 --> 00:03:05,090
Im schlimmsten Fall wird die
Array in umgekehrter Reihenfolge.

62
00:03:05,090 --> 00:03:11,180
Sie haben zu jeder der n Elemente verschieben
bis n Positionen, jedes einzelne Mal, wenn wir

63
00:03:11,180 --> 00:03:12,880
machen eine Insertion.

64
00:03:12,880 --> 00:03:15,720
Das ist eine Menge der Verschiebung.

65
00:03:15,720 --> 00:03:18,014
>> Im besten Fall, die
Array ist perfekt sortiert.

66
00:03:18,014 --> 00:03:20,680
Und ein bisschen wie, was passiert
mit fünf und sechs im Beispiel

67
00:03:20,680 --> 00:03:23,779
wo wir nur tack sie auf
ohne dass eine Verlagerung zu tun,

68
00:03:23,779 --> 00:03:24,820
wir würden im Wesentlichen tun.

69
00:03:24,820 --> 00:03:27,560
>> Wenn Sie sich vorstellen, dass unsere
Array war eins bis sechs,

70
00:03:27,560 --> 00:03:29,900
wir würden durch starten
erklärte man sortiert.

71
00:03:29,900 --> 00:03:33,300
Zwei kommt nach einer so können wir einfach
sagen, OK, gut ein und zwei sortiert sind.

72
00:03:33,300 --> 00:03:36,190
Drei kommt nach zwei so, OK,
eins und zwei und drei werden sortiert.

73
00:03:36,190 --> 00:03:39,590
>> Wir sind nicht irgendwelche Swaps, wir sind
Mitnahme dieses willkürliche Linie

74
00:03:39,590 --> 00:03:42,460
zwischen sortiert und unsortiert, wie wir gehen.

75
00:03:42,460 --> 00:03:46,646
So wirksam wie die in dem Beispiel hat,
Drehelemente blau, wie wir vorgehen.

76
00:03:46,646 --> 00:03:48,270
Also, was ist der schlimmste Fall der Laufzeit, dann?

77
00:03:48,270 --> 00:03:51,854
Denken Sie daran, wenn wir jedes verschieben
die n-Elemente möglicherweise n Positionen,

78
00:03:51,854 --> 00:03:54,020
hoffentlich, das Ihnen
eine Idee, die im schlimmsten Fall

79
00:03:54,020 --> 00:03:57,770
Laufzeit ist Big O n quadriert.

80
00:03:57,770 --> 00:04:00,220
>> Wenn das Array vollkommen
sortiert, alles was wir tun müssen,

81
00:04:00,220 --> 00:04:04,480
wird bei jedem einzelnen Element zu suchen
einmal, und dann sind wir fertig.

82
00:04:04,480 --> 00:04:08,440
Also im besten Fall ist es Omega der n.

83
00:04:08,440 --> 00:04:09,490
>> Ich bin Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Dies ist CS50.

85
00:04:11,760 --> 00:04:13,119