[Powered by Google Translate] [Bubble SIRALAMA] [JACKSON STEINKAMP HARVARD UNİVERSİTETİNİN] [BU CS50 edir. CS50TV] Bubble Sort bir çeşidlənməsi alqoritm bir nümunəsidir - ki, elementlərin müəyyən çeşidlənməsi üçün bir prosedurdur artan və ya azalan. Bir sıra sort istəyirdi Məsələn, əgər nömrələri ibarət [3, 5, 2, 9], Bubble Sort düzgün həyata qaytarmaq olardı sıralanır array [2, 3, 5, 9] üçün artan. İndi alqoritmi çalışır pseudocode izah arkasýndayým. 

3, 2, 9, 6 və 5 - Gəlin biz 5 integers bir siyahısı çeşidlənməsi edirik deyirlər. Bu alqoritm, ilk iki elementləri, 3 və 2 baxaraq başlayır onlar bir-birinə nisbətən üçün həyata edirsinizsə və yoxlanılması. Onlar - 3 2-dən böyükdür. Artan qaydada olmaq üçün, onlar ətrafında digər yol olmalıdır. Belə ki, biz onları dəyişdirmək. [2, 3, 9, 6, 5]: İndi siyahısı kimi görünür. 

Sonra, biz ikinci və üçüncü elementləri, 3 və 9 baxın. Onlar bir-birinə nisbətən düzgün qaydada edirik. Alqoritmi onları dəyişdirmək deyil 9 az belə ki, 3 edir. Sonra, biz 9 və 6 oldu. Onlar üçün bitti. 

Belə ki, biz 9 6 böyükdür, çünki onların dəyişdirmək lazımdır. Nəhayət, biz son iki integers, 9 və 5 oldu. Onlar üçün bitti, onlar dəyişdirildikdə olmalıdır. Siyahısını ilk tam ötürməsindən sonra, [2, 3, 6, 5, 9]: Bu kimi görünür. Pis deyil. Demək olar ki, sıralanır edir. Amma biz tamamilə sıralanır almaq üçün yenidən siyahısını axır lazımdır. İki 3-dən az, belə ki, biz onları dəyişdirmək deyil. 

Three 6 azdır, belə ki, biz onları dəyişdirmək deyil. Altı 5-dən böyükdür. Biz dəyişdirildikdə. Altı 9 azdır. Biz dəyişdirmək deyil. Vasitəsilə ikinci ötürməsindən sonra, bu kimi görünür: [2, 3, 5, 6, 9]. Mükəmməldir. İndi pseudocode yazmaq edək. Ümumiyyətlə, siyahıda hər element üçün, biz baxmaq lazımdır və bilavasitə onun sağ üçün element. Onlar üçün bir-birinə nisbətən həyata varsa - ki, əgər sol element hüququ bir daha böyükdür - biz iki elementləri dəyişdirmək lazımdır. 

Biz siyahısı hər element üçün bunu və biz vasitəsilə bir keçid etdik. İndi biz yalnız siyahısını təmin etmək ötürmə kifayət dəfə var tam, düzgün çeşidlənir. Amma biz siyahısına keçmək neçə dəfə var biz Bitirdiğinizde garanti? Biz tamamilə geri siyahısı varsa Yaxşı, ən pis ssenari deyil. Sonra sayına bərabər keçmək-throughs bir sıra edir elementlər n-1. Bu daxilən mənada deyil, sadə bir halda hesab edirəm ki, - siyahısı [2, 1]. 

Bu düzgün düzmək üçün bir ötürmə etmək niyyətindədir. [3, 2, 1] - Ən pis halda, 3 elementləri ilə geri sıralanır ki, bu sort üçün 2 tekrarlamalar etmək olacaq. Bir iteration sonra, [3 1 2] var. İkinci verir the sıralanır array [1, 2, 3]. Belə ki, siz ümumiyyətlə, array vasitəsilə getmək heç vaxt bilmək n sıra elementlərin sayı yerləşir n-1 dəfə çoxdur. Ən böyük elementlərin bubble-up 'meyli çünki Bubble Sort deyirlər olduqca sürətlə sağa. Əslində, bu alqoritm çox maraqlı davranış var. 

Bütün array vasitəsilə m tekrarlamalar sonra, bu rightmost m elementləri təmin edilir onların düzgün yer ayrılır bilər. Siz özünüz üçün bu görmək istəyirsinizsə biz tamamilə geri siyahısı [9, 6, 5, 3, 2] haqqında cəhd edə bilərsiniz. Bütün siyahısını bir keçid sonra, [Yazılı səs] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] bu rightmost element 9 onun düzgün yerdədir. Ötürmə ikinci sonra 6 'bubbled-up' da olacaq ikinci rightmost yer. 6 və 9 - - hüququ üzrə iki elementləri onların düzgün yerlərdə olacaq ilk iki pass-throughs sonra. 

Belə ki, necə biz alqoritm optimize istifadə edə bilərsiniz? Yaxşı, array vasitəsilə bir iteration sonra biz əslində rightmost element yoxlamaq lazım deyil biz bilirik çünki sıralanır edir. Iki tekrarlamalar sonra biz rightmost iki element mövcuddur əmin bilirik. Belə ki, ümumiyyətlə, tam array vasitəsilə k tekrarlamalar sonra, Bildiyimiz ildən keçən k elementləri yoxlanılması lazımsız edir onlar artıq doğru yerdə istəyirik. 

Siz n elementlərin bir sıra çeşidlənməsi etdiyiniz əgər, ilk iteration üzrə - you'll bütün öğeleri sıralama var - ilk n-0. Ikinci iteration, siz bütün öğeleri lakin son baxmaq lazımdır - n-1 ilk. Digər optimallaşdırma siyahısı artıq çeşidlənir yoxlamaq ola bilər hər iteration sonra. Artıq sıralaması var, biz bir daha tekrarlamalar etmək lazım deyil siyahısı ilə. Biz bunu edə bilər? Bəli, biz bir siyahısı ötürmə hər hansı mübadiləsi etmək yoxsa, biz bir şey dəyişdirmək deyil, çünki siyahısını artıq sıralanır ki, aydın deyil. Belə ki, biz mütləq yenidən sıralama yoxdur. 

Bəlkə üçün 'sıralanır deyil' adlı bir bayrağı dəyişən başlamaq bilər siz hər hansı elementləri dəyişdirmək üçün, əgər yalan və doğru dəyişdirmək serialın vasitəsilə bir iteration. Və ya eyni, siz neçə svopları saymaq üçün counter etmək hər hansı iteration haqqında. Bir iteration sonunda, siz elementləri hər hansı dəyişdirmək olmasaydı, siz siyahısına artıq çeşidlənir və Bitirdiğinizde bilirik. Bubble Sort digər çeşidlənməsi alqoritmlərin kimi ola bilər bir sifariş metodu hər hansı elementləri üçün işləmək tweaked. 

Bu, demək üçün bir yol var iki elementləri verilmiş, əgər birinci bərabər və ya ikinci az daha böyükdür. Məsələn, deyərək əlifbasının hərfləri düzmək bilər a <b, b <c, s ki, Bazar ertəsi az olduğu və ya həftə gün sort bilər olan çərşənbə axşamı azdır. 

Heç bir çox səmərəli və sürətli çeşidlənməsi alqoritm vasitəsilə Bubble Sort edir. Onun ən pis halda uzunluğu n Big O ² bir siyahısını n tekrarlamalar etmək lazımdır, çünki hər ötürmə bütün n elementləri nəzarət, nxn = n ². Bu axır zaman elementlərinin sayı kimi, artır çeşidlənməsi edirik o deməkdir ki, run zaman quadratically artırır. 

Lakin səmərəlilik proqram böyük bir narahatlıq olmadığını və ya yalnız elementləri kiçik çeşidlənməsi edirsinizsə, siz Bubble Sort faydalı ola bilər, çünki bunu anlamaq asan çeşidlənməsi alqoritmlərin biri və kod üçün. Bu da nəzəri tərcümə ilə təcrübə almaq üçün bir böyük yol faktiki fəaliyyət kodu daxil alqoritmi. Yaxşı, sizin üçün Bubble Sort var. Izləmək üçün təşəkkür edirik. CS50.TV