1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Ubacivanje Sortiraj]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Sveučilište Harvard]

3
00:00:04,240 --> 00:00:07,290
[Ovo je CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Idemo pogledati unosa vrste, algoritam za uzimanje popis brojeva te ih sortirati.

5
00:00:13,060 --> 00:00:18,300
Algoritam, zapamtite, je jednostavno korak-po-korak postupak za ostvarivanje zadatka.

6
00:00:18,300 --> 00:00:23,640
Osnovna ideja iza unosa vrste, je podijeliti našu listu na dva dijela,

7
00:00:23,640 --> 00:00:26,580
sortirani dio i nerazvrstani dio.

8
00:00:26,580 --> 00:00:29,290
>> Na svakom koraku algoritma, broj je premještena

9
00:00:29,290 --> 00:00:32,439
od nerazvrstani dijela na sortirati dio

10
00:00:32,439 --> 00:00:35,680
dok na kraju cijeli popis sortiran.

11
00:00:35,680 --> 00:00:43,340
Ovdje je popis od šest Unsorted brojeva - 23, 42, 4, 16, 8, i 15.

12
00:00:43,340 --> 00:00:47,680
Budući da ove brojke nisu svi u uzlaznom redoslijedu, oni nesortirani.

13
00:00:47,680 --> 00:00:53,890
Budući da nismo počeli sortiranje još ćemo razmotriti svih šest elementima našu nerazvrstani dio.

14
00:00:53,890 --> 00:00:59,270
>> Jednom smo započeli sortiranje, mi ćemo staviti ove sortirane brojeve na lijevoj strani tih.

15
00:00:59,270 --> 00:01:03,600
Dakle, počnimo sa 23, prvi element u našem listu.

16
00:01:03,600 --> 00:01:06,930
Mi nemamo nikakve elemente u našoj sortirani dijela ipak,

17
00:01:06,930 --> 00:01:12,460
pa neka je jednostavno uzeti u obzir 23 biti početak i kraj našeg poredani dijela.

18
00:01:12,460 --> 00:01:16,510
Sada, naš razvrstani dio ima jedan broj, 23,

19
00:01:16,510 --> 00:01:20,260
i naš nerazvrstani dio ima tih pet brojeva.

20
00:01:20,260 --> 00:01:27,320
Idemo sada umetnite sljedeći broj u našoj nerazvrstani dio, 42, u razvrstanih dijela.

21
00:01:27,320 --> 00:01:35,930
>> Da biste to učinili, morat ćemo usporediti 42 do 23 - jedini element u našoj sortirani dijela tako daleko.

22
00:01:35,930 --> 00:01:41,980
Četrdeset i dva je veći od 23, tako da smo jednostavno možete dodati 42 do kraja

23
00:01:41,980 --> 00:01:45,420
o poredani dijela popisa. Sjajno!

24
00:01:45,420 --> 00:01:51,850
Sada naša razvrstani dio ima dva elementa, a naš nerazvrstani dio ima četiri elementa.

25
00:01:51,850 --> 00:01:57,200
Dakle, ajmo sad premjestiti na četiri, sljedeći element u nerazvrstani dijela.

26
00:01:57,200 --> 00:02:00,230
Dakle, gdje bi trebao to biti smješteni u sortirani dio?

27
00:02:00,230 --> 00:02:04,220
>> Zapamtite, mi želimo da se taj broj u sortiraju bi

28
00:02:04,220 --> 00:02:08,680
tako je i naš razvrstani dio ostaje pravilno razvrstani u svim vremenima.

29
00:02:08,680 --> 00:02:14,380
Ako stavite 4 desno od 42, onda naš popis će biti iz reda.

30
00:02:14,380 --> 00:02:18,380
Dakle, neka je i dalje se kreće s desna na lijevo u našem sortiranja dijela.

31
00:02:18,380 --> 00:02:23,260
Kao što smo premjestiti, neka je smjena svaki broj dolje na mjesto kako bi napravili mjesta za novi broj.

32
00:02:25,440 --> 00:02:31,740
Ok, 4 je također manje od 23, pa ne možemo staviti ni ovdje.

33
00:02:31,740 --> 00:02:34,480
Idemo na 23 pravo jednom mjestu.

34
00:02:36,500 --> 00:02:43,120
>> To znači da bismo željeli staviti 4 u prvom utor u razvrstanih dijela.

35
00:02:43,120 --> 00:02:46,300
Obavijest o tome kako je ovaj prostor u popisu je već bio prazan,

36
00:02:46,300 --> 00:02:51,120
jer smo bili kreće sortirane elemente dolje kao što smo ih susreli.

37
00:02:51,120 --> 00:02:52,740
U redu. Dakle, mi smo na pola puta.

38
00:02:52,740 --> 00:02:57,990
Idemo dalje naš algoritam umetanjem 16 u razvrstanih dijela.

39
00:02:59,260 --> 00:03:03,820
Šesnaest je manje od 42, pa ajmo pomaknula 42 na desnoj strani.

40
00:03:05,700 --> 00:03:10,190
Šesnaest je također manje od 23, pa neka je i pomak tog elementa.

41
00:03:11,790 --> 00:03:20,820
>> Sada, 16 je veći od 4. Dakle, izgleda da bih umetnuti 16 između 4 i 23.

42
00:03:20,820 --> 00:03:24,620
Dok se kreće kroz poredani dio popisa s desna na lijevo,

43
00:03:24,620 --> 00:03:29,160
4 je prvi broj vidjeli smo da je manji od broja

44
00:03:29,160 --> 00:03:31,540
Pokušavamo umetnuti.

45
00:03:31,540 --> 00:03:35,820
Dakle, sada možemo umetnuti 16 u ovom prazni utor,

46
00:03:35,820 --> 00:03:40,520
koja, zapamtite, mi smo stvorili pokretnih elemenata u sortiranja dijela preko

47
00:03:40,520 --> 00:03:43,340
kao što smo ih susreli.

48
00:03:43,340 --> 00:03:47,900
>> U redu. Sada imamo četiri sortirane elemente i dva Unsorted elemente.

49
00:03:47,900 --> 00:03:51,600
Dakle, neka je premjestiti 8 u razvrstanih dijela.

50
00:03:51,600 --> 00:03:55,010
Osam je manje od 42.

51
00:03:55,010 --> 00:03:56,940
Osam je manje od 23.

52
00:03:56,940 --> 00:04:00,230
I 8 je manje od 16.

53
00:04:00,230 --> 00:04:03,110
No 8 veći od 4.

54
00:04:03,110 --> 00:04:07,280
Dakle, željeli bismo umetnuti 8 između 4 i 16.

55
00:04:09,070 --> 00:04:13,650
I sada imamo samo jedan više elementa lijevo za sortiranje - The 15.

56
00:04:13,950 --> 00:04:16,589
Petnaest je manje od 42,

57
00:04:16,589 --> 00:04:19,130
Petnaest je manje od 23.

58
00:04:19,130 --> 00:04:21,750
I 15 je manje od 16.

59
00:04:21,750 --> 00:04:24,810
Ali 15 je veći od 8.

60
00:04:24,810 --> 00:04:27,440
>> Dakle, ovdje je mjesto gdje želimo da naš konačni umetanje.

61
00:04:28,770 --> 00:04:30,330
I mi smo gotovi.

62
00:04:30,330 --> 00:04:33,540
Mi nemamo više elemenata u nerazvrstani dijela,

63
00:04:33,540 --> 00:04:36,670
i naš razvrstani dio je u ispravnom redoslijedu.

64
00:04:36,670 --> 00:04:40,270
Brojevi su poredani od najmanjeg do najvećeg.

65
00:04:40,270 --> 00:04:44,330
Dakle, neka je pogledati neke pseudocode koji opisuje korake samo smo izvodili.

66
00:04:46,760 --> 00:04:51,740
>> Na liniji 1, možemo vidjeti da ćemo morati ponoviti više svaki element u popisu

67
00:04:51,740 --> 00:04:57,060
osim prve, od prvog elementa u nerazvrstani dijelu jednostavno će postati

68
00:04:57,060 --> 00:05:00,220
prvi element u poredani dijelu.

69
00:05:00,220 --> 00:05:06,320
Na linijama 2 i 3, mi smo praćenje naše sadašnje mjesto u nerazvrstani dijela.

70
00:05:06,320 --> 00:05:10,450
Element predstavlja broj trenutno smo kreće u razvrstanog dijela,

71
00:05:10,450 --> 00:05:15,600
i j predstavlja našu indeks u nerazvrstanog dio.

72
00:05:15,600 --> 00:05:20,980
>> Na liniji 4, mi smo Ponavljanje kroz poredani dio s desna na lijevo.

73
00:05:20,980 --> 00:05:26,010
Želimo da se zaustavi Ponavljanje jednom elementu na lijevoj strani naše trenutne pozicije

74
00:05:26,010 --> 00:05:30,050
je manji od elementa Pokušavamo umetnuti.

75
00:05:30,050 --> 00:05:35,600
Na liniji 5, mi smo prebacuje svaki element susrećemo jedno mjesto na desno.

76
00:05:35,600 --> 00:05:40,950
Na taj način, imat ćemo jasnu prostor za umetanje u kada smo pronašli prvi element

77
00:05:40,950 --> 00:05:44,080
manje od elementa krećemo.

78
00:05:44,080 --> 00:05:50,800
Na liniji 6, ažurirat ćemo naš brojač nastaviti kretati lijevo kroz poredani dijela.

79
00:05:50,800 --> 00:05:56,860
Konačno, na liniji 7, mi smo umetanja element u poredani dio popisa.

80
00:05:56,860 --> 00:06:00,020
>> Mi znamo da je u redu da uložite u položaj j,

81
00:06:00,020 --> 00:06:05,360
jer već smo se preselili element koji se koristi da se tamo jedno mjesto na desno.

82
00:06:05,360 --> 00:06:09,460
Zapamtite, idemo kroz poredani dio s desna na lijevo,

83
00:06:09,460 --> 00:06:13,960
ali idemo kroz nesortirani dio s lijeva na desno.

84
00:06:13,960 --> 00:06:19,090
U redu. Idemo sada pogledati koliko dugo trčanje koje algoritam uzeo.

85
00:06:19,090 --> 00:06:25,300
Mi smo prvi put ću postaviti pitanje koliko dugo to traje za ovaj algoritam za rad u najgorem slučaju.

86
00:06:25,300 --> 00:06:29,040
Sjetite se da smo predstavljaju ovu trčanje vrijeme s Big O notacijom.

87
00:06:32,530 --> 00:06:38,500
Kako bi se sortirati naš popis, morali smo ponoviti tijekom elemente u nerazvrstani dijela,

88
00:06:38,500 --> 00:06:43,430
a za svaki od tih elemenata, potencijalno nad svim elementima u razvrstanih dijela.

89
00:06:43,430 --> 00:06:47,950
Intuitivno, ovo zvuči kao O (n ^ 2) rada.

90
00:06:47,950 --> 00:06:51,840
>> Gledajući naše pseudocode, imamo petlju ugniježđena unutar drugog kruga,

91
00:06:51,840 --> 00:06:55,290
koji je, doista, zvuči kao O (n ^ 2) rada.

92
00:06:55,290 --> 00:07:01,590
Međutim, razvrstani dio popisa ne sadrže cijeli popis do samog kraja.

93
00:07:01,590 --> 00:07:06,920
Ipak, mi potencijalno mogao ubaciti novi element na samom početku sortirane dio

94
00:07:06,920 --> 00:07:09,320
na svakom iteracija algoritma,

95
00:07:09,320 --> 00:07:14,500
što znači da ćemo morati gledati na svakom elementu trenutno u razvrstanih dijela.

96
00:07:14,500 --> 00:07:20,090
Dakle, to znači da smo potencijalno mogao napraviti jednu usporedbu za drugi element,

97
00:07:20,090 --> 00:07:24,660
dvije usporedbe za trećeg elementa, i tako dalje.

98
00:07:24,660 --> 00:07:32,480
Dakle, ukupan broj koraka je zbroj brojeva od 1 do duljine popisa minus 1.

99
00:07:32,480 --> 00:07:35,240
Mi može predstavljati to sa zbrajanjem.

100
00:07:41,170 --> 00:07:47,270
>> Nećemo ići u summations ovdje, ali ispada da je to zbir je jednaka

101
00:07:47,270 --> 00:07:57,900
n (n - 1) više od 2, što je ekvivalent n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Kada govorimo o asimptotska izvođenja,

103
00:08:00,800 --> 00:08:05,170
ovo n ^ 2 pojam će dominirati ovaj n pojam.

104
00:08:05,170 --> 00:08:11,430
Dakle, umetanje vrsta je Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Što ako smo trčali unosa vrsta na već sortirane liste.

106
00:08:16,150 --> 00:08:20,960
U tom slučaju, mi jednostavno bih izgraditi sortirani dio s lijeva na desno.

107
00:08:20,960 --> 00:08:25,050
Dakle, mi samo trebate na red n koraka.

108
00:08:25,050 --> 00:08:29,740
>> To znači da umetanje vrsta ima najbolje slučaj izvedbu n,

109
00:08:29,740 --> 00:08:34,130
koje predstavljaju s Ω (n).

110
00:08:34,130 --> 00:08:36,190
I to je to za umetanja vrste,

111
00:08:36,190 --> 00:08:40,429
samo jedan od mnogih algoritama možemo koristiti za sortiranje popisa.

112
00:08:40,429 --> 00:08:43,210
Moje ime je Tommy, a ovo je CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, vi jednostavno ne možete prestati da nakon što počne.

115
00:09:01,620 --> 00:09:04,760
Oh, mi to učinio - >> Bum!