[MUSIC PLAYING] DOUG LLOYD: Bütün sağ, belə ki, bubble sırala alqoritm siz elementləri bir sıra düzmək üçün istifadə edə bilərsiniz. Nin bu işləri necə bir nəzər salaq. 

Belə ki, əsas fikir arxasında bubble sort bu. Biz, ümumiyyətlə, yüksək hərəkət etmək istəyirəm ümumiyyətlə sağ üçün dəyərli elementləri, və ümumiyyətlə qiymətləndirilir elementləri aşağı sol, biz gözləmək kimi. Biz aşağı şeylər olmaq istəyirəm başlanğıcı və ali şeyi sonunda olacaq. 

Bunu necə edə bilərəm? Yaxşı pseudocode kodu, biz edək, deyə bilər qeyri-sıfır dəyəri bir svop counter seçin. Biz ikinci ki, niyə biz görəcəksiniz. Və sonra biz aşağıdakı təkrar svop counter 0 qədər prosesi, və ya biz heç svopları etmək qədər. 

Svop counter sıfırlamak 0 artıq 0 deyil, əgər. Sonra hər baxmaq elementləri qonşu cüt. Bu iki elementlər varsa etməmək üçün, onları dəyişdirmək, və svop counter 1 əlavə edin. Siz haqqında düşünür istəyirsinizsə bu görüntüləmək əvvəl, Bu aşağı hərəkət edəcək ki, görürsünüz sol qiymətləndirilir elementləri və ali sağ elementləri qiymətləndirilir səmərəli biz istəyirik nə, olan qruplar hərəkət edir ki, yol elementləri. Nin necə görüntüləmək imkan bizim array istifadə ola bilər Biz test üçün istifadə ki, bu alqoritmlər həyata. Biz yenə burada çeşidlənməmiş sıra var elementləri bütün göstərilən qırmızı olan. Mən svop counter müəyyən bir nonzero dəyəri. Mən özbaşına seçdi mənfi 1 var Bu 0 deyil. Biz bu prosesi təkrar etmək istəyirəm swap counter qədər 0. Mən svop müəyyən Buna görə bəzi qeyri-sıfır dəyəri counter, başqa, çünki svop counter 0 olardı. Biz hətta başlamaq deyil alqoritmi prosesi. Belə ki, yenə addımlar are-- svop counter sıfırlamak 0, sonra hər bitişik baxmaq cüt və onlar üçün həyata əgər, onları dəyişdirmək və 1 əlavə svop counter. Belə ki, bu prosesi başlasın. Beləliklə, biz nə ilk şey biz 0 svop counter müəyyən və sonra axtarır başlamaq hər bitişik cüt. 

Beləliklə, biz ilk 5 və 2 baxaraq başlamaq. Biz onların həyata var ki, görəcəksiniz sifariş və biz onları dəyişdirmək. Və biz mübadilə counter 1 əlavə edin. Belə ki, indi bizim svop counter 1, və 2 və 5 işə edilmişdir. İndi biz yenidən prosesi təkrar edin. 

Biz növbəti bitişik cüt baxmaq, 5 və onlar da üçün bitti 1 var, belə ki, biz onları dəyişdirmək və əlavə Svop counter 1. Sonra biz 5 və 3 oldu. Onlar üçün həyata, belə ki, biz dəyişdirmək Onlara və biz mübadilə counter 1 əlavə edin. Sonra biz 5 və 6 oldu. Onlar üçün istəyirik, biz, həqiqətən, yoxdur bir şey bu dəfə dəyişdirmək lazımdır. Sonra biz 6 və 4 oldu. Onlar qaydada həyata də istəyirik, biz dəyişdirmək Onlara və biz mübadilə counter 1 əlavə edin. 

İndi baş nə görürsünüz. Biz sonuna 6 bütün yol hərəkət etdik. Seçim sort Belə ki, siz var əgər video görüldü nə etdik oldu biz hərəkət sona çatdı binasında kiçik elementləri mahiyyətcə sorted array ən böyük, kiçik sağ. Bubble növ halda, biz əgər bu alqoritm sonra, biz, həqiqətən, bina olacaq sağdan sıralanır array kiçik, böyük sol. Biz səmərəli 6, bubbled var böyük dəyəri, sonuna bütün yol. 

Və belə ki, biz indi elan edə bilər ki, çeşidlənir ki, və gələcəkdə iterations-- array keçir again-- biz artıq 6 hesab yoxdur. Biz yalnız hesab etmək lazımdır çeşidlənməmiş elementləri zaman biz qonşu cüt baxırıq. Beləliklə, biz bir başa bubble sırala keçir. Belə ki, indi biz suala geri, svop counter 0 qədər deyirəm. Yaxşı svop counter 4, belə ki, biz gedirik yenidən bu prosesi təkrar saxlamaq. 

Biz svop counter sıfırlamak olacaq 0 və hər bitişik cüt baxmaq. Belə ki, biz onlar 1 var 2 ilə başlamaq və qaydada həyata, belə ki, biz onları dəyişdirmək və biz mübadilə counter 1 əlavə edin. 2 və 3, onlar üçün istəyirik. Biz bir şey etmək lazım deyil. 3 və 5 üçün var. Biz orada bir şey etmək lazım deyil. 

5 və 4, onlar həyata sifariş və biz onları dəyişdirmək və əlavə etmək lazımdır Svop counter 1. İndi biz, 5 hərəkət etdik növbəti böyük element, çeşidlənməmiş hissəsi sonuna. Beləliklə, biz indi zəng edə bilərsiniz sıralanır hissəsinin hissəsidir. 

İndi baxırıq ekran və yəqin ki, demək olar, , mən array kimi İndi çeşidlənir. Amma biz hələ ki, sübut edə bilməz. Biz zəmanət yoxdur ki, sıralanır. Amma bu harada svop deyil counter oyun minir olacaq. 

Beləliklə, biz bir keçid tamamladım. svop counter 2. Beləliklə, biz demək olacaq yenə bu proses, svop counter 0 qədər deyirəm. 0 svop counter sıfırlamak. Belə ki, biz yenidən lazımdır. 

İndi hər bitişik cüt baxmaq. Ki, üçün 1 və 2 var. 2 və 3 üçün var. 3 və 4 üçün var. Belə ki, bu nöqtədə, biz tamamladım qeyd hər bitişik cüt baxaraq, lakin swap counter hələ 0. 

Biz keçid yoxsa hansı elementləri, onlar ilə, qaydada olmalıdır Bu prosesin əsasında. Və belə növ bir səmərəliliyinin, ki, biz kompüter alimləri sevgi, indi elan edə bilər ki, bütün array olmalıdır Biz çünki, sıralaması hər hansı elementləri dəyişdirmək lazımdır. Bu olduqca gözəl. 

Belə ki, nə ən pis halda var bubble növ ilə ssenari? Ən pis halda array var tamamilə əks qaydada, və biz hər bir bubble var böyük elementləri bütün array arasında bir yoldur. Və biz səmərəli də var bubble kiçik elementləri bütün geri Çox array arasında bütün yol. Belə ki, n elementlərin hər hərəkət var digər n elementləri bütün arasında. Belə ki, ən pis ssenari var. Ən yaxşı halda ssenari olsa da, bu seçim sort qədər fərqli. array artıq biz getmək zaman sıralanır. Biz hər hansı bir etmək yoxdur ilk pası svopları. Belə ki, biz baxmaq üçün ola bilər az elementləri, sağ? Biz bu təkrar yoxdur artıq bir neçə dəfə emal. 

Belə ki, nə deməkdir? Belə ki, nə ən pis ssenari var bubble sort üçün, və nə bubble sort üçün ən yaxşı ssenari? Bu tahmin mi? Ən pis halda təkrarlamaq lazımdır bütün n elementləri n dəfə arasında. Belə ki, ən pis halda kvadrat n edilir. 

Array mükəmməl olarsa sorted baxmayaraq, yalnız hər baxmaq bir dəfə elementləri. Və svop counter hələ 0 olduqda, Bu array çeşidlənir demək olar. Və belə ən yaxşı halda, bu seçilməsi daha həqiqətən yaxşı sort N omega var. 

Mən Doug Lloyd edirəm. Bu CS50 edir.