1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Birleştirme Sort]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard Universiteti]

3
00:00:04,000 --> 00:00:07,000
[Bu CS50 edir. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Birləşmə sort haqqında danışmaq edək.

5
00:00:09,000 --> 00:00:14,000
İndiyə qədər siz bubble növ daxil sort və seçim cür gördüm.

6
00:00:14,000 --> 00:00:17,000
Mən yaxşı tərəfindən demək nə dalğa mənim əl cür rəftar baxmayaraq,

7
00:00:17,000 --> 00:00:21,000
daxil sort ümumiyyətlə bu 3 növ hər hansı bir daha yaxşı həyata keçirir.

8
00:00:22,000 --> 00:00:27,000
>> Amma birləşmə cür söhbət əvvəl 2 sıralanır siyahıları birləşmə haqqında danışmaq edək.

9
00:00:27,000 --> 00:00:31,000
Biz bu kimi, 2 sıralanır siyahıları qəbul prosesi arayacaðým

10
00:00:31,000 --> 00:00:35,000
və onlara bir sorted siyahısı edilməsi - siyahıları birləşmə.

11
00:00:35,000 --> 00:00:37,750
Biz bunu edə bilər?

12
00:00:37,750 --> 00:00:41,290
Yaxşı, bir fikir yalnız başqa siyahı sonunda üzərinə bir siyahı qalmaq üçün

13
00:00:41,290 --> 00:00:43,830
və sonra yekun siyahısı sort.

14
00:00:43,830 --> 00:00:47,220
>> Bu işləri baxmayaraq, gərəksiz bir çox iş var.

15
00:00:47,220 --> 00:00:49,900
Biz yalnız çeşidlənməsi daha sürətli bunu edə bilərsiniz.

16
00:00:49,900 --> 00:00:54,100
Bir yanlış fikir yalnız hər siyahıdan alternativ fincan almaq üçün bildirək ki.

17
00:00:54,100 --> 00:00:56,460
Ilk o işlər kimi görünə bilər baxmayaraq,

18
00:00:56,460 --> 00:01:05,760
16 və 23 yersiz olduğunu xəbərdarlıq - biz 4, 8, 15, 23, 16 ilə qədər bunu.

19
00:01:05,760 --> 00:01:09,380
Bu, çünki birləşmiş siyahısına ardıcıl görünür ki, 2 elementləri

20
00:01:09,380 --> 00:01:11,720
Eyni ilkin siyahısı var.

21
00:01:11,720 --> 00:01:14,850
15 və 16-həm sol siyahısında var.

22
00:01:14,850 --> 00:01:19,810
Bu oyun həm siyahıları artıq ayrılır ki, istifadə etmək üçün.

23
00:01:19,810 --> 00:01:23,320
Bu o deməkdir ki, biz yalnız iki siyahılarının ilk elementləri baxsaq -

24
00:01:23,320 --> 00:01:29,580
burada, 4 və 8 - Onlardan biri də birləşmiş siyahı ilk element olmalıdır.

25
00:01:29,580 --> 00:01:31,620
Yaxşı, niyə ki?

26
00:01:31,620 --> 00:01:33,520
Bu siyahıları həm də artıq sıralanır,

27
00:01:33,520 --> 00:01:38,410
biz 2 siyahıları birləşdirmək zaman belə, 4 və ya 8 ya kiçik element olmalıdır.

28
00:01:38,410 --> 00:01:41,770
Bu halda, kiçik, 4

29
00:01:41,770 --> 00:01:46,370
biz 4 çıxarmaq və bu, bizim birləşmiş siyahı ilk element edə bilərsiniz.

30
00:01:46,370 --> 00:01:50,710
İndi biz ilk siyahısını qalan 3 elementlər birləşmə davam

31
00:01:50,710 --> 00:01:52,920
və ikinci siyahıda 4 elementləri.

32
00:01:52,920 --> 00:01:57,150
>> Bir daha, biz yalnız iki siyahılarının ilk element baxmaq lazımdır.

33
00:01:57,150 --> 00:02:01,060
2-nin kiçik bizim birləşmiş siyahısı ikinci element olmalıdır.

34
00:02:01,060 --> 00:02:05,440
Bu dəfə, 8 və 15 arasında kiçik 8, və biz daxil olan

35
00:02:05,440 --> 00:02:09,240
bizim sıralaması siyahısında ikinci element kimi.

36
00:02:09,240 --> 00:02:12,180
Biz həm siyahılarının ilk elementləri müqayisə davam edə bilər

37
00:02:12,180 --> 00:02:14,420
və 2 kiçik çıxarılması.

38
00:02:14,420 --> 00:02:19,460
15 və 23, 15 müqayisədə kiçik və belə ki, üçüncü elementidir.

39
00:02:21,000 --> 00:02:23,910
İndi 16 müqayisə və 23, 16 kiçik.

40
00:02:23,910 --> 00:02:26,820
Belə ki, dördüncü element var.

41
00:02:26,820 --> 00:02:30,390
>> 2 elementlər bir sıra eyni siyahı gəldi edək ki,.

42
00:02:30,390 --> 00:02:34,400
Bu nə birləşmiş siyahısı 2 siyahıları yalnız alternativ elementləri bilməz.

43
00:02:34,400 --> 00:02:40,020
50 və 23, 23, müqayisə kiçik, belə ki seçin.

44
00:02:40,770 --> 00:02:44,070
50 və 42 arasında, 42 kiçik.

45
00:02:44,070 --> 00:02:48,290
50 və 108 arasında, 50 kiçik.

46
00:02:48,290 --> 00:02:52,330
Və, nəhayət, biz yalnız 108 var, belə ki, bizim siyahı sonunda getmək lazımdır.

47
00:02:53,750 --> 00:02:56,180
Biz bir gözəl, sorted siyahısı edək ki,.

48
00:02:56,180 --> 00:02:59,040
Biz 2 siyahılarının ilk 2 elementlər müqayisədə hər zaman

49
00:02:59,040 --> 00:03:02,730
biz birləşmiş siyahısı növbəti element müəyyən edə bildik.

50
00:03:02,730 --> 00:03:08,070
Bu halda yekun siyahı n burada 8 Ü n nömrələri şey deməkdir

51
00:03:08,070 --> 00:03:12,610
sonra doğru yerə bu nömrələr bütün almaq üçün ən n müqayisələr da lazımdır.

52
00:03:13,230 --> 00:03:16,230
Belə bir alqoritm, xətti zaman çalışır deyilir

53
00:03:16,230 --> 00:03:18,090
amma burada bu barədə narahat olmayın.

54
00:03:18,570 --> 00:03:22,810
>> Birləşdirilməsi üçün alqoritm istifadə edərək, sürətli birləşmə cür alqoritm edə bilərsiniz.

55
00:03:22,810 --> 00:03:25,170
Belə ki, bizim siyahıları yenidən bildirin.

56
00:03:35,210 --> 00:03:37,750
Birləşmə sort prosesində 2 böyük addımlar var.

57
00:03:37,750 --> 00:03:41,500
Birincisi, davamlı yarıya indirir daxil fincanların siyahısı split

58
00:03:41,500 --> 00:03:44,860
biz onlara yalnız 1 fincan ilə siyahıları bir dəstə qədər.

59
00:03:44,860 --> 00:03:47,350
Siyahısını tək sayda varsa, narahat olmayın

60
00:03:47,350 --> 00:03:49,880
və onların arasında mükəmməl təmiz cut edə bilməz.

61
00:03:49,880 --> 00:03:53,750
Yalnız özbaşına əlavə kubok daxil daxil olan siyahısı seçin

62
00:03:53,750 --> 00:03:56,240
Belə ki, nin bu siyahıları split imkan verir.

63
00:03:58,140 --> 00:04:01,310
İndi 2 siyahıları var.

64
00:04:04,120 --> 00:04:06,570
İndi biz 4 siyahıları var.

65
00:04:10,350 --> 00:04:13,870
>> İndi biz bir siyahısını bir fincan 8 siyahıları var.

66
00:04:13,870 --> 00:04:16,630
Belə ki, 1 adım üçün deyil.

67
00:04:16,630 --> 00:04:22,230
Adım 2, biz dəfələrlə biz əvvəl öyrənildi birləşmə alqoritmi istifadə siyahıları cüt birləşməsi.

68
00:04:22,230 --> 00:04:29,160
108 və 15 birləşmə, biz siyahısına 15, 108 ilə qədər.

69
00:04:30,330 --> 00:04:36,250
50 və 4 birləşmə, biz 4, 50 ilə qədər.

70
00:04:36,960 --> 00:04:41,400
8 və 42 birləşmə, biz, 8 ilə 42 qədər.

71
00:04:42,790 --> 00:04:48,130
Və 23 və 16 birləşmə, biz, 16 ilə 23 qədər.

72
00:04:49,740 --> 00:04:52,450
İndi bütün siyahıları ölçüsü 2 daşıyır.

73
00:04:53,020 --> 00:04:56,180
4 siyahıları hər çeşidlənir edək ki,.

74
00:04:56,180 --> 00:04:59,160
>> Yəni biz yenidən siyahıları cüt birləşməsi başlaya bilərsiniz.

75
00:04:59,160 --> 00:05:03,240
15 və 108, 4 və 50 Birləşdirən -

76
00:05:03,240 --> 00:05:11,170
ilk sonra 108, sonra 50, sonra 15, 4 edirlər.

77
00:05:11,170 --> 00:05:15,120
8, 42 və 16, 23, Birləşdirən

78
00:05:15,120 --> 00:05:22,440
biz ilk sonra sonra 8, 16, 23, 42 edir.

79
00:05:22,440 --> 00:05:27,370
Belə ki, indi biz size 4 yalnız 2 siyahıları ki, hər biri çeşidlənir.

80
00:05:27,370 --> 00:05:30,980
Belə ki, indi biz bu 2 siyahıları daxil.

81
00:05:30,980 --> 00:05:33,440
İlk 4 edirlər.

82
00:05:33,440 --> 00:05:36,580
Sonra 8 edirlər.

83
00:05:36,580 --> 00:05:50,700
Sonra 15 və sonra sonra 16, 23, 42, 50, 108 almaq.

84
00:05:50,700 --> 00:05:52,220
Və biz tamamlayın.

85
00:05:52,220 --> 00:05:54,900
İndi sıralanır siyahısı var.

86
00:05:54,900 --> 00:05:57,890
Beləliklə, bu tam necə sürətli oldu?

87
00:05:57,890 --> 00:06:02,000
Texniki baxımından, birləşmə sort, O (n log n) ki,

88
00:06:02,000 --> 00:06:07,380
bubble növ daxil sort və seçim növ bütün O var isə (n ²).

89
00:06:07,380 --> 00:06:11,120
Tezliklə öğreneceksiniz kimi Əslində, siz bir növ ilə gəlmək mümkün olmayacaq

90
00:06:11,120 --> 00:06:14,820
ki, ümumi halda O (n log n) daha yaxşı həyata keçirir.

91
00:06:14,820 --> 00:06:19,120
Siz hələ görməmişik əgər Yenə bu böyük O notation haqqında narahat olmayın.

92
00:06:19,120 --> 00:06:23,490
>> Biz, həqiqətən, böyük siyahısını düzmək üçün istəyirdi bu o deməkdir ki, bilirik

93
00:06:23,490 --> 00:06:26,820
bubble növ daxil sort və seçim cür potensial bilər

94
00:06:26,820 --> 00:06:29,500
əhəmiyyətli dərəcədə artıq sort daxil deyil.

95
00:06:29,500 --> 00:06:33,210
Bu birləşmə cür sürətli bütün siyahıları olacaq demək deyil ki,

96
00:06:33,210 --> 00:06:36,220
və ya hətta müəyyən bir ölçüsü altında hər hansı bir siyahısı üçün.

97
00:06:36,220 --> 00:06:41,950
Məsələn, durub sırala 5 element daha kiçik bütün siyahıları üçün sürətli sort ola bilər.

98
00:06:41,950 --> 00:06:47,360
Təcrübədə, birləşmə sort 50 elementlər kimi kiçik kimi siyahıları üçün adətən daha sürətli edir.

99
00:06:47,360 --> 00:06:51,120
>> Amma bu əlavə sürətli bir qiyməti olmayan gəlmir.

100
00:06:51,120 --> 00:06:54,770
Digər növ fərqli olaraq, hansı yerdə siyahısı siyahısını almaq və dəyişdirmək

101
00:06:54,770 --> 00:06:58,740
biz bir sorted siyahısı qədər birləşməsi sort bir əlavə yer lazımdır

102
00:06:58,740 --> 00:07:00,900
birlikdə 2 siyahıları daxil etmək üçün.

103
00:07:00,900 --> 00:07:04,690
Biz dərhal birləşmiş siyahısını saxlamaq üçün birləşdi olunur ki, siyahıları istifadə edə

104
00:07:04,690 --> 00:07:08,880
biz hələ birləşdi lazımdır elementləri yalnış ola bilər-ci ildən.

105
00:07:08,880 --> 00:07:13,540
Bu yer bir qiymət bir az, lakin adətən əsassız deyil.

106
00:07:13,540 --> 00:07:15,330
Və birləşmə sort üçün var.

107
00:07:15,330 --> 00:07:18,490
>> My name Rob Bowden, bu CS50 edir.

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

109
00:07:20,500 --> 00:07:24,000
- Və seçim sort.

110
00:07:24,000 --> 00:07:25,880
[Gülür]

111
00:07:25,880 --> 00:07:31,480
Oh, mən təqdim necə işə çünki çox ki, çıxarmaq lazımdır.

112
00:07:31,480 --> 00:07:35,680
Sol siyahısı. Bu typo idi.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] Mən qıfıllar -

114
00:07:39,290 --> 00:07:41,190
[Gülür]

115
00:07:41,190 --> 00:07:44,190
Mən nə bilmirəm -