>> [MÜZİK OYUN]
Doug LLOYD: Pekala, Kabarcık sıralama bir algoritma
Eğer elemanlarının bir dizi sıralamak için kullanabilirsiniz.
Nasıl çalıştığına bir göz atalım.
>> Yani temel fikir arkasında kabarcık sıralama budur.
Biz genellikle daha yükseklere taşımak istiyoruz Genellikle sağa doğru değerli elemanları,
ve genellikle değerli elemanları alt sola, biz beklediğiniz gibi.
Biz düşük şeyler olmak istiyorum başlangıç ​​ve daha yüksek şeyler
sonunda olmak.
>> Bunu nasıl yapacağız?
Peki pseudocode kodunda, Biz diyelim, söyleyebiliriz
sıfır olmayan bir değere bir takas sayacı ayarlayın.
Biz ikinci bunu neden biz göreceğiz.
Ve sonra biz şu tekrarlayın swap sayacı 0 olana kadar süreç,
ya da hiç swapları yapana kadar.
>> Takas sayacını sıfırlayın 0 Zaten 0 değilse.
Sonra her bakmak elemanların bitişik çifti.
Bu iki unsur ise değil sırayla, takas,
ve takas sayacına 1 eklenir.
Hakkında düşünüyorsanız Bu onu görselleştirmek önce,
Bu alt hareket edeceğini fark sola değerli elemanlar
ve daha yüksek, sağ unsurları değerli etkili biz ne yapmak istediğinizi yapıyor,
olanlar grupları taşımak olduğunu bu şekilde elemanların.
En bu nasıl görselleştirmek edelim Bizim dizi kullanarak görünebilir
Biz sınamak için kullanılan bu Bu algoritmalar dışarı.
Biz burada tekrar bir sıralanmamış dizi var tüm elemanları ile gösterilen
kırmızı olmak.
Ve ben takas sayacı ayarlamak sıfır olmayan bir değere.
Ben keyfi seçti Negatif 1-- 0 değil.
Biz bu işlemi tekrarlamak istiyorum swap sayacı kadar 0'dır.
Benim takas set Bu yüzden Bazı sıfır olmayan bir değere karşı,
çünkü aksi takdirde swap sayacı 0 olacaktır.
Biz bile başlamak olmaz algoritmanın bir işlem.
Yani yine adımlar mudur takas sayacını sıfırlamak
0, daha sonra her bitişik bakmak çifti, onlar sıra dışı iseniz,
Bunları takas ve 1 ekleyin takas sayaç.
Yani bu süreci başlasın.
Yani biz bunu ilk şey Biz 0 takas sayacı ayarlayın
ve sonra aramaya başlamak Her bitişik çifti.
>> Bu yüzden ilk 5 ve 2 bakarak başlayın.
Biz onlar dışarı görüyoruz sipariş ve bu yüzden onları takas.
Ve biz takas sayacına 1 eklenir.
Yani şimdi bizim takas sayacı 1, 2 ve 5 anahtarlamalı oylandı.
Şimdi tekrar işlemi yineleyin.
>> Önümüzdeki bitişik çifti bakmak, 5 ve onlar da sipariş bitti 1--,
bu yüzden onları takas ve ekleme Swap sayacına 1.
Sonra 5 ve 3 bak.
Bunlar bozuk, bu yüzden takas Onları biz swap sayacına 1 eklenir.
Sonra 5 ve 6 bakmak.
Bunlar sırayla konum, bu yüzden aslında yok için herşeyi bu kez takas gerekir.
Sonra 6 ve 4 bakmak.
Bunlar bozuk da, o yüzden biz takas Onları biz swap sayacına 1 eklenir.
>> Şimdi ne olduğunu fark.
Biz sonuna kadar 6 Bütün yol taşındım.
Seçim tür Yani, yasiyorsaniz o video görüldü ne yaptığımız oldu
Biz hareket sona erdi bina küçük elemanları
esasen Sıralı dizi büyük için en küçük sağa sola.
Kabarcık tür durumda, eğer Bu, özel bir algoritma sonra,
biz aslında bina için gidiyoruz Sağ taraftan sıralanan dizi
küçüğüne, en büyük sola.
Biz etkili bir şekilde 6, kabarmış var en büyük değer, sonuna kadar tüm yol.
>> Ve böylece biz şimdi bildirebilirsiniz Bu sıralanır olduğunu,
ve gelecekteki iterations-- dizinin geçiyor vasıtasıyla yine
artık 6 düşünmek zorunda değilsiniz.
Biz sadece düşünmek zorundayız sıralanmamış elemanlar
ne zaman bitişik çiftler bakıyoruz.
Yani biz bir bitirdikten kabarcık sıralama geçer.
Yani şimdi biz soruya geri dönmek, swap sayacı 0 olana kadar tekrarlayın.
Peki takas sayacı 4, bu yüzden gidiyoruz
Yine bu işlemi tekrar tutmak için.
>> Biz takas sayacını sıfırlamak için gidiyoruz 0 ve her komşu çifti bak.
Bu yüzden onlar konum 1-- 2 ile başlar ve sıra dışı, bu yüzden onları takas
ve biz takas sayacına 1 eklenir.
2 ve 3, onlar sırayla konum.
Biz bir şey yapmanız gerekmez.
3 ve 5 olarak sıralanmıştır.
Biz orada bir şey yapmanıza gerek yok.
>> 5 ve 4, onlar dışarı düzen, ve bu yüzden biz
Bunları takas ve eklemeniz gerekir Swap sayacına 1.
Ve şimdi biz 5 hareket ettik sonraki en büyük unsur,
sıralanmamış kısmının ucuna.
Yani biz şimdi çağırabilirsiniz sıralanmış kısmının bir parçası.
>> Şimdi bakıyoruz Ekran ve muhtemelen söyleyebilirim,
, I can dizisi bu kadar Şu anda sıralanır.
Ama biz henüz ispat edemez.
Biz bir garanti yok o sıralanmış oluyor.
Ama bu nereye takas olduğunu sayaç devreye girer gidiyor.
>> Bu yüzden bir geçiş tamamladık.
Takas sayacı 2 'dir.
Bu yüzden tekrar gidiyoruz Yine bu proses,
swap sayacı 0 olana kadar tekrarlayın.
0 takas sayacını sıfırlayın.
Yani biz sıfırlamak gerekir.
>> Şimdi her bitişik çifti bak.
Bu, sırayla, 1 ve 2 bu.
2 ve 3 olarak sıralanmıştır.
3 ve 4 olarak sıralanmıştır.
Yani bu noktada, biz tamamladık fark Her komşu çifti bakarak,
ancak takas sayacı hala 0'dır.
>> Biz geçmek yoksa Herhangi elemanları, daha sonra
tarafından sırayla olmalıdır Bu sürecin erdem.
Ve böylece tür bir etkinlik, biz bilgisayar bilim seviyorum,
Şimdi bildirebilirsiniz edilir Tüm dizi gerekir
we did not, çünkü sıralanabilir Herhangi elemanları takas etmek zorunda.
Bu oldukça güzel.
>> Peki kötü durumda bulunuyor kabarcık sıralama ile senaryo?
En kötü durumda dizidir Tamamen tersten,
ve bu yüzden her kabarcık var Büyük bütün elemanları
dizi boyunca yol.
Ve biz etkili bir de var kabarcık küçük elemanların hepsi geri
Çok dizi boyunca tüm yol.
Yani n elemanlarının her hareket etmek zorundadır Diğer n elemanlarının tamamında.
Yani en kötü senaryo.
En iyi durumda senaryo olsa da, bu
Seçim sıralama biraz farklı.
Dizi zaten Biz giderken sıralanır.
Biz herhangi bir yapmak zorunda değilsiniz ilk geçişte swapları.
Yani biz bakmak zorunda kalabilirsiniz Daha az unsurları, değil mi?
Biz bu tekrarlamak zorunda değilsiniz üzerinde birkaç kez işlemek.
>> Peki bu ne anlama geliyor?
Peki en kötü senaryo var kabarcık sıralama için, ve ne
kabarcık sıralama için en iyi senaryo?
Bunu tahmin mü?
En kötü durumda, yineleme var Bütün n elemanlı n kere arasında.
Yani en kötü durum n karesi edilir.
>> Dizi mükemmel değilse Sıralanan olsa da, sadece
Her bakmak zorunda Bir kez elemanları.
Ve takas sayacı hala 0 ise, Bu dizi sıralanır söyleyebiliriz.
Böylece en iyi durumda, bu seçim daha aslında daha iyi
sort-- o n omega var.
>> Ben Doug Lloyd değilim.
Bu CS50 olduğunu.