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

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Tak Sortowanie przez wstawianie jest inny
Algorytm możemy użyć do sortowania tablicy.

4
00:00:09,370 --> 00:00:12,350
Ideą tego algorytmu
jest zbudowanie posortowaną tablicę

5
00:00:12,350 --> 00:00:19,670
w miejscu przesunięcie elementów z
sposób jak przejść, aby zrobić miejsce.

6
00:00:19,670 --> 00:00:22,240
To jest nieco inny
od wyboru rodzaju lub bańki

7
00:00:22,240 --> 00:00:25,460
sortowania, na przykład, gdy
mamy regulację położenia,

8
00:00:25,460 --> 00:00:26,910
gdzie robimy swapy.

9
00:00:26,910 --> 00:00:29,760
>> W tym przypadku to, co jesteśmy w rzeczywistości
robi to elementy ślizgowe

10
00:00:29,760 --> 00:00:31,390
powyżej, z drogi.

11
00:00:31,390 --> 00:00:34,030
Jak to algorytm
pracy w Pseudokod?

12
00:00:34,030 --> 00:00:37,646
Dobrze niech po prostu arbitralnie powiedzieć, że
Pierwszy element tablicy jest sortowana.

13
00:00:37,646 --> 00:00:38,770
Budujemy go w miejscu.

14
00:00:38,770 --> 00:00:42,660
>> Będziemy iść jeden element na raz i
budować, to i tak pierwsze co widzimy

15
00:00:42,660 --> 00:00:43,890
Jest to tablica jeden element.

16
00:00:43,890 --> 00:00:47,720
A z definicji, jednym
element tablicy jest sortowana.

17
00:00:47,720 --> 00:00:50,850
>> Potem powtórzyć ten proces until--
będziemy powtarzać następujący proces

18
00:00:50,850 --> 00:00:52,900
dopóki wszystkie elementy są klasyfikowane.

19
00:00:52,900 --> 00:00:57,770
Spójrz na następny nieposortowanego elementu i
włóż ją do części posortowanej,

20
00:00:57,770 --> 00:01:01,209
przez przeniesienie wymaganej liczby
z elementami z drogi.

21
00:01:01,209 --> 00:01:03,750
Mam nadzieję, że ta wizualizacja
pomoże Ci dokładnie zobaczyć, co jest

22
00:01:03,750 --> 00:01:05,980
dzieje z Sortowanie przez wstawianie.

23
00:01:05,980 --> 00:01:08,010
>> Więc jeszcze raz, tu jest nasz
Cały nieposortowane tablica,

24
00:01:08,010 --> 00:01:10,970
wszystkie elementy oznaczone na czerwono.

25
00:01:10,970 --> 00:01:13,320
I Prześledźmy
etapy naszej Pseudokod.

26
00:01:13,320 --> 00:01:16,970
Pierwszą rzeczą, jaką możemy zrobić, jest nazywamy
Pierwszy element tablicy, sortowane.

27
00:01:16,970 --> 00:01:20,920
Więc jesteśmy po prostu powie
pięć, jesteś teraz sortowane.

28
00:01:20,920 --> 00:01:24,570
>> Następnie patrzymy na następny
nieposortowane element tablicy

29
00:01:24,570 --> 00:01:27,610
i chcemy wstawić, że
w sortowanej porcji

30
00:01:27,610 --> 00:01:29,750
przez przesunięcie elementów ciągu.

31
00:01:29,750 --> 00:01:33,470
Więc dwa to kolejny nieposortowane
Element tablicy.

32
00:01:33,470 --> 00:01:36,250
Oczywiście należy przed
pięć, więc co zrobimy

33
00:01:36,250 --> 00:01:41,580
jest rodzajem przytrzymaj dwa bok na chwilę,
przesunięcie pięć nad, a następnie włóż dwie

34
00:01:41,580 --> 00:01:43,210
przed piątą, gdzie powinien iść.

35
00:01:43,210 --> 00:01:45,280
A teraz możemy powiedzieć, że dwa są sortowane.

36
00:01:45,280 --> 00:01:48,400
>> Więc jak widać, mamy tylko do tej pory
wyglądała na dwóch elementów macierzy.

37
00:01:48,400 --> 00:01:50,600
Nie spojrzał na
spoczywać na wszystkich, ale mamy

38
00:01:50,600 --> 00:01:54,582
ale te dwa elementy klasyfikowane według
sposób z mechanizmem przesuwania.

39
00:01:54,582 --> 00:01:56,410
>> Więc jeszcze raz powtórzyć proces.

40
00:01:56,410 --> 00:01:58,850
Spójrz na następny nieposortowane
Element, który jest jeden.

41
00:01:58,850 --> 00:02:04,010
Załóżmy, że oprócz posiadania przez sekundę,
przesunąć wszystko nad i umieścić jeden

42
00:02:04,010 --> 00:02:05,570
gdzie powinien iść.

43
00:02:05,570 --> 00:02:08,110
>> Ponownie, wciąż, mamy zawsze tylko
spojrzał na jeden, dwa, i pięć.

44
00:02:08,110 --> 00:02:12,480
Nie wiemy, co jeszcze przyjdzie,
ale my klasyfikowane te trzy elementy.

45
00:02:12,480 --> 00:02:16,030
>> Następny nieposortowane elementem jest
trzy, więc będziemy odłóż go na bok.

46
00:02:16,030 --> 00:02:18,200
Będziemy zmieniać na co
potrzebne do której tym razem

47
00:02:18,200 --> 00:02:21,820
to nie wszystko, jak w poprzednim
dwa przypadki, to tylko pięć.

48
00:02:21,820 --> 00:02:25,440
A potem będziemy trzymać trzy w,
między nimi a pięć.

49
00:02:25,440 --> 00:02:27,849
>> Sześć jest kolejnym nieposortowane
elementem tablicy.

50
00:02:27,849 --> 00:02:31,140
W rzeczywistości six jest większa niż pięć, tak
nawet nie trzeba robić żadnych swapping.

51
00:02:31,140 --> 00:02:35,710
Możemy po prostu przykleić sześć prawo na
Koniec sortowany porcji.

52
00:02:35,710 --> 00:02:38,270
>> Wreszcie, cztery jest
Ostatnim elementem nieposortowane.

53
00:02:38,270 --> 00:02:42,060
Będziemy więc odłóż go na bok, przesunięcie w
elementy musimy przenieść się,

54
00:02:42,060 --> 00:02:43,780
a następnie umieścić cztery, gdzie należy.

55
00:02:43,780 --> 00:02:46,400
A teraz spójrz, mamy sort
wszystkich elementów.

56
00:02:46,400 --> 00:02:48,150
Zawiadomienie o wprowadzeniu
sortowanie, nie mieliśmy

57
00:02:48,150 --> 00:02:50,240
iść tam iz powrotem po tablicy.

58
00:02:50,240 --> 00:02:54,720
Udaliśmy się tylko po drugiej stronie tablicy
jeden raz, a my przesunięty rzeczy

59
00:02:54,720 --> 00:02:59,870
że że już napotkał, w celu
aby zrobić miejsce dla nowych elementów.

60
00:02:59,870 --> 00:03:02,820
>> Więc co jest najgorszym przypadku
Scenariusz z wstawiania rodzaju?

61
00:03:02,820 --> 00:03:05,090
W najgorszym przypadku,
Tablica jest w odwrotnej kolejności.

62
00:03:05,090 --> 00:03:11,180
Musisz przenieść każdego z n elementów
do pozycji n, każdy mamy czas

63
00:03:11,180 --> 00:03:12,880
dokonać wkładanie.

64
00:03:12,880 --> 00:03:15,720
To dużo przesunięcia.

65
00:03:15,720 --> 00:03:18,014
>> W najlepszym przypadku,
Tablica jest doskonale klasyfikowane.

66
00:03:18,014 --> 00:03:20,680
I coś w rodzaju tego, co się stało
z piątej i szóstej przykład

67
00:03:20,680 --> 00:03:23,779
gdzie możemy po prostu przykleić go na
bez konieczności wykonywania jakichkolwiek zmianę biegów,

68
00:03:23,779 --> 00:03:24,820
my w zasadzie zrobić.

69
00:03:24,820 --> 00:03:27,560
>> Jeśli możesz sobie wyobrazić, że nasze
Tablica była jedną z sześciu,

70
00:03:27,560 --> 00:03:29,900
chcielibyśmy zacząć od
oświadczając, jeden jest posortowana.

71
00:03:29,900 --> 00:03:33,300
Dwa przychodzi po jednej więc możemy po prostu
powiedzieć: OK, dobrze jeden i dwa są klasyfikowane.

72
00:03:33,300 --> 00:03:36,190
Trzy przychodzi po dwóch, tak, OK,
jeden i dwa i trzy są klasyfikowane.

73
00:03:36,190 --> 00:03:39,590
>> Nie robisz żadnych swapy, jesteśmy
po prostu się to dowolny wiersz

74
00:03:39,590 --> 00:03:42,460
między sortowane i niesortowane jak idziemy.

75
00:03:42,460 --> 00:03:46,646
Tak skutecznie, jak to zrobiliśmy w tym przykładzie,
elementy przygasa, jak postępować.

76
00:03:46,646 --> 00:03:48,270
Więc co jest najgorszym przypadku czas pracy, a potem?

77
00:03:48,270 --> 00:03:51,854
Pamiętaj, że jeśli mamy do zmiany każdego z
elementy n ewentualnie pozycji n,

78
00:03:51,854 --> 00:03:54,020
miejmy nadzieję, że daje
pomysł, że w najgorszym przypadku

79
00:03:54,020 --> 00:03:57,770
czas pracy jest Big O n do kwadratu.

80
00:03:57,770 --> 00:04:00,220
>> Jeśli tablica jest idealnie
klasyfikowane, wszystko co musisz zrobić,

81
00:04:00,220 --> 00:04:04,480
jest patrzeć na każdego elementu
raz, a potem gotowe.

82
00:04:04,480 --> 00:04:08,440
Tak więc w najlepszym wypadku, to omega n.

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

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

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