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

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Sveučilište Harvard]

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

4
00:00:07,000 --> 00:00:09,000
Ajmo pričati o spajanja vrste.

5
00:00:09,000 --> 00:00:14,000
Do sada ste vidjeli mjehurić vrsta, umetanja sortiranje i odabir vrste.

6
00:00:14,000 --> 00:00:17,000
Iako ću vrsta vala moju ruku na što mislim bolje,

7
00:00:17,000 --> 00:00:21,000
spojiti vrsta uglavnom obavlja bolje od bilo koje od tih triju vrsta.

8
00:00:22,000 --> 00:00:27,000
>> No, prije nego što se govori o spajanja vrste, pričajmo o spajanju dvije sortirane liste.

9
00:00:27,000 --> 00:00:31,000
Mi ćemo pozvati proces uzimanja dvije sortirane liste, kao što su ovi,

10
00:00:31,000 --> 00:00:35,000
i stvaranje jednog sortirani popis od njih - spajanje popise.

11
00:00:35,000 --> 00:00:37,750
Kako možemo to učiniti?

12
00:00:37,750 --> 00:00:41,290
Pa, jedan ideja je da se samo držati jedan popis na kraju drugog popisa

13
00:00:41,290 --> 00:00:43,830
a zatim sortirati dobivenog popisa.

14
00:00:43,830 --> 00:00:47,220
>> Dok to radi, to je puno nepotrebnog posla.

15
00:00:47,220 --> 00:00:49,900
Možemo to učiniti brže nego samo sortiranje.

16
00:00:49,900 --> 00:00:54,100
Obavijest da je jedan krivo Ideja je da samo uzeti izmjenične šalice sa svake liste.

17
00:00:54,100 --> 00:00:56,460
Dok se to može činiti kao da se radi na prvi,

18
00:00:56,460 --> 00:01:05,760
događaj koji smo završili s 4, 8, 15, 23, 16 - najave da 16 i 23 su izvan mjesta.

19
00:01:05,760 --> 00:01:09,380
To je zato dva elementa koji bi se trebao pojaviti zaredom u pripojenoga popisu

20
00:01:09,380 --> 00:01:11,720
su u istom početnom popisu.

21
00:01:11,720 --> 00:01:14,850
Oba 15 i 16 su u popisu na lijevoj strani.

22
00:01:14,850 --> 00:01:19,810
Trik je iskoristiti činjenicu da su obje liste već su poredani.

23
00:01:19,810 --> 00:01:23,320
To znači da, ako mi samo pogledate prvi elementima obje liste -

24
00:01:23,320 --> 00:01:29,580
ovdje, 4 i 8 - jedan od njih također mora biti prvi element spojeni popisa.

25
00:01:29,580 --> 00:01:31,620
Pa, zašto je to?

26
00:01:31,620 --> 00:01:33,520
Obje ove liste već su razvrstani,

27
00:01:33,520 --> 00:01:38,410
i tako bilo 4 ili 8 mora biti najmanji element kada smo kombinirati dvije liste.

28
00:01:38,410 --> 00:01:41,770
U ovom slučaju, najmanji je 4,

29
00:01:41,770 --> 00:01:46,370
tako da možemo uzeti četiri i učiniti ga prvi element naše spojene popisu.

30
00:01:46,370 --> 00:01:50,710
Sada ćemo nastaviti spajanjem preostale tri elemente prvog popisa

31
00:01:50,710 --> 00:01:52,920
i 4 elementi drugom popisu.

32
00:01:52,920 --> 00:01:57,150
>> Opet, trebamo samo gledati na prvom elementu oba popisa.

33
00:01:57,150 --> 00:02:01,060
Manji od 2 mora biti drugi element naše spojene popisu.

34
00:02:01,060 --> 00:02:05,440
Ovaj put, između 8 i 15 najmanji je osam, i tako smo ubaciti da

35
00:02:05,440 --> 00:02:09,240
kao drugi element našeg sortirani popis.

36
00:02:09,240 --> 00:02:12,180
Možemo nastaviti uspoređujući prvi elemente oba popisa

37
00:02:12,180 --> 00:02:14,420
i uklanjanje manji od 2.

38
00:02:14,420 --> 00:02:19,460
Uspoređujući 15 i 23, 15 je manji i da je naš treći element.

39
00:02:21,000 --> 00:02:23,910
Sada usporedbom 16 i 23, 16 je manji.

40
00:02:23,910 --> 00:02:26,820
Dakle, to je četvrti element.

41
00:02:26,820 --> 00:02:30,390
>> Primijetit ćete da dva elementa došao iz istog popisa u nizu.

42
00:02:30,390 --> 00:02:34,400
To je razlog zašto je nastao popis ne može samo izmjenjuju elementi iz dvije liste.

43
00:02:34,400 --> 00:02:40,020
Uspoređujući 50 i 23, 23 je manji, pa smo odlučili da.

44
00:02:40,770 --> 00:02:44,070
Između 50 i 42, 42 je manji.

45
00:02:44,070 --> 00:02:48,290
Između 50 i 108, 50 je manji.

46
00:02:48,290 --> 00:02:52,330
I, konačno, imamo samo 108, tako da se mora ići na kraju našeg popisa.

47
00:02:53,750 --> 00:02:56,180
Primijetit ćete da imamo lijep, sortirani popis.

48
00:02:56,180 --> 00:02:59,040
Svaki put kad smo usporedili prvi dvije elemente dvije liste

49
00:02:59,040 --> 00:03:02,730
bili smo u mogućnosti kako bi se utvrdilo sljedeći element spojeni popisu.

50
00:03:02,730 --> 00:03:08,070
To znači da, ako konačni popis sadrži n brojeva, gdje je n ovdje je 8,

51
00:03:08,070 --> 00:03:12,610
onda moramo na većini n usporedbe dobiti sve od tih brojeva u pravo mjesto.

52
00:03:13,230 --> 00:03:16,230
Takav algoritam je rekao da se izvoditi u linearnom vremenu,

53
00:03:16,230 --> 00:03:18,090
ali ne brinite o tome ovdje.

54
00:03:18,570 --> 00:03:22,810
>> Koristeći naš algoritam za spajanjem, možemo napraviti brzo spajanje algoritam sortiranja.

55
00:03:22,810 --> 00:03:25,170
Dakle, ajmo ponovno naše liste.

56
00:03:35,210 --> 00:03:37,750
Postoje dvije velike korake u procesu spajanja vrste.

57
00:03:37,750 --> 00:03:41,500
Prvo, kontinuirano podijeliti popis šalice na polovice

58
00:03:41,500 --> 00:03:44,860
dok imamo hrpu liste sa samo jednom šalicom u njima.

59
00:03:44,860 --> 00:03:47,350
Ne brinite ako popis sadrži neparan broj

60
00:03:47,350 --> 00:03:49,880
i ne možete napraviti savršeno čisti rez između njih.

61
00:03:49,880 --> 00:03:53,750
Samo proizvoljno odabrati koji popis uključiti dodatni šalicu u.

62
00:03:53,750 --> 00:03:56,240
Dakle, ajmo podijeliti ove liste.

63
00:03:58,140 --> 00:04:01,310
Sada imamo dvije liste.

64
00:04:04,120 --> 00:04:06,570
Sada imamo četiri liste.

65
00:04:10,350 --> 00:04:13,870
>> I sada imamo 8 liste s jednom šalicom u svakom popisu.

66
00:04:13,870 --> 00:04:16,630
Dakle, to je to za 1. koraku.

67
00:04:16,630 --> 00:04:22,230
Za koraku 2, smo u više navrata spajanje parova popisa pomoću spajanja algoritam smo naučili prije.

68
00:04:22,230 --> 00:04:29,160
Stapanje 108 i 15, mi završiti s popisa 15, 108.

69
00:04:30,330 --> 00:04:36,250
Stapanje 50 i 4, mi završiti s 4, 50.

70
00:04:36,960 --> 00:04:41,400
Spajanje 8 i 42, mi završiti s osam, 42.

71
00:04:42,790 --> 00:04:48,130
A spajanjem 23 i 16, mi završiti s 16, 23.

72
00:04:49,740 --> 00:04:52,450
Sada svi naši popisi su veličine dva.

73
00:04:53,020 --> 00:04:56,180
Primijetite da svaka od 4 lista je razvrstan.

74
00:04:56,180 --> 00:04:59,160
>> Dakle, možemo početi spajanjem parova popisima ponovno.

75
00:04:59,160 --> 00:05:03,240
Stapanje 15 i 108 i 4 i 50 -

76
00:05:03,240 --> 00:05:11,170
najprije od 4, a zatim 15, a zatim 50, a zatim 108.

77
00:05:11,170 --> 00:05:15,120
Spajanje 8, 42 i 16, 23,

78
00:05:15,120 --> 00:05:22,440
prvo se 8, a zatim 16, zatim 23, zatim 42.

79
00:05:22,440 --> 00:05:27,370
Tako sada imamo samo dvije liste veličine 4, od kojih je svaki razvrstani.

80
00:05:27,370 --> 00:05:30,980
Dakle, sada smo spojiti ove dvije liste.

81
00:05:30,980 --> 00:05:33,440
Najprije smo se 4.

82
00:05:33,440 --> 00:05:36,580
Onda smo se osam.

83
00:05:36,580 --> 00:05:50,700
Onda smo se 15 i 16, zatim 23, zatim 42, zatim 50, a zatim 108.

84
00:05:50,700 --> 00:05:52,220
I mi smo gotovi.

85
00:05:52,220 --> 00:05:54,900
Mi sada imamo sortirani popis.

86
00:05:54,900 --> 00:05:57,890
Dakle, koliko brzo je to točno?

87
00:05:57,890 --> 00:06:02,000
U tehničkom smislu, spajanje vrsta je O (n log n),

88
00:06:02,000 --> 00:06:07,380
a sve mjehurića vrste, umetanja sortirati i izbor sortirati su O (n ²).

89
00:06:07,380 --> 00:06:11,120
U stvari, kao što ćete saznati uskoro, nećete biti u mogućnosti da se s nekom vrstom

90
00:06:11,120 --> 00:06:14,820
koji obavlja bolje od O (n log n) u općem slučaju.

91
00:06:14,820 --> 00:06:19,120
Opet, ne brinite o ovom velikom O notaciji, ako niste ga vidjeli još.

92
00:06:19,120 --> 00:06:23,490
>> Samo znam da to znači da ako želimo sortirati stvarno velik popis

93
00:06:23,490 --> 00:06:26,820
mjehurić vrsta, umetanje vrsta, a izbor vrsta potencijalno mogao uzeti

94
00:06:26,820 --> 00:06:29,500
znatno duže od pisama vrsta.

95
00:06:29,500 --> 00:06:33,210
To ne znači da je spajanje vrsta će biti brži za sve popise

96
00:06:33,210 --> 00:06:36,220
ili čak za jednu popisu pod određenu veličinu.

97
00:06:36,220 --> 00:06:41,950
Na primjer, za umetanje vrsta može biti najbrži vrsta za sve popise manje od pet elemenata.

98
00:06:41,950 --> 00:06:47,360
U praksi, spajanje vrsta je obično brže za popise kao mali kao 50 elemenata.

99
00:06:47,360 --> 00:06:51,120
>> No, ovaj dodatni brzina ne dolazi bez cijene.

100
00:06:51,120 --> 00:06:54,770
Za razliku od naših drugih vrsta, koja se popis i mijenjati popis u mjestu

101
00:06:54,770 --> 00:06:58,740
dok smo dobili sortiran popis, spajanje vrsta treba neki dodatni prostor

102
00:06:58,740 --> 00:07:00,900
spojiti dvije liste zajedno.

103
00:07:00,900 --> 00:07:04,690
Mi ne može odmah koristiti popise koje se spojili za pohranu spojene popis

104
00:07:04,690 --> 00:07:08,880
jer smo mogli pregaziti elemente koji još uvijek treba spajati.

105
00:07:08,880 --> 00:07:13,540
Ovaj prostor je malo cijeni, ali to obično nije nerazumna.

106
00:07:13,540 --> 00:07:15,330
I to je to za spajanje vrste.

107
00:07:15,330 --> 00:07:18,490
>> Moje ime je Rob Bowden, a ovo je CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- I odabir vrsta.

110
00:07:24,000 --> 00:07:25,880
[Smijeh]

111
00:07:25,880 --> 00:07:31,480
Oh, moram poduzeti da se previše jer sam se prebacio kako sam ga predstaviti.

112
00:07:31,480 --> 00:07:35,680
Popis na lijevoj strani. To je bila pogreška pri upisu.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] ja zeznuo -

114
00:07:39,290 --> 00:07:41,190
[Smijeh]

115
00:07:41,190 --> 00:07:44,190
Ne znam što -