1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Sort dodany]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Harvard University]

3
00:00:04,240 --> 00:00:07,290
[To jest CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Rzućmy okiem na sortowanie wstawiania, algorytm podejmowania listę numerów i sortowania ich.

5
00:00:13,060 --> 00:00:18,300
Algorytm, pamiętasz, to po prostu krok po kroku procedurę realizacji zadania.

6
00:00:18,300 --> 00:00:23,640
Podstawową ideą rodzaju wstawiania, jest podzielenie naszej listy na dwie części,

7
00:00:23,640 --> 00:00:26,580
posortowane część i unsorted porcję.

8
00:00:26,580 --> 00:00:29,290
>> Na każdym etapie algorytmu numer przeniesiony

9
00:00:29,290 --> 00:00:32,439
z nieposortowanych części do sortowanie części

10
00:00:32,439 --> 00:00:35,680
aż w końcu cała lista jest posortowana.

11
00:00:35,680 --> 00:00:43,340
Oto lista sześciu nieposortowanych liczb - 23, 42, 4, 16, 8, i 15.

12
00:00:43,340 --> 00:00:47,680
Ponieważ numery te nie są w porządku rosnącym, są one sortowane.

13
00:00:47,680 --> 00:00:53,890
Ponieważ nie zaczęli jeszcze sortowania, będziemy rozpatrywać wszystkie sześć elementów naszej niesortowanych porcję.

14
00:00:53,890 --> 00:00:59,270
>> Kiedy rozpocząć sortowanie, umieścimy te posortowane numery do lewej tych.

15
00:00:59,270 --> 00:01:03,600
Więc zacznijmy od 23, pierwszy element w naszej liście.

16
00:01:03,600 --> 00:01:06,930
Nie mamy żadnych elementów w naszym sortowanie części jeszcze

17
00:01:06,930 --> 00:01:12,460
więc niech po prostu uważają 23 za początek i koniec naszej sortowanie części.

18
00:01:12,460 --> 00:01:16,510
Teraz nasza posortowane część ma jeden numer, 23,

19
00:01:16,510 --> 00:01:20,260
i nasz unsorted część ma te pięć numerów.

20
00:01:20,260 --> 00:01:27,320
Zróbmy teraz wstawić następny numer naszego nieposortowanych części, 42, do sortowanie części.

21
00:01:27,320 --> 00:01:35,930
>> Aby to zrobić, musimy porównać 42 do 23 - jedyny element w naszej sortowanie części tak daleko.

22
00:01:35,930 --> 00:01:41,980
Czterdziestu dwóch jest większy niż 23, dzięki czemu można po prostu dołączyć do końca 42

23
00:01:41,980 --> 00:01:45,420
sortowanie z części listy. Great!

24
00:01:45,420 --> 00:01:51,850
Teraz nasz posortowane część ma dwa elementy, a nasze unsorted część ma cztery elementy.

25
00:01:51,850 --> 00:01:57,200
Więc, teraz przenieść się do 4, następny element w nieposortowanych porcji.

26
00:01:57,200 --> 00:02:00,230
Tak więc, w tym, gdzie powinna być umieszczona w sortowanie części?

27
00:02:00,230 --> 00:02:04,220
>> Pamiętaj, że chcesz umieścić ten numer w uporządkowanej kolejności

28
00:02:04,220 --> 00:02:08,680
więc nasz posortowane część pozostaje prawidłowo posortowane w każdym czasie.

29
00:02:08,680 --> 00:02:14,380
Jeśli to 4 na prawo od 42, to nasza lista będzie w porządku.

30
00:02:14,380 --> 00:02:18,380
No to kontynuować ruch od prawej do lewej w naszej części sortowania.

31
00:02:18,380 --> 00:02:23,260
Jak iść, niech przesunąć każdą liczbę w dół w miejscu, aby zrobić miejsce na nowy numer.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 jest mniejsza niż 23, więc nie jesteśmy w stanie umieścić go tutaj, albo.

33
00:02:31,740 --> 00:02:34,480
Przejdźmy do 23 prawo o jedno miejsce.

34
00:02:36,500 --> 00:02:43,120
>> Oznacza to, że chcielibyśmy, aby umieścić 4 do pierwszego gniazda w sortowanie części.

35
00:02:43,120 --> 00:02:46,300
Zauważ, jak to miejsce na liście było już puste,

36
00:02:46,300 --> 00:02:51,120
ponieważ byliśmy w ruchu sortowanie elementów w dół jak już napotkał je.

37
00:02:51,120 --> 00:02:52,740
Dobrze. Tak, jesteśmy w połowie drogi.

38
00:02:52,740 --> 00:02:57,990
Kontynuujmy nasz algorytm wkładając 16 do sortowanie części.

39
00:02:59,260 --> 00:03:03,820
Szesnaście jest mniejsza niż 42, to powiedzmy 42 do przesunięcia w prawo.

40
00:03:05,700 --> 00:03:10,190
Sixteen jest również mniejsza niż 23, więc niech także przesunąć ten element.

41
00:03:11,790 --> 00:03:20,820
>> Teraz, 16 jest większy niż 4. Tak, wygląda na to, chcemy wstawić 16 między 4 i 23.

42
00:03:20,820 --> 00:03:24,620
Podczas przenoszenia przez sortowanie części listy, z prawej do lewej,

43
00:03:24,620 --> 00:03:29,160
4 jest pierwszy numer widzimy, że jest mniejsza niż liczba

44
00:03:29,160 --> 00:03:31,540
chcemy wstawić.

45
00:03:31,540 --> 00:03:35,820
Tak, teraz możemy włożyć 16 do tego pustego gniazda,

46
00:03:35,820 --> 00:03:40,520
które, pamiętaj, stworzyliśmy przez poruszających elementów w części sortowania ponad

47
00:03:40,520 --> 00:03:43,340
jak już napotkał je.

48
00:03:43,340 --> 00:03:47,900
>> Dobrze. Teraz mamy cztery posortowane elementy i dwa nieposortowane elementy.

49
00:03:47,900 --> 00:03:51,600
Więc przejdźmy do 8 do sortowanie części.

50
00:03:51,600 --> 00:03:55,010
Osiem jest mniej niż 42.

51
00:03:55,010 --> 00:03:56,940
Osiem jest mniejsza niż 23.

52
00:03:56,940 --> 00:04:00,230
I 8 jest mniejsza niż 16.

53
00:04:00,230 --> 00:04:03,110
8, ale jest większe niż 4.

54
00:04:03,110 --> 00:04:07,280
Więc chcielibyśmy włożyć 8 między 4 i 16.

55
00:04:09,070 --> 00:04:13,650
A teraz mamy tylko jeden element w lewo sort - 15.

56
00:04:13,950 --> 00:04:16,589
Piętnaście jest mniejsza niż 42,

57
00:04:16,589 --> 00:04:19,130
Piętnaście jest mniejsza niż 23.

58
00:04:19,130 --> 00:04:21,750
I 15 jest mniejsza niż 16.

59
00:04:21,750 --> 00:04:24,810
Ale 15 jest większa niż 8.

60
00:04:24,810 --> 00:04:27,440
>> Tak, o to, gdzie chcemy, aby nasz końcowy wstawiania.

61
00:04:28,770 --> 00:04:30,330
I gotowe.

62
00:04:30,330 --> 00:04:33,540
Nie mamy więcej elementów w nieposortowanych porcji

63
00:04:33,540 --> 00:04:36,670
i nasz posortowane część znajduje się w prawidłowej kolejności.

64
00:04:36,670 --> 00:04:40,270
Liczby są sortowane od najmniejszego do największego.

65
00:04:40,270 --> 00:04:44,330
Więc, rzućmy okiem na niektóre Pseudokod opisującym kroki właśnie ruchu.

66
00:04:46,760 --> 00:04:51,740
>> W linii 1, widzimy, że musimy iterować każdy element na liście

67
00:04:51,740 --> 00:04:57,060
z wyjątkiem pierwszego, od pierwszego elementu w niesegregowanych części po prostu się

68
00:04:57,060 --> 00:05:00,220
Pierwszy element w posortowanej części.

69
00:05:00,220 --> 00:05:06,320
Na liniach 2 i 3, jesteśmy śledzenia naszego miejsca w nieposortowanych porcji.

70
00:05:06,320 --> 00:05:10,450
Element reprezentuje liczbę jesteśmy obecnie porusza się w sortowanie części,

71
00:05:10,450 --> 00:05:15,600
oraz j reprezentuje nasz indeks w nieposortowanych porcji.

72
00:05:15,600 --> 00:05:20,980
>> W linii 4, jesteśmy iteracja posortowanej części od prawej do lewej.

73
00:05:20,980 --> 00:05:26,010
Chcemy zatrzymać Iterowanie raz elementu z lewej naszej aktualnej pozycji

74
00:05:26,010 --> 00:05:30,050
jest mniejsza niż element staramy się wstawić.

75
00:05:30,050 --> 00:05:35,600
W linii 5, mamy przesunięcie każdy element możemy spotkać o jedno miejsce w prawo.

76
00:05:35,600 --> 00:05:40,950
W ten sposób będziemy mieć wolną przestrzeń, aby wstawić do kiedy znajdziemy pierwszy element

77
00:05:40,950 --> 00:05:44,080
mniej niż element jesteśmy w ruchu.

78
00:05:44,080 --> 00:05:50,800
W linii 6, my aktualizujemy nasze licznik nadal poruszać w lewo przez sortowanie części.

79
00:05:50,800 --> 00:05:56,860
Wreszcie, w linii 7 mamy wstawienie elementu do sortowanie części listy.

80
00:05:56,860 --> 00:06:00,020
>> Wiemy, że to jest w porządku, aby wstawić do j pozycji,

81
00:06:00,020 --> 00:06:05,360
bo my już przeniesiony element, które było tam jedno miejsce w prawo.

82
00:06:05,360 --> 00:06:09,460
Pamiętaj, że idziemy przez sortowanie części od prawej do lewej,

83
00:06:09,460 --> 00:06:13,960
ale idziemy przez nieposortowanych części od lewej do prawej.

84
00:06:13,960 --> 00:06:19,090
Dobrze. Spróbujmy teraz przyjrzeć się, jak długo działa, że ​​algorytm wziął.

85
00:06:19,090 --> 00:06:25,300
Zaczniemy zadawać sobie pytanie, jak długo trwa ten algorytm, aby uruchomić w najgorszym przypadku.

86
00:06:25,300 --> 00:06:29,040
Przypomnijmy, że reprezentujemy ten czas pracy z Big notacji O.

87
00:06:32,530 --> 00:06:38,500
W celu uporządkowania naszej listy, mieliśmy do iteracyjnego elementy w nieposortowanych porcji

88
00:06:38,500 --> 00:06:43,430
i dla każdego z tych elementów, potencjalnie ponad wszystkich elementów w posortowanej części.

89
00:06:43,430 --> 00:06:47,950
Intuicyjnie, to brzmi jak (n ^ 2) O pracy.

90
00:06:47,950 --> 00:06:51,840
>> Patrząc na Pseudokod mamy pętlę zagnieżdżona w innej pętli

91
00:06:51,840 --> 00:06:55,290
które rzeczywiście brzmi jak (n ^ 2) O pracy.

92
00:06:55,290 --> 00:07:01,590
Jednak posortowane część listy nie zawierają całą listę, aż do samego końca.

93
00:07:01,590 --> 00:07:06,920
Mimo, że można potencjalnie wstawić nowy element na samym początku części sortowanie

94
00:07:06,920 --> 00:07:09,320
na każdej iteracji algorytmu,

95
00:07:09,320 --> 00:07:14,500
co oznacza, że ​​musimy patrzeć na każdy element aktualnie w sortowanie części.

96
00:07:14,500 --> 00:07:20,090
Tak, to znaczy, moglibyśmy potencjalnie wykonać jedno porównanie do drugiego elementu,

97
00:07:20,090 --> 00:07:24,660
dwa porównania dla trzeciego elementu, i tak dalej.

98
00:07:24,660 --> 00:07:32,480
Tak więc, całkowita ilość stopni jest suma liczb od 1 do długości listy minus 1..

99
00:07:32,480 --> 00:07:35,240
Możemy reprezentować to z sumowaniu.

100
00:07:41,170 --> 00:07:47,270
>> Nie pójdziemy do podsumowań, ale to okazuje się, że to podsumowanie jest równa

101
00:07:47,270 --> 00:07:57,900
N (N - 1) w ciągu 2, co odpowiada n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Kiedy mówimy o asymptotycznej wykonywania,

103
00:08:00,800 --> 00:08:05,170
to n ^ 2 termin będzie dominować ten n kadencję.

104
00:08:05,170 --> 00:08:11,430
Tak więc, w pewnym sensie wstawiania jest Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Co zrobić, jeśli zabrakło sortowanie wstawiania na już posortowanej listy.

106
00:08:16,150 --> 00:08:20,960
W tym przypadku, będziemy po prostu budować posortowaną część od lewej do prawej.

107
00:08:20,960 --> 00:08:25,050
Tak, to musimy tylko na zlecenie n kroków.

108
00:08:25,050 --> 00:08:29,740
>> Oznacza to, że rodzaj wstawiania ma najlepsze case wydajność n

109
00:08:29,740 --> 00:08:34,130
które stanowią w Ω (n).

110
00:08:34,130 --> 00:08:36,190
I to na sortowanie wstawiania

111
00:08:36,190 --> 00:08:40,429
tylko jeden z wielu algorytmów możemy użyć, aby posortować listę.

112
00:08:40,429 --> 00:08:43,210
Nazywam się Tommy, i to jest CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, po prostu nie mogę przestać, że po uruchomieniu.

115
00:09:01,620 --> 00:09:04,760
Oh, to zrobiliśmy - Boom! >>