[Powered by Google Translate] [Birleştirme Sort]
[Rob Bowden - Harvard Universiteti]
[Bu CS50 edir. - CS50.TV]
Birləşmə sort haqqında danışmaq edək.
İndiyə qədər siz bubble növ daxil sort və seçim cür gördüm.
Mən yaxşı tərəfindən demək nə dalğa mənim əl cür rəftar baxmayaraq,
daxil sort ümumiyyətlə bu 3 növ hər hansı bir daha yaxşı həyata keçirir.
>> Amma birləşmə cür söhbət əvvəl 2 sıralanır siyahıları birləşmə haqqında danışmaq edək.
Biz bu kimi, 2 sıralanır siyahıları qəbul prosesi arayacaðým
və onlara bir sorted siyahısı edilməsi - siyahıları birləşmə.
Biz bunu edə bilər?
Yaxşı, bir fikir yalnız başqa siyahı sonunda üzərinə bir siyahı qalmaq üçün
və sonra yekun siyahısı sort.
>> Bu işləri baxmayaraq, gərəksiz bir çox iş var.
Biz yalnız çeşidlənməsi daha sürətli bunu edə bilərsiniz.
Bir yanlış fikir yalnız hər siyahıdan alternativ fincan almaq üçün bildirək ki.
Ilk o işlər kimi görünə bilər baxmayaraq,
16 və 23 yersiz olduğunu xəbərdarlıq - biz 4, 8, 15, 23, 16 ilə qədər bunu.
Bu, çünki birləşmiş siyahısına ardıcıl görünür ki, 2 elementləri
Eyni ilkin siyahısı var.
15 və 16-həm sol siyahısında var.
Bu oyun həm siyahıları artıq ayrılır ki, istifadə etmək üçün.
Bu o deməkdir ki, biz yalnız iki siyahılarının ilk elementləri baxsaq -
burada, 4 və 8 - Onlardan biri də birləşmiş siyahı ilk element olmalıdır.
Yaxşı, niyə ki?
Bu siyahıları həm də artıq sıralanır,
biz 2 siyahıları birləşdirmək zaman belə, 4 və ya 8 ya kiçik element olmalıdır.
Bu halda, kiçik, 4
biz 4 çıxarmaq və bu, bizim birləşmiş siyahı ilk element edə bilərsiniz.
İndi biz ilk siyahısını qalan 3 elementlər birləşmə davam
və ikinci siyahıda 4 elementləri.
>> Bir daha, biz yalnız iki siyahılarının ilk element baxmaq lazımdır.
2-nin kiçik bizim birləşmiş siyahısı ikinci element olmalıdır.
Bu dəfə, 8 və 15 arasında kiçik 8, və biz daxil olan
bizim sıralaması siyahısında ikinci element kimi.
Biz həm siyahılarının ilk elementləri müqayisə davam edə bilər
və 2 kiçik çıxarılması.
15 və 23, 15 müqayisədə kiçik və belə ki, üçüncü elementidir.
İndi 16 müqayisə və 23, 16 kiçik.
Belə ki, dördüncü element var.
>> 2 elementlər bir sıra eyni siyahı gəldi edək ki,.
Bu nə birləşmiş siyahısı 2 siyahıları yalnız alternativ elementləri bilməz.
50 və 23, 23, müqayisə kiçik, belə ki seçin.
50 və 42 arasında, 42 kiçik.
50 və 108 arasında, 50 kiçik.
Və, nəhayət, biz yalnız 108 var, belə ki, bizim siyahı sonunda getmək lazımdır.
Biz bir gözəl, sorted siyahısı edək ki,.
Biz 2 siyahılarının ilk 2 elementlər müqayisədə hər zaman
biz birləşmiş siyahısı növbəti element müəyyən edə bildik.
Bu halda yekun siyahı n burada 8 Ü n nömrələri şey deməkdir
sonra doğru yerə bu nömrələr bütün almaq üçün ən n müqayisələr da lazımdır.
Belə bir alqoritm, xətti zaman çalışır deyilir
amma burada bu barədə narahat olmayın.
>> Birləşdirilməsi üçün alqoritm istifadə edərək, sürətli birləşmə cür alqoritm edə bilərsiniz.
Belə ki, bizim siyahıları yenidən bildirin.
Birləşmə sort prosesində 2 böyük addımlar var.
Birincisi, davamlı yarıya indirir daxil fincanların siyahısı split
biz onlara yalnız 1 fincan ilə siyahıları bir dəstə qədər.
Siyahısını tək sayda varsa, narahat olmayın
və onların arasında mükəmməl təmiz cut edə bilməz.
Yalnız özbaşına əlavə kubok daxil daxil olan siyahısı seçin
Belə ki, nin bu siyahıları split imkan verir.
İndi 2 siyahıları var.
İndi biz 4 siyahıları var.
>> İndi biz bir siyahısını bir fincan 8 siyahıları var.
Belə ki, 1 adım üçün deyil.
Adım 2, biz dəfələrlə biz əvvəl öyrənildi birləşmə alqoritmi istifadə siyahıları cüt birləşməsi.
108 və 15 birləşmə, biz siyahısına 15, 108 ilə qədər.
50 və 4 birləşmə, biz 4, 50 ilə qədər.
8 və 42 birləşmə, biz, 8 ilə 42 qədər.
Və 23 və 16 birləşmə, biz, 16 ilə 23 qədər.
İndi bütün siyahıları ölçüsü 2 daşıyır.
4 siyahıları hər çeşidlənir edək ki,.
>> Yəni biz yenidən siyahıları cüt birləşməsi başlaya bilərsiniz.
15 və 108, 4 və 50 Birləşdirən -
ilk sonra 108, sonra 50, sonra 15, 4 edirlər.
8, 42 və 16, 23, Birləşdirən
biz ilk sonra sonra 8, 16, 23, 42 edir.
Belə ki, indi biz size 4 yalnız 2 siyahıları ki, hər biri çeşidlənir.
Belə ki, indi biz bu 2 siyahıları daxil.
İlk 4 edirlər.
Sonra 8 edirlər.
Sonra 15 və sonra sonra 16, 23, 42, 50, 108 almaq.
Və biz tamamlayın.
İndi sıralanır siyahısı var.
Beləliklə, bu tam necə sürətli oldu?
Texniki baxımından, birləşmə sort, O (n log n) ki,
bubble növ daxil sort və seçim növ bütün O var isə (n ²).
Tezliklə öğreneceksiniz kimi Əslində, siz bir növ ilə gəlmək mümkün olmayacaq
ki, ümumi halda O (n log n) daha yaxşı həyata keçirir.
Siz hələ görməmişik əgər Yenə bu böyük O notation haqqında narahat olmayın.
>> Biz, həqiqətən, böyük siyahısını düzmək üçün istəyirdi bu o deməkdir ki, bilirik
bubble növ daxil sort və seçim cür potensial bilər
əhəmiyyətli dərəcədə artıq sort daxil deyil.
Bu birləşmə cür sürətli bütün siyahıları olacaq demək deyil ki,
və ya hətta müəyyən bir ölçüsü altında hər hansı bir siyahısı üçün.
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.
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.
>> Amma bu əlavə sürətli bir qiyməti olmayan gəlmir.
Digər növ fərqli olaraq, hansı yerdə siyahısı siyahısını almaq və dəyişdirmək
biz bir sorted siyahısı qədər birləşməsi sort bir əlavə yer lazımdır
birlikdə 2 siyahıları daxil etmək üçün.
Biz dərhal birləşmiş siyahısını saxlamaq üçün birləşdi olunur ki, siyahıları istifadə edə
biz hələ birləşdi lazımdır elementləri yalnış ola bilər-ci ildən.
Bu yer bir qiymət bir az, lakin adətən əsassız deyil.
Və birləşmə sort üçün var.
>> My name Rob Bowden, bu CS50 edir.
[CS50.TV]
- Və seçim sort.
[Gülür]
Oh, mən təqdim necə işə çünki çox ki, çıxarmaq lazımdır.
Sol siyahısı. Bu typo idi.
[Misspoke] Mən qıfıllar -
[Gülür]
Mən nə bilmirəm -