MIT Açık Ders malzemeleri

http://ocw.mit.edu

6.046J Algoritmalara Giriş, Güz 2005

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

Erik Demaine ve Charles Leiserson, 6.046J Introduction to Algorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010).

Lisans: Creative Commons Attribution-Noncommercial-Share Alike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

DERS 5

Bu gün sorting yani sıralama konusunda konuşacağız, sanıyorum bu size büyük bir sürpriz olmayacak. Aslında bu konuda bir süredir konuşuyoruz ama bugün bunu biraz daha üst düzeyde ele alacağız ve bugüne kadar yaptığımız bazı varsayımları sorgulayacağız. Ve bugün “biz ne kadar hızlı sıralama yapabiliriz?” sorusunu soracağız. Bu çok doğal bir soru ve cevabı bildiğinizi düşünebilirsiniz, belki de biliyorsunuzdur. Bunun yanıtının ne olduğu konusunda fikri olan var mı? Birkaç olası yanıt var ve çoğu da kısmen doğrudur. Bu sabah sizin uyanmanızı sağlamak için bu yanıtlardan bir kısmını duymak istiyorum. Pardon?

Θ(n), log n; evet bu güzel bir yanıt ve çoğunlukla da doğrudur. Başka öneriler var mı? ; eğer sadece komşu elemanların yerini değiştirme izniniz varsa bu da doğru. Bu oldukça yakın bir yanıttı ama ben aslında bütün yanıtların doğru olmasını sağlamaya çalışıyorum. Genelde doğru cevap değildir ama bazı modellerde öyledir. Θ(n) de bazı durumlarda doğru cevaptır, ama gerçek doğru cevap “koşullara bağlı” olmalıdır. Bu bugünkü dersin temel konusu olacak. Doğru cevap kullanmanıza izin verilen computational model yani hesaba dayalı modele bağlıdır. Ve derslerde özellikle yaptığımız sorting yani sıralama işleminde dikkat ettiğimiz konu elemanların sırası, bu elemanlarla işlem yaparken nelere izin verildiği ve bu işlemleri yaptığınız zaman bunların sırasını bulmanız.. Yani model bu elemanlarla ne yapabileceğinize bağlı olarak değişiyor.

Bir kaç tane sıralama algoritmasını görmüştük. Bunların bazılarını söylemek ister misiniz? Ben dört tane işlediğimizi düşünüyorum ama siz daha fazla algoritma da bilebilirsiniz. Quicksort yani çabuk sıralama; devam edin. Heapsort yani yığın sıralaması. Merge sort yani birleştirme sıralaması, iyi, birinci derse kadar olanları hatırlıyorsunuz. Başka var mı? Insertion sort yani araya yerleştirme sıralaması; tamam bugün bütün bunlara hâkimsiniz. Neden bilmiyorum ama ilk ikisi tek kelime ve bu ikisi de iki kelimeden oluşmuş. Bu herhalde bir stil.. Pekiyi, çabuk sıralamanın koşma süresi nedir?

Bu biraz şaşırtıcıdır; ortalama durumda n lgn ama, çabuk sıralamayı rasgele hale getirirsek, rasgele çabuk sıralama beklenen her giriş diziliminde n lgn süresinde çalışır. O halde n lgn rasgele hali diyelim. Şu Θ dır. Ve bildiğimiz çabuk sıralamanın en kötü durumu için ilk elemanı bölüntü elemanı olarak seçersiniz ve koşma süresi olur. Yığın sıralamasının koşma süresi nedir? Her zaman n lgn dir. Birleştirme sıralamasınkini de hatırlayacağınızı umuyorum. n lgn. Ve araya yerleştirme sıralaması neydi? . Bütün bu algoritmaların hiç birisi n lgn’den daha hızlı çalışmıyor, o halde kendimize sormamız gereken soru “Θ (n logn) den daha iyi bir sonuç elde edebilir miyiz?” olacak.

Ve bugün bu sorunun yanıtını bir anlamda hem evet hem hayır olarak bulacağız. Ama bu algoritmaların hepsinin model açısından elemanlarıyla ne yapılabileceği ile ilgili bir ortak yönleri var. Bu modelin ne olabileceği konusunda tahminleriniz var mı? Evet? Eleman çiftlerini birbiriyle karşılaştırıyorsunuz, doğru. Aslında her dört algoritmanın da kullandığı model bu ve bu modelde n lgn alabileceğiniz en iyi sonuç. Şu ana kadar sadece comparison sorting yani karşılaştırmalı sıralama algoritmalarına, başka bir deyişle “karşılaştırma sıralamalarına” baktık. Ve bu uygulamada bu model sıralama problemini çözmeniz için izin verilen modeldir.

Bu modelde izin verilen tek şey, elemanları karşılaştırıp, daha küçük, daha büyük, küçük veya eşit, büyük veya eşit, ya da eşittir işlemlerini kullanarak bunları göreceli olarak sıralamaktır. Bu algoritmalarla ilgili bir sınırlamadır. Bu bir bakıma bizim hangi tür elemanlarla işlem yaptığımızı belirler. Bu elemanlar bizim karşılaştırma yapabileceğimiz elemanlardır. Belirli bir düzenleri vardır, bazıları değer olarak küçük, bazıları büyüktür, ama bu durum algoritmaya da bir sınır getirir. Dersiniz ki, “sayıları sıralayabiliyorum ama onları sadece karşılaştırmaya iznim var”; yani onları çarpmaya veya değişik şeyler yapmaya izin yok. Bu karşılaştırmalı sıralama modelidir. Bu derste, standart matematiksel ilerleme mantığı çerçevesinde, bir teorem ele alınır, önce kanıtlanır, sonra da aykırı bir örnek verilir. Matematik her zaman iyidir.

Hiçbir karşılaştırma sıralama algoritmasının n lgn’den daha iyi çalışamayacağını kanıtlayacağız. Karşılaştırmalar. Teoremi belirteceğiz ve bunu kanıtlayacağız; ve sonra buna aykırı bir örnek vererek, eğer karşılaştırmalı sıralama modelinin dışına çıkarsak bundan daha iyi sonuçlar elde edebileceğimizi, bazı durumlarda doğrusal zamana yaklaşabileceğimizi yani n lgn’ den daha iyi bir sonuç alacağımızı göstereceğiz. Bugün yapacağımız şey budur.

Ama öncelikle karşılaştırmalı modele bağlı kalacağız ve n lgn karşılaştırmalarına neden ihtiyacımız olduğunu ve sınırımızın neden bu olduğunu anlamaya çalışacağız. Bunu gerçekleştirmek için karar ağaçları denilen bir kavrama bakacağız ve bunun bir algoritmada kullanılabilecek başka bir model olduğunu göreceğiz; öte yandan bu model karşılaştırma modelinden biraz daha geneldir. Şimdi öngörümüzü geliştirmek için örnek yapalım: Diyelim ki üç elemanı sıralamak istiyoruz. Bu çok karmaşık bir işlem değil ama üç elemanın sıralanmasıyla ilgili karar ağacını çizeceğiz; bu çözümlerden bir tanesi olabilir.

Aslında bu kesinlikle bir algoritma ama sözde kod yerine bir ağaç şeklinde çizilmiş. Bu ağacın anlamı her düğüm yada nod’da bir karşılaştırma yapmanızdadır. Bu diyor ki, ile ’yi karşılaştır. Eğer ’ den küçükse o zaman bu yola doğru git; eğer ’ den büyükse o zaman şu yola git ve ondan sonra devam et. Son yaprağa vardığınızda cevabı bulursunuz. Unutmayın sıralama problemlerinde amaç girişlerin sıralanmasını sağlayacak giriş permütasyonlarını bulmaktır. Örnek olarak 9, 4, 6 gibi bir sayı dizisinde bunu deneyelim. 9, 4 ve 6 yı sıralamak istiyoruz bunun için önce birinci elemanı ikinci elemanla karşılaştırıyoruz. 9, 4’den daha büyük olduğu için bu yolu takip edeceğiz. Sonra birinci elemanı üçüncü elemanla yani 9 u 6 ile karşılaştıracağız. 9, 6’dan büyük onun için bu yola gideceğiz. Sonra da ikinci elemanı üçüncü elemanla karşılaştıracağız 4, 6’dan küçük, onun için bu yolu takip edeceğiz ve sonra da diyeceğiz ki bu elemanların doğru permütasyonudur. yi temsil eden 4 ü alacaksınız, ü temsil eden 6 yı alacaksınız, ondan sonra da i temsil eden 9’u alacaksınız. Evet, sistem böyle çalışır ve ben bunu doğru yazdıysam, bu, karar ağacı modelinde bir sıralama algoritmasıdır.

Bu oyunun genel kurallarını size anlatayım. Çoğunlukla elimizde sıralamak istediğimiz n sayıda eleman olur. Ben burada n=3 seçtim, çünkü bu ağaçlar çok çabuk büyürler.. Her içsel nodun yada düğümün, yani yaprak olmayan her ayrımın, i:j gibi bir etiketi vardır ve i ile j, 1 ile n arasında değerlerdir. Yani biz yi ile karşılaştırırız ve her düğümden iki alt ağaç çıkar. Soldaki alt ağaç bize algoritmanın, karşılaştırmada küçük çıkma durumunda, takip eden adımlarda ne yapacağını söyler.

Burada dikkat etmemiz gereken bir şey daha var aslında; iki değer birbirine eşit de olabilir. Bu durumda dikkat etmeniz gereken şey soldaki alt ağacın eşit yada daha küçük durumunu, sağdaki alt ağacın da kesinlikle daha büyük durumunu temsil etmesidir. Bu daha önce yaptıklarımızdan daha hassas bir yaklaşımdır. Burada bütün elemanlar birbirinden farklı değerler taşıyordu onun için sorun yoktu ama genelde eşitlik durumunu da göz önünde tutmak zorundayız.

Bunlar iç nodlar yada düğümler ve sonunda her yaprak ayrı bir permütasyon verir. Bu nedenle permütasyonun bu sıralama problemine çözüm olması için, permütasyonun elemanları sıralayabilme özelliği olması gerekir. Bunu sıralama problemlerini tanımladığımız birinci dersten hatırlayacaksınız; n sayıdaki şeyin permütasyonu den daha küçük veya ona eşit gibi açıklanmıştı. Evet, bu bir karar ağacının tanımıdır. Bu özellikte olan herhangi bir ikili ağaç bu özellikleri karşılamak zorundadır, yani bir bakıma bir sıralama algoritması olur ve bu karar ağacı modelindeki bir sıralama algoritmasıdır.

Şimdi tahmin ettiğiniz gibi bu aslında karşılaştırma modelinden çok farklı bir yaklaşım değildir, Size bir karşılaştırmalı sıralama algoritması verirsem, ki bunlardan dört tanesini görmüştük; çabuk sıralama, yığın sıralama, birleştirme sıralaması ve araya yerleştirme sıralamalarıydı, bütün bunlar bir karar ağacı modeline dönüştürülebilir. Bu aslında algoritmanın ne yaptığının grafik bir anlatımıdır, ama bir algoritmayı yazarken çok yararlı bir yaklaşım da değildir. Bunu neden söylediğim konusunda tahmini olan var mı?

Biz bu resimleri neden bir çabuk sıralama yada birleştirme sıralamasını tanımlamak için çizmiyoruz? Evet, bu girişin boyutuna bağlıdır, bu iyi bir görüş; yani bu ağaç özgül olarak n’nin değerine orantılı olacağı için aslında jenerik yani cinsine özgü değildir. Şimdi bu evrede bu karar ağaçlarından birinin herhangi bir n değerinin yapılanması ile ilgili olarak her giriş boyutunda çalışacak gerçek algoritmalarını yazmaya çalışabiliriz; ama bu bile algoritmayı yazmada uygun bir sunum olmaz.

Bunun nedenini anlayabilmeniz için, bir sıralama algoritmasını bir karar ağacına dönüştürecek transformasyonu yada dönüşümü yazalım. Bu yararsız bir model değil, öyle olsaydı size bunu söylemezdim. Bunun yararı n lgn’ den daha iyi bir sonuç alamayacağımızı kanıtlamaktır; yoksa bunu bir algoritma olarak yazarak uygulamada çok büyük yarar sağlayacağınızı söylemiyorum. Sanal bir karar ağacı gibi çalışan bir bilgisayarınız olsaydı gene de böyle olacaktı.

Ama gene de bu teorimi kanıtlayalım, yani karar ağaçlarının bir bakıma karşılaştırmalı sıralama algoritmaların bir modeli olduğunu söyleyelim, buna da karşılaştırma sıralamaları diyelim. Bu bir dönüştürme ve her n değeri için bir ağaç oluşturacağız. Karar ağacı n’ye bağlı değişecek; algoritma umut ediyoruz ki n’ye bağlı fakat bütün n değerleri için geçerli olacak. Ve algoritmanın bir çatal gibi ikiye bölündüğünü, karşılaştırma durumunda bir sol alt ağaç ve bir de sağ alt ağaç olduğunu varsayacağız.

Birleştirme sıralaması gibi bir karşılaştırma sıralamasını ele alırsak, bu birçok şeyi yapabilir. Bununla index aritmetiği yani dizin aritmetiği, yineleme gibi uygulamaları gerçekleştirebiliriz. Ama bir noktada bu bir karşılaştırma yaptığında diyebiliriz “bu algoritma iki bölümden oluşuyor. Karşılaştırma sonucunda eşit veya küçük durumları burada ve büyük durumları şurada olur.” Böylece bu yolla bir ağaç oluşturabilirsiniz. Bir bakıma bu ağacın yaptığı şey bu algoritmanın bütün olası uygulamalarını listelemek ve bütün olası değerler konusunda karşılaştırma yapmaktır.

Biz bunlara tüm olası instruction traces yani komut izleri diyeceğiz. Bu algoritma tarafından gerçekleştirilen bütün komutlara bakarsanız, ’den ’ye kadar değişen bütün olası giriş dizilimlerinde, tüm karşılaştırmaların nasıl sonuçlandığı ve algoritmanın ne yaptığını göz önüne alacak olursanız sonunda bir ağaç elde edersiniz. Şimdi, bu ağaç kabaca hangi boyutta olur? n’nin bir fonksiyonu olarak.. Evet? İyi; eğer n uzunluğunda bir listedeki bütün olasılıkları sıralayacaksa o zaman yapraklar düzeyinde bütün bu elemanların permütasyonlarını ele alması gerekir.

Bu çok kapsamlı bir iş… n eleman üzerinde çok fazla yayılım vardır. Bunlar n-faktoryel yani n-çarpınım düzeyinde. n-faktoryel aslında üstel, yani çok büyük. Bu nedenle bu ağaç çok büyük olacak. Bu ağaç n boyutundaki bir giriş için üstel düzeyde olacak. Bu nedenle, bu yazılabilir olsa da biz algoritmaları bir karar ağacı şeklinde yazmıyoruz. Yazarsak bu kompakt yada kısa bir anlatım olmaz.. Biz algoritmaları sabit bir uzunluğu olan sözde kodla yazarız; bu algoritmanın özlü bir tanımıdır. Burada ağacın uzunluğu n’ye üstel olarak bağlıydı ve bu çok yararlı değil, çünkü bunu yazmak yada çizmek çok uzun zaman alır. Ama gene de biz bunu bu karşılaştırmalı sıralama algoritmalarını çözümlemede uygun bir araç olarak kullanabiliriz. Elimizde her şey var. Aslında her algoritma bu yolla bir karar ağacına dönüştürülebilir.

Şimdi, buna baktığımızda, bu karar ağacındaki yaprak sayısının gerçekten çok büyük olduğu gözlemini yapıyoruz. Yapraklarla ilgili birazdan konuşmak istiyorum; yapraklara değinmeden önce ağacın derinliğiyle ilgili biraz konuşalım. Bu karar ağacı, algoritmanın bütün olası uygulamalarını içerir. Herhangi bir uygulamaya baktığımda, yani kökten yaprağa giden herhangi bir yolu izlediğimde, koşma süresi yada uygulama tarafından yapılacak karşılaştırma sayısı o yolun uzunluğuna eşit.

Bu nedenle de n uzunluğundaki bütün girişleri kapsayacak en kötü koşma süresi, ne olur? n-1 olabilir. Bu karar ağacının yapısına bağlıdır. Ama karar ağacının bir fonksiyonu olarak buna ne denir? En uzun yol, doğru, ve buna ağacın yüksekliği denir. Evet işte ölçmek istediğimiz değer bu ve ağacın yüksekliğinin en az n lgn olmasını istiyoruz; önünde bir Ω olacak. Kanıtlayacağımız şey bu.

Ve burada kullanacağımız tek şey bu ağacın yapraklarının çok fazla olduğu yani n faktoryel olduğu.. Bu karar ağacı sıralamasındaki alt sınırdır. Ve alt sınır bize belirli sabit faktörlere kadar n elemanını sıralayacak bir karar ağacının yüksekliğinin en az n lgn olacağını belirtir. İşte teoremimiz bu; şimdi bu teoremi kanıtlayacağız. Ve bu ağaçtaki yaprak sayısının en az n-faktöryel olduğu varsayımı kullanacağız.

Çünkü, girişlerde n-faktöryel devinim var ve bunların hepsi gerçekleşebilir. Ve bu algoritmanın doğru çalışması için bu devinimlerin herhangi birini bir şekilde algılaması gerekir. Şimdi bunu çok çabuk yapabilir. Biz en fazla n lgn kadar karşılaştırma olsun istiyoruz, çünkü bunun mümkün olduğunu biliyoruz. Ağacın derinliğinin çok fazla olması gerekmez ama alttaki yaprak sayısı çok fazla olmalı. Bu durumda n-faktöryel yaprak olacak şekilde dallanması lazım çünkü her seçenek için doğru cevabı bulması lazım. Bu bir anlamda ayırt etmemiz gereken muhtemel girişleri saymaktır. Bu yaprak sayımızdır; şu anda ilgilendiğimiz şey ağacın yüksekliği. Ağacın yüksekliğine h diyelim.

Eğer elimde h yüksekliğinde bir ağaç varsa bunun kaç tane yaprağı olabilir? En fazla kaç yapraktan oluşabilir? , doğru. Çünkü bu ağaç bir ikili ağaç ve

karşılaştırma ağaçlarının her zaman ikili dallanma yapısı vardır; bu durumda eğer ağacın yüksekliği h ise bu ağaçtaki yaprak sayısı da en fazla olur. Şimdi, bu bana bir ilişki veriyor: Yaprak sayısı bir taraftan n-faktöryele büyük-eşit, öteki taraftan da ‘ye küçük-eşit.. Böylece eğer varsayımım doğru ise, n-faktöryel, ye eşit veya ondan küçüktür.

Şimdi, yine h ile n-faktöryel bağlamında ilgileniyorsak, bunu logaritma kullanarak çözebiliriz. Burada yönleri de değiştireceğim. h en azından ‘e eşit, çünkü burada bir 2 var ve bunun n faktöriyeli var. Burada bu eşitsizliği şu eşitsizlikten elde etmek için bir özellik kullanıyorum; tekniğini açıklamıyorum ama bunun teknik bir konu olduğunun farkında olmanız önemli.

Uygulayacağım genel prensip elimde bir eşitsizliğin olduğu ve her iki tarafta da aynı işlemi yaptığımda eşitsizliğin yine geçerli olacağı olasılığıdır. Ama bunun gerçekçi olabilmesi için yaptığım uygulama ile ilgili bir niteliğin olması gerek; evet, bunun bir monotonik transformasyon yani tek düzey dönüşüm olması gerekiyor. Burada kullandığım logaritmanın tek düzey artan bir fonksiyon olması. Bu oldukça önemli; eğer iki tarafı da -1 ile çarparsam, ki bu azalan bir fonksiyondur, eşitsizliğin evrilmesi gerekir. Buradaki eşitsizlik evrilmediğine göre logaritmanın monotonik artan bir fonksiyon olduğunu anlıyorum. Eğer logaritma görürseniz bu doğrudur, ama burada dikkatli olmamız gerekir.

Şimdi buradaki logaritmayı hesaplamak için n! ‘in bir approximation’ına yani, yaklaştırımına gerek var. n! için iyi bir yaklaşım biliyor musunuz? Yani bu eşitliğin formülünü değil, ismini soruyorum. Stirling formülü. İyi, hepiniz Stirling’i hatırlıyorsunuz. Benim sadece en yüksek düzeyli terime ihtiyacım var ve sanırım o da budur. n! en azından lg dir. Evet, burada gerekli olan şey bu.

Şimdi logaritmaların özelliklerinden faydalanarak n’ yi dışarıya alacağım. Bu da bana n lg (n/e) yi verecek.

Bundan sonra lg (n/e) yi basitleştirebilirim. Bu lg n - lg e demektir. Böylece bu n(lg n – lg e) olur. lg e bir sabittir ve n ile büyüyen lg n ile karşılaştırıldığında çok küçük kalır. Bu Ω (n lgn) olur; bizi ilgilendiren sadece baştaki terimdir. Aslında bu Θ (n lgn) ama elimizde büyük-eşit durumu olduğu için biz burada bunu Ω olarak değerlendireceğiz. Buraya Ω yerine Θ koyduğumuz zaman bu algoritmamızı daha güçlendirmez.

Tabii bütün algoritmaların koşma süresi n log n değildir veya bunlarla n log n karşılaştırmaları yapılamaz. Bazıları ile yapılabilir, bazıları ile zordur ama sonuçta bu hepsinin en azından n logn yüksekliğine ihtiyaç duyduğunu kanıtlar. İşte burada yaprakların sayısını gözlemleyip Stirling formülünü hatırlarsanız kanıt ortaya çıkar. Bu kanıtı bilmeniz gerekiyor. Aslında bu tür problemlerde bu teknikle n logn süresine gerek duyulduğunu, elinizde bir karar ağacı modeli varsa göstermeniz mümkün.

Bu önemli. Algoritmamızın bir karar ağacı olarak gösterilmesine ihtiyaç var ve özellikle bu dönüşümle bütün karşılaştırmalı sıralamaların bir karar ağacı olarak gösterilebileceğini biliyoruz. Ama bazı sıralama algoritmaları vardır ki bunları bir karar ağacı olarak gösteremezsiniz. Birazdan bu konuya gireceğiz; ama buna girmeden önce “bu karar ağacı sıralamasının alt sınırı ile ilgili bir teoremdir” demiştim. Doğal olarak bununla karşılaştırmalı sıralamada da bir alt sınır elde ediyoruz.

Ve bu, özellikle birleştirme sıralaması ve yığın sıralamasının asimptotik olarak optimal yani en uygun olduğunu bize gösterir. Buradan görürüz ki asimptotik simgelem bağlamında n’ ye olan bağlılıkları bize sabitleri ihmal etme izni verir ve bu algoritmalar n’ nin büyümesi konusunda optimal yani en uygun algoritmalardır; ama bu sadece karşılaştırmalı modellerde geçerlidir. Yani karşılaştırmalı sıralama algoritmaların arasında bunlar asimptotik olarak optimal olanlardır. Belirli sabit faktörlere kadar bunlar en az sayıda karşılaştırma kullanırlar. Aslında bunların koşma sürelerini belirleyen ana olgu karşılaştırma sayılarıdır yani Θ( n lgn) dir. Bu iyi haberdir. Bu evrede rasgele algoritmalarda da ne olduğundan biraz bahsetmem gerekiyor. Şu ana kadar burada anlattıklarım bir bakıma sadece deterministik yani belirleyici algoritmalar için geçerlidir.

Burada rasgele algoritmalar kullandığımda neyin değişeceğini yada nerede bir belirleyici karşılaştırma sıralaması olduğunu varsaydığımı fark eden var mı? Bu biraz incelikli bir şey ve ben de bunu bu sabah notlarımı okurken fark ettim ve “bir dakika” dedim. Size bir ipucu vereceğim; o buralarda bir yerde dünyanın sağ tarafında.. Eğer elimde belirleyici bir algoritma varsa, algoritma her adımında belirleyici davranır.

Bu algoritmanın herhangi bir noktaya kadar yaptığı bütün karşılaştırmaları bilirsem bu algoritmanın ne yapacağı bellidir. Ama elimde rastgele bir algoritma varsa, o zaman sonuç yazı tura atışlarının sonucuna da bağlıdır. Burada neyin değiştiği konusunda önerisi olan var mı? Birden fazla ağaç olacaktır, doğru. Şu ana kadar olan uygulamalarda bizim varsayımımız her n için bir ağaç olacağı şeklindeydi. Aslında ağaçların olasılık dağılımını elde ediyoruz. n’nin her değeri için, algoritmanın olası uygulamalarına bakacak olursanız ve komut izlerini takip ederseniz, her dallanma karşılaştırmasında ek olarak yazı tura atışlarında yazı mı tura mı geldiğine bağlı olarak, 1 ile n arasında rastgele sayıların oluşmasından meydana gelen bir durum ortaya çıkacak. Bu durumda da ağaçlarda bir olasılık dağılımı görülecek. Ama alt sınır koşulu yine de geçerli olacaktır.

Çünkü ne tip bir ağaç çıkarsa çıksın bu önemli değil. Ben her n değeri için en azından bir ağaç elde ediyorum. Ve bu kanıt her ağaç için geçerlidir. Bu nedenle ne tip bir ağaç oluşumu gerçekleşirse gerçekleşsin, eğer doğru bir ağaçsa bunun yüksekliği Ω(n logn) olacaktır. Bu alt sınır durumu rastgele algoritmalar için de geçerlidir. Yani n logn’den daha iyi bir sonuç elde edemezsiniz, çünkü ne tip bir ağaç yapısı oluşursa oluşsun, bu yazı tura durumları nasıl gelirse gelsin, bu argüman gene de geçerli olacaktır.

Oluşan her ağaç yapısı doğru olmak zorundadır . Bu nedenle bunun en azından bir ağaç şeklinde yazılması gerekir.. Ve şimdi bu artık işleyecektir. Bunun sonucunda rastgele çabuk sıralamanın da beklenene erişme konusunda asimptotik olarak en uygun olduğu gerçeği ile karşılaşacağız. Ama çabuk sıralamanın asimptotik olarak optimal olduğunu söyleyebilmemiz için rastgele algoritmaların Ω(n lgn) karşılaştırmasına ihtiyacı olduğunu bilmek durumundayız. Ama şimdi bunu biliyoruz ve her şey yolunda. Bu karşılaştırma modelidir. Devam etmeden önce soru var mı? İyi.

Gelecek konu karşılaştırmalı modelin dışına çıkıp, doğrusal zamanda sıralama üzerine olacak . Açık olan şu ki. eğer elinizde bir tür paralel algoritma veya daha karmaşık bir uygulama yoksa, doğrusal zamandan daha çabuk sıralayamamazsınız; çünkü en azından verilere bakmamız gerekir. Yani bu verilerle ne yapacak olursanız olun öncelikle onlara bakmak zorundasınız. Aksi takdirde bunları sıralayamazsınız.

Bu nedenle lineer yani doğrusal zaman bizim umut edebileceğimiz en iyi sonuçtur ve n lgn buna oldukça yakındır. Pekiyi, biz doğrusal zamanda nasıl sıralama yapabiliriz? Bunu yapabilmek için daha kuvvetli varsayımlara ihtiyaç duyarız – ve şimdi karşı bir örnek...

Karşılaştırmalı modelin dışına çıkıp elemanlarımızla başka bir şeyler yapacağız. Ve buradaki varsayımımız da bunların belli bir değer kümesinde olan tamsayılar olduğu ve bizim de bunu lineer zamanda sıralama yapmak için kullanacağımızdır. Biz burada n lg n’ den daha hızlı sıralama yapacak 2 algoritma üzerinde duracağız.

Birincisi oldukça kolay ve bunu 2. Algoritmada da kullanacağız. Bunun adı Counting Sort yani sayma sralaması. Sayma sıralamasındaki girişimiz alıştığımız gibi bir dizilim ama biz bu dizilimin elemanlarının neye benzediğini kafamızda şekillendireceğiz. Her A[ i ], 1’den k’ya kadar değişen bir tam sayı. Bu oldukça kuvvetli bir varsayım. Ve koşma süresi de aslında k’ya bağlı olarak değişecek. Eğer k küçükse, bu iyi bir algoritma olacak. Eğer k büyük bir değerse, o zaman bu kötü bir algoritma olacak; n lgn’ den daha da kötü olacak. Bizim amacımız bu dizilimin bir tür sıralanmış çıkış versiyonunu bulmak.

Buna A’nın sıralaması adını verelim. Burada çıkışı direkt olarak yazmak, bu algoritmanın permütasyonunu yazmaktan daha kolay olur.

Elimizde ek bir depolama alanımızın olduğunu düşünelim. Birazdan sözde kodu yazacağım için bütün değişkenlerimi burada tanımlıyorum. Ek depolamanın da uzunluğu k olacak ve girişlerimin değer kümesine eşit olacak. Şimdi algoritmaya bakalım.

Bu bir sayma sıralaması. Bunu yazmak biraz zaman alır ama oldukça kolaydır. Önce initialization yani ilklendirme yapacağız; yani ilk kuralları koyacağız. Sonra sayım işlemine geçeceğiz. Ondan sonra da biraz toplama yapacağız. Son olarak da çıktıyı yazacağız.

Bu algoritma herkes için yeterince açık mı? Kimse için değil mi? İyi. Bu aslında sözde kodun ne kadar belirsiz olduğunu gösteriyor. Ve siz de problem setlerinizi çözerken bir algoritmayı sadece sözde kodu verildiği zaman anlamanın oldukça zor bir şey olduğunu her zaman göz önünde bulundurun. Olan biteni anlamak için İngilizce açıklamaya ihtiyacınız olabilir, çünkü bu kodun ne olduğunu anlamaya çalışmak sizin yarım saatinizi belki bir saatinizi alabilir. Ve bu da kendinizi anlatmanın iyi bir yolu değildir. Şimdi yapacağım şey size bunun İngilizce açıklamasını yapmak, ama sonradan ne olduğunu anlamak için buna döneceğiz.

Bu bizim algoritmanın ne yapacağı konusundaki kutsal kitabımız gibidir. Bunun üzerinde kısaca açıklamalar yapayım. 1. Adım sadece bir ilklendirme adımıdır. Bu C[i]’ler bir şeyleri saymamıza yarıyor, yani değerlerin oluşumunu sayıyoruz. Bu nedenle bunlara önce sıfır değeri verelim. Sonra her gördüğümüz A[ j ] değeri için sayacımızı o A[ j ] değeri için yükselteceğim. Bu yolla C[ i ]’ lerim bana belirtilen i değerine eşit elemanların sayısını verecek.

Bundan sonra prefix yani öntakı toplamlarını alacağım ve böylece C[i] bana anahtarların sayısını, bir önceki adımdaki eşitlikler yerine, i’ye eşit yada daha küçük elemanların sayısını verecek. Ondan sonra da göreceğiz ki bu işlemler bütün elemanların doğru yerde olması için yeterli olacak. Buna ben distribution yada dağılım diyeceğim. Bu dağılım adımı. Ve aslında tüm adımlar arasında en az belirgin olan da bu adımdır. Şimdi bunu daha anlaşılır kılmak için bir örnek çözelim.

A dizilimini alalım. A= [4, 1, 3, 4, 3]. Bundan sonra bir C dizilimine ihtiyacım var. Buraya birkaç index yani dizin yada anahtar listesi ekleyim ki algoritmanın ne yaptığını görebilelim. Buradan görüleceği gibi bütün sayılarım 1 den 4 e kadar; böylece k= 4 diyebiliriz. C dizilimimin 4 değeri var. Başlangıçta bunların hepsini sıfır yapıyorum. Bu kolay. Şimdi her şeyi saymak istiyorum. Ve burada hile yapmayayım. İkinci adımdayım demek istiyorum. Ve sıralı her elemana bakıyorum. C[i] değerine bakıyorum. Birinci Eleman 4. O halde ben C4’e bakıyorum. Bunun değeri 0. Bunu 1’ e arttırıyorum. Sonra eleman 1’e bakıyorum. Bu da 0. Bunu da 1’e arttırıyorum. Ondan sonra 3 e bakıyorum ve o burada. Bunun da ilk değeri 0 ve bunu da 1’e arttırıyorum. Şu ana kadar heyecan verici hiç birşey yok. Şimdi 4’ ü görüyorum. İyi bunu daha önce görmüştüm, ne kadar heyecan verici. Burada buna 1 değerini vermiştim, şimdi bunu 2’ye arttırıyorum. Ondan sonra da 3’e bakıyorum. Bunun da değeri 1’di. Bunu da 2’ye yükseltiyorum. Bu şekilde sonuç [1, 0, 2, 2] oluyor. Algoritmanın çözümünün bu evresinde benim C dizilimim böyle görünüyor.

Şimdi elimdekilerle öntakı toplamlarını alarak basit bir dönüşüm yapıyorum. Bilmek istediğim şey bu bağımsız değerler yerine ön takıların toplamı. Bu öntakının toplamı, bu öntakının toplamı, bu öntakının toplamı ve bu öntakının toplamı.. C’nin değişik versiyonları arasında kaybolmamak için buna C’ diyeceğim. Bu sadece 1. 1 artı 0 = 1. 1 artı 2, 3 eder. 3 artı 2 de 5. Sonuçta bunlar koşan toplamlar gibi oluyor.

Toplamda 5 elemanımız var; bunların üçü 3’e eşit veya ondan küçük, biri 2’ye eşit veya ondan küçük, vesaire. Şimdi eğlenceli kısmı, yani dağılım yada distribution. Ve işte bu noktada B dizilimimizi elde ediyoruz. Aslında B aynı boyutta olmalı, burada olan her eleman B’nin içinde bir yerde olmalı ve sıralamalı düzende karşımıza çıkmalı. Şimdi algoritmayı çalıştıralım. j bu dizilimin sonundan başlayacak ve aşağıya doğru 1’e kadar, yani diziliminin başına kadar inecek.

Ve yaptığımız şey A’nın son elemanı olan A[n]’ yi seçmek. Sayaca bakacağız. O değer için C’nin vektörüne bakacağız. Burada 3 değeri var ve bu üçüncü sütunda 3 değeri var. Ve diyoruz ki B içinde bunun yeri bu olmalı. 3 sayısını alırsınız, B diziliminin üçüncü dizinine yerleştirirsiniz. Ondan sonra sayacı 1 azaltacaksınız. Buradaki 3 ün yerine 2 koyacağım. Buradaki düşünce aslında bu sayıların, bu değerlerin gideceği yeri size göstereceğidir. Değeri 1 olan herhangi bir şey birinci pozisyona gitmelidir. Değeri 3 olan herhangi bir şey üçüncü pozisyona veya altına gitmelidir. Burası 3 ün gidebileceği en son yerdir.

Böylece değeri 4 olan herhangi bir şey beşinci pozisyon yani son pozisyon yada onun altına girmek zorunda, çünkü bu dizilimin içinde 4 en yüksek değerdir. Ve bu sayaç da mükemmel olarak çalışacak çünkü bu sayımlar dizilimin her bölgesinde yeterli yer bıraktı. Pratikte bu kısım 1 ler için ayrılmış, 2’ler zaten yok, bu kısım 3’ler için ayrılmış, ve bu kısım da 4’ler için ayrılmış. Bu dizilimin anlamını kendiniz de kontrol edebilirsiniz. Şimdi algoritmayı yürütme işini bitirelim. Şu son elemandı. Bunu ben silmeyeceğim ama pratikte bunu zaten yaptık.

Şimdi ben son elemanın yanındakine bakacağım. Bu 4. 4’ler 5. pozisyona gidiyor. Böylece ben 4’ümü 5. pozisyona yerleştiriyorum ve sayacımı 1 azaltıyorum. Sonra başka bir 3 e bakıyorum. 3 ler 2. pozisyona gidiyor, Onun için bu şuraya gider. Şimdi sayacımı tekrar 1 azaltıyorum. Aslında daha fazla azaltmaya ihtiyaç yok ama algoritma böyle söylediği için bunu gene de yapalım.. Bir önceki elemana bakıyorum. Bunun değeri 1.

1’ler 1. pozisyona gidiyor, onun için onu buraya koyuyorum ve sayacımı bir daha azaltıyorum. Ve sonuçta başka bir 4 karşıma çıkıyor. Ve 4’ler şimdi 4. pozisyona gidiyor, 4. pozisyon burada ve sayacımı tekrar 1 azaltıyorum. İşte bu sayma sıralaması. Ve dikkat ederseniz bütün elemanlar var ve sıralanmış olarak görünüyorlar; işte algoritma bu. Şimdi sayma sıralamasının koşma süresi nedir? kn bir üst sınırdır. Bundan biraz daha iyi olması lazım. Aslında çok daha iyi olması lazım. Bunun için biraz toplama yapmaya ihtiyaç var. Algoritmanın en tepesine gidelim. Bu adım ne kadar zaman alır? k. Pekiyi, bu adım ne kadar zaman alır? n. Bu adım ne kadar zaman alır? k. Bu döngülerindeki işlemlerin her biri sabit bir zaman alıyor, onun için bu döngünün içinde kaç tekrar var? Ve sonuçta bu adım da n zamanını alıyor. Böylece sayma sıralamasının toplam koşma süresi k+n olur. Ve k küçük bir değerse, örneğin en fazla n ise, o zaman bu algoritma çok önemli bir algoritma haline gelir. Eğer k, n² yada gibi büyük değerlerdeyse o zaman bu iyi bir algoritma değildir. Ama eğer k = O( n) ise o zaman çok kullanışlı bir algoritmadır.

Ve biz bu durumda istediğimiz doğrusal zamanlı sıralama algoritmasını elde etmiş oluruz. Ama unutmayın ki buradaki varsayımımız sadece sayıların tam sayı olması değildi; algoritmanın verimli çalışması için aynı zamanda bu sayıların küçük bir aralıkta olması gerektiği durumu da vardı. Eğer sayıların hepsi 1 ile n arasındaysa o zaman biz doğrusal zamanlı algoritmayı elde edebiliriz. Ama bunların değeri n lgn’ye uzanıyorsa o zaman işimize yaramaz. O zaman n lgn sıralamasını yapmaya geri döneriz. Bu da çok kullanışlı bir durum değildir. Bu durumda k, n lg n’ den büyükse o zaman birleştirme sıralamasını kullanabilirsiniz. Eğer k, n lgn’den küçükse, o zaman da sayma sıralaması kullanabilirsiniz. Bu durumda bu çalışır, ama bundan da daha iyi bir sonuç elde edebiliriz.

Saat kaç oldu? Bu evrede not etmemiz gereken şey aslında sınırımızı aşıp karşılaştırmalı modelin dışında çalışıyor olduğumuz. Aslında orijinal teoreme aykırı bir şey yapmadık; sadece modeli değiştirdik. Ve herhangi bir problem senaryosunda izniniz olan durumları sorgulamak her zaman iyidir. Örneğin bazı pratik senaryolarda eğer kullandığınız sayılar bir bayt uzunluğundaysa o zaman bu model çok uygun olacaktır. Örneğin, k sadece yani 256 ise ihtiyacınız olan ek dizilimin boyutu 256 dır ve bu da çok hızlı çalışır. 256 + n, n ne kadar büyük olursa olsun n’ye doğrusal orantılıdır. Eğer sayılarınızın küçükse, bu iyi bir şeydir. Ama eğer sayılarımız daha büyükse, örneğin bunlar tam sayı ama 32 bitlik sözcüklere sığıyorlarsa, o zaman bu uygulamayla hayat o kadar kolay olmaz.

Çünkü k bu durumda nci kuvvetindedir. Bu da 4,2 milyar civarında bir sayı eder ve bu oldukça büyüktür. Bu durumda da sizin ihtiyacınız 4,2 milyar sözcük boyutunda bir ek dizilimdir. Ve bu da yaklaşık 16 GB yer tutar. Bu nedenle siz daha başlamadan önce dizilimi ilklendirmek zorunda kalırsınız. Yani n, 4 milyardan çok daha büyükse ve elinizde 16 GB’ lik bir kullanılmayan bellek kapasitesi varsa, ki ben aslında 16 GB önbelleği olan bir makine da bilmiyorum, o zaman bu algoritma kullanışlı bir algoritma olmaz. Yani sadece sayılar küçük olduğu zaman bu algoritmanın yararlı olacağını hissetmelisiniz.

Bir sonraki konumuzda daha karmaşık bir algoritmadan bahsedeceğiz; bu algoritmayı küçük sayıları işleyen bir alt yordam gibi kullanacak ve sonra bunları birleştirerek daha büyük sayılarla uygulama yapılmasını sağlayacak. Bu algoritmanın adı radix sort yani taban sıralaması. Ama bu konuya girmeden önce sayma sıralamasının önemli bir özelliğine ihtiyacımız var. Ve bu önemli özellik stabilite yani kararlılıktır. Kararlı bir sıralama algoritması eşit elemanların sıralarını muhafaza eder, göreli sıralarını diyelim.

Bu biraz hassas bir konudur, çünkü biz elemanları sadece sayılar olarak düşünürüz. Mesela elimizde birkaç tane 3, birkaç tane de 4 var. Aslında sonuçta baktığınızda bu 3’lerin ve 4’ lerin sırası hep yerlerinde kaldı. Çünkü sondaki 3’ü aldık ve buraya yerleştirdik. Sonra da sondaki 3’e komşu olanı aldık ve soluna koyduk. Ve sayacımız da dizilimin sonundan başına doğru hareket ediyordu. Bunu nasıl yaparsak yapalım 3’lerin sırası muhafaza edildi. Ve 4’ lerin de sıraları muhafaza edildi. Bu aslında kolay bir şey gibi görünüyor ama işlediğimiz diğer 4 sıralama algoritmasına baktığınız zaman bunların hepsinin kararlı olmadığını görürsünüz. Ve bu bir alıştırma olacak.

Egzersiniz yada alıştırmanız diğer hangi sıralama algoritmalarının kararlı olduğu ve hangilerinin kararlı olmadığını bulmaktır. Ben size bu konuda çalışmanızı öneriyorum. Çünkü böyle sorular size testlerde ve quizlerde gelecektir. Ama şu anda bilmemiz gereken tek şey sayma sıralamasının kararlı bir uygulama olduğudur. Ben bunu kanıtlamayacağım ama algoritmaya baktığınız zaman bu açıkça görülüyor zaten. Şimdi gelelim radix sort yada taban sıralamasına..

Taban sıralaması doğrusal zamanda çok daha büyük aralıktaki sayılar için kullanılabilir. Yine de bu sayıların büyüklükleri konusunda bir varsayım yapmak gereklidir ama bu oldukça gevşek bir varsayımdır. Şimdi gerilimi biraz daha arttırmak için size taban sıralamasıyla ilgili tarihi bilgi vereceğim. Bu tarihteki en eski sıralama algoritmalarından biridir. Aslında büyük ihtimalle en eski uygulanmış algoritmadır. 1890 yıllarında uygulandı. Herman Hollerith tarafından 1890 yıllarında uygulandı. Herman Hollerith’i duymuş olan var mı? Birkaç kişi. Çok fazla değil. Aslında oldukça önemli biriydi. Bir zamanlar MIT’de ders vermişti. O punch kartların yani delgili kartların eski versiyonlarını geliştirmişti. Yani delikli kart teknolojisini geliştirmişti. Bu benim zamanımdan epey önce, bu bakımdan hatırlamak için notlarıma bakıyorum. Evet, onlar da buna delikli kart derlermiş. Belki bunları görmüşsünüzdür.

Eğer bunları daha önce görmediyseniz power point ders notlarında görebilirsiniz. Şöyle bir büyük grid yada ızgara var. Bugünlerde eğer modern delikli kartları kullandıysanız bunlar 80 karakter genişliğinde ve tahmin ediyorum 16 boyunda, tam hatırlamıyorum. Sonra buralara küçük küçük delikler deliyorsunuz. Bir sihirli makine var, bir daktiloya benziyor. Siz bir harfe basıyorsunuz ve bu bir karaktere karşılık geliyor. Belki şuraya bir delik açacak veya oraya bir delik açacak. Eğer tarihe meraklıysanız ve bunun nasıl olduğunu merak ediyorsanız web sitesine bakabilirsiniz. Bunları bugünlerde çok görmüyorsunuz ama bu, günümüzde birçok terminalin neden 80 karakter genişliğinde olduğunu izah ediyor. Çünkü bunlar zamanında da öyleydi. Hollerith aslında bu delikli kartlarla başlamadı ama sonunda bunları geliştirdi.

Başlangıçta önemli olay 1890’daki ABD nüfus sayımı uygulamasıydı. Eğer haberleri izliyorsanız bundan 1 yada 2 sene önce Amerikan nüfus sayımının nasıl önemli bir şey olduğunu, çünkü herkesten verilerini toplamanın pahalı olduğunu duymuşsunuzdur. Ve anayasa da bu verileri herkesten her 10 yılda bir toplamak gerektiğini emrediyor. Ve bu giderek zorlaşıyordu. Ve 1880 de bir nüfus sayımı yaptılar. Ama nüfus sayımının değerlendirilmesi yaklaşık 10 sene sürdü. Nüfus artıyordu ve 10 senede bir yapılan nüfus sayımını, 10 senede değerlendirirseniz, bunlar birbirleriyle örtüşeceği için giderek daha da pahalı hale gelir.

Bu nedenle 1890 yılında daha kullanışlı bir şey yapmayı planladılar. Hollerith dedi ki, “ben size öyle bir makine yapacağım ki siz verileri bununla toplayacaksınız”. Bu biraz değiştirilmiş bir delikli karttı, ve bundaki belirli kareleri medeni durumunuza gore, evli yada bekar olmanız gibi durumlara göre işaretleyebiliyordunuz. Ve bu kartla nüfus sayımında bilinmesi istenen her şeyi ikili sistemde kodlayarak kaydedebiliyordunuz. Sonra da bu kartları sayma işlemini gerçekleştirecek bir sıralama makinesi yaptı.

Bazı açılardan bakılınca bunlar sayılardı. Ve bu sayılar çok büyük değillerdi. Fakat o kadar büyüklerdi ki sayma sıralaması çalışmayacaktı. Yani söylemek istediğim şey burada 100 tane sayı varsa, oldukça korkutucu bir değerdir ve burada sayma sıralamasını kullanamayız. İlk fikir yanlış bir fikirdi.

Bunlardan sayıymış gibi bahsedeceğim. Diyelim ki bu sütunların her biri bir sayı olsun. Böylece bunların arasındaki en önemli basamak burada olsun, en önemsiz basamak da şurada olsun. İlk fikir bu sıralamanın en önemli basamaktan başlayarak yapılmasıydı. Bu çok verimli bir algoritma olmadı, çünkü en önemli basamağı alarak sıralama yaparsanız, elinizde kart demetlerinin olduğu birtakım sepetler oluşur. Ve bu fiziksel bir araçtı. Bu elektronik olarak kontrol edilen bir bilgisayar değildi. Burada okuyucuya kartı takmak için bir insan gerekiyordu. Makine kartın birinci sütununda hangi deliklerin delinmiş olduğuna bakıyordu. Ondan sonra da fiziksel bir çekmece açıyordu ve biri de sayılan kartları o sepetin içine doğru itiyordu. Sistem yarı otomatikti. Yani söylemek istediğim bilgisayar yarı insan yarı makineydi ama buna kafanızı takmayın. Prosedür yada yöntem buydu. Siz sonuç olarak selelerin içine kartları sıralıyordunuz. Sonra bunları tekrar alıp sıralamayı bu sefer ikinci basamağa göre yeniden yapıyordunuz.

Kısa sürede bu depolama sepetlerinin sayısı giderek çok büyümeye başladı. Çok fazla basamağınız yoksa bu kabul edilebilir ama aslında yapılacak doğru şey değildir. Doğru fikir, bu uygulamadan sonra Hollerith’in aklına geldi ve sıralamayı en önemsiz basamaktan başlayarak yaptı. Ve siz de kararlı bir sıralama algoritması kullanıyorsanız bunu böyle yapmalısınız. Tahmin ediyorum Hollerith buna zamanında kararlı sıralama algoritması demedi ama biz bu terimi kullanacağız. Ve bu sayede Hollerith çok para ve iyi şeyler kazandı. 1911 yılında bir tablolama makinesi firması kurdu ve bu firma birkaç başka firmayla birleşerek 1924 de ismini duymuş olabileceğiniz IBM isimli bir firmaya dönüştü. Yani siz Hollerith’in adını duymuşsanız ya bu konuyla ilgili duymuşsunuzdur veya daha önce delikli kartlar kullanmışsınızdır.

Buradaki fikir basamak basamak bir sıralama yapmamızdır. Bunu en başında söylemem gerekirdi. Ve bu işi en az önemli olan basamaktan başlayarak en önemli olana doğru yapacağız. Göreceksiniz ki bu işlevsel olacak. Ve bunu yapmak için bir örnek üzerinde çalışalım. Bana öyle geliyor ki 2 tahtaya da ayrı ayrı ihtiyacım olacak. Önce bir örnek görelim, sonra da teoremi kanıtlayalım. Kanıtlama aslında çok kolay olacak. Ama bunu daha önce görmediyseniz aslında kolay hayal edebileceğiniz bir şey değil. Doğruyu söylemek gerekirse ben bunu ilk kez gördüğümde bu bana bayağı bir sürpriz olmuştu. Bu algoritmayla ilgili güzel yön de aslında bir sürü toplama sepeti olmaması. Her zaman bir büyük sepet var, o kadar. Haydi bazı rakamları seçelim. 329. Bu 3 basamaklı bir sayı. Ben basamakları biraz ayrı yazacağım ki onları daha iyi görelim.

457. 657. 839. 436. 720 ve 355. Burada ondalıklı sayıları kullandığımızı kabul ediyorum. Niye olmasın? Umut ederim ki bunlar şu anda sıralı değiller. Biz onları sıralamak istiyoruz. İlk yapmamız gereken şey en önemsiz basamağı alıp, sıralamaya en önemsiz basamaktan başlamak. Ve ne zaman eşit elemanlar görürsek, buradaki iki 9 gibi, bunların göreli sıralarını koruyacağız. Böylece 329 839 un üstünde kalacak. Burada çok fark etmeyecek, çünkü daha ilk sıralamamızı yapıyoruz. Ama genelde her zaman kararlı bir sıralama algoritması kullanıyoruz. Bu sütunda sıralama yaptığımız zaman önce 0 geliyor. Onun için bu 720. Ondan sonra 5 geliyor. Yani 355.

Sonra 6 var 436. Burada hata yaparsam lütfen beni uyarın. Bundan sonra 7’ler var ve sırayı koruyarak devam ediyoruz. Burada doğru sırada gibi görünüyorlar ama ilerde böyle olmayabilir. Daha sonraki basamaklara bakmadık. Ondan sonra 9’lara geliyoruz, burada iki tane 9 var, 329 ve 839. Buraya kadar tamam mı? İyi, şimdi ortadaki yani bir sonraki en az önemli basamaktan devam edeceğiz ve sıralamaya ikilerden başlayacağız. Burada bir tane 2 var ve şu aşağıda da bir adet 2 var. Tabii önce ilk 2’ yi yazacağız, 720 ve sonra da 329. Bundan sonra 3’lere bakacağız ve elimizde 436 ile 839 var.

Ondan sonra bir kaç tane 5 var gibi görünüyor. Şu ana kadar bir şey atladım mı? Hayır, iyi. Elimizde üç tane 5 var, 355, 457 ve 657. Bu evrede herhangi bir elemanı kaçırmış olup olmadığımı kontrol edeceğim. Burada 7 var, şurada 7 var ve şurada da 7 var. İyi, son olarak da en son basamakta sıralama yapacağız. Son basamakta sıralama yapmadan önce dikkat etmemiz gereken bir konu daha var. Şu an itibariyle bu sayılar sıralanmamış görünüyorlar ama, işleyeceğimiz basamak dışındakilerine, yani şu iki basamağa, bakarsanız bu bayağı güzel sıralanmış.. 20, 29, 36, 39, 55, 57, 57. Güzel değil mi? Haydi şimdi işi bitirelim. Birinci basamakta kararlı sıralama yapacağız. Ve burada gördüğümüz en küçük sayı 3, böylece önce 329’ u sonra da 355’ i elde ediyoruz.

Sonra bazı 4’ler var, 436 ve 457, sonra bir tane 6 var, 657, bir tane 7 ve bir tane de 8 var. Haydi kontrol edelim, hala elimde 7 tane eleman var. İyi, herhangi birini kaybetmedim ve gerçekten de şu anda sıralı bir düzendeler. Şimdi bunun niye böyle çalıştığını görebilirsiniz. Burada eşit elemanlar olduğunda suffix’i yani sontakıyı zaten sıralamış oluyor.

Haydi bunun kanıtını yazalım. Bu algoritmanın hoş yanı, bunları binlere yada sepetlere bölüntülemememiz. Tüm işlem boyunca bütün elemanları bir büyük yığın içerisinde tutuyoruz ama bunların üzerinden birkaç kez geçiyoruz. Genelde birkaç kez geçmemiz gerekiyor ve çok fazla geçiş olmamasını umuyoruz.

Ama önce doğruluğu konusunda bir tartışma açalım. Bunun koşma süresinin çözümlenmesi biraz karmaşık, çünkü bu sizin basamaklara nasıl böldüğünüze bağlı değişiyor. Doğruluk kolay. Sıralama işlemindeki basamak pozisyonundan başlarız; buna t diyelim. Ve tümevarım yaklaşımı ile bunun t basamağının ötesinde sıralandığını kabul edebiliriz. Bu bizim tümevarım hipotezimiz. Biz düşük düzeyli t-1 basamağında sıralanmış olduğumuzu kabul ederiz. Sonra yaptığımız şey, t basamağında sıralama yapmaktır. Bu evrede bunun işlevsel olduğunu kontrol etmemiz yeterli olur. Ve t - 1 için uyguladığımız tümevarım hipotezini bu kez t için yenileriz.

t basamağında sıralama başladığında iki şık oluşur. Herhangi iki elemana baktığımız zaman bilmek istediğimiz şey doğru sırada olup olmadıklarıdır. Eğer iki eleman da aynı t basamağında ise bu biraz karmaşık bir durumdur. Bu durumda sıralarının değişmemesi gerekir. Stability yani dengelilik prensibinden aynı sırada kalmaları gerekir, çünkü dengelilik prensibi sıralamada aynı anahtarı kullandığımız zaman elemanların yerlerini muhafaza etmelerini söyler. Ve tümavarım hipotezi bizden bunların sıralanmış düzende tutulmasını ister, çünkü tümevarım hipotezi bunların daha önceden sıralanmış olduğunu varsayar.

Aynı değeri her ikisinin de başına koymak herhangi bir değişikliğe sebep olmaz ve sıralanmış olarak kalırlar. Ve eğer değişik t basamakları varsa, bu sıralama adımı onları doğru sıraya sokacaktır. Çünkü sıralamanın işlevi budur. En önemli basamakta işlem yaptığınızda, birbirlerinden farklılarsa o zaman t basamağındaki değere göre sıralamanız gerekir. Geri kalan değerler önemsizdir. Böylece algoritmayı biliyorsanız, doğruluğunun kanıtlanması çok kolaydır. Devam etmeden önce sorular var mı? İyi, şimdi sayma sıralamasını kullanacağız.

Bağımsız basamaklardaki işlemler için herhangi bir sıralama algoritmasını kullanabiliriz ama koşma süresi n lgn’den daha iyi olduğunu bildiğimiz tek algoritmayı kullanalım ve daha hızlı ve daha genel bir algoritmaya ulaşıp ulaşamayacağımıza bakalım. Buradan koşma sürelerini şimdilik sildim. Sayma sıralaması k+n süresi düzeyinde çalışır. Bunu hatırlamamız gerekir. Ve buradaki sayıların değer kümesi 1’den k’ya veya 0’dan k-1’e kadardır. Herhangi bir basamakta sıralama yaparken n lgn algoritmasını kullanmamamız lazım, çünkü bu sistem bir tur için n lgn zaman alır ve birden fazla tur var. Bu durumda sonuç n lgn’den daha kötü olacaktır. Bu nedenle her basamak için sayma sıralamasını kullanacağız; ve biliyoruz ki sayma sıralamasının koşma süresi k+n’dir. Ama tam sayılarımın basamaklara ayrılmış olduğunu varsaymak istemiyorum. Bu sisteme çok fazla esneklik vermek demektir. Çünkü buraya yazılmış olan herhangi bir sayıyı, hangi formda yazılmış olursa olsun, belki de ikili sistemde yazılmış olacak, bazı bitleri gruplayıp bunlara bir basamak diyebilirim. Onun için sayılarımızı ikili bazda alalım ve elimizde n tamsayı olduğunu düşünelim. Bunların hepsi belirli bir değer kümesi içinde olsun. Ve bu değer kümesinin hangi büyüklükte olduğunu bilmek istiyoruz. Pratik açıdan da ikili dünyada yaşadığımızı düşünerek her tam sayının b bit uzunluğunda olduğunu varsayalım.

Bu durumda başka bir deyişle bizim değer kümemiz 0 ile 2b-1 arasında değişiyor. Sayılarımın negatif olmadığını varsayıyorum, ama negatif de olsalardı fazla bir şey fark etmeyecekti. Ben hangi büyüklükteki bir b ile işlem yapabileceğimi bilmek istiyorum, ama bitleri de benim basamaklarım olarak bölmek istemiyorum, çünkü o durumda elimde b basamak olurdu ve bu algoritmayı b tur yürütmem gerekirdi. Bu algoritmadaki turların sayısı elimdeki basamakların sayısı kadar olur. Ve umut ediyorum ki bunların her biri bana doğrusal bir zamana mal olacak. Ve eğer tek bit kullanırsam k, 2 olur ve bu n düzeyindedir. Ama bu durumda koşma süresi tur başına n düzeyindedir. Ve elimde b kadar basamak olduğuna göre, bunlar bit olarak ele alınırsa, o zaman düzey n kere b süresi olacaktır. Bu durumda b, lg n gibi küçük bir değer olsa bile, yani lg n değeri kadar bit’im olduğunu varsayalım, o zaman bu sayılar 0 ile n-1 arasında yer alacaktır.

Ben 0 ile n-1 arasındaki sayıları doğrusal zamanda sıralamayı zaten biliyorum. Burada n lgn kadar zaman sarf ediyorum ve bu çok iyi bir şey değil. Bunun yerine yapacağımız şey bir bit demetini almak ve buna bir basamak demek; bunu öyle yapmalıyız ki sayma sıralamasında kullanılabilecek en çok biti kullanalım. Bunun simgeleminde her tamsayıyı b/r basamağa bölüyorum. Herbiri r bit uzunluğunda. Diğer bir deyişle sayımın tabanlı olduğunu düşünüyorum. Ve bunları ikili sistemde yazıyorum ama r kadar biti kümeliyorum ve bu yolla tabanlı birtakım basamaklar elde ediyorum. Böylece elimde b/r basamak var. Bu b/r turların sayısı olacak. Ve bu taban, herhangi bir basamakta kullanabileceğim en yüksek değer. Bu 0 ile arasında. Bir bakıma sayma sıralamasının bir turundaki k’ ya benziyor. Bunun koşma süresi nedir? Elimde b/r tur var. O halde bu b/r kere bir turun koşma süresi. Elimde n kadar sayı var ve benim k değerim . Bu sayma sıralamasının koşma süresi yani n+k, bu da turların ya da tekrarların sayısı; böylece elimize b/r çarpı (n +) olur. Ve ben r’ye istediğim değeri atamakta serbestim. Yapmak istediğim şey bu koşma süresini r seçimlerimle asgari düzeye düşürmek.

r seçimi ile asgari koşma süresini bulmam konusunda önerileriniz var mı? Çözümler olmayabilir, teknikler de olabilir. Buna alışkın değiliz, çünkü bu asimptotik ama buradaki büyük O’yu unutun. Ben bu fonksiyonu tek değişkene göre nasıl en aza düşürebilirim? Evet, türevini alarak. Bu fonksiyonun r’ye göre türevini alırım, türevi 0’ a eşitlerim ve bu şekilde fonksiyonun kritik noktasını bulurum. Bunu yaptığım zaman şu ortaya çıkar ki bu fonksiyon r bağlamında unimodal yani tek dorukludur ve bu şekilde minimumunu ya da asgari değerini bulabilirsiniz. Bunu yapabiliriz., Ama burada bunu yapmayacağım çünkü biraz uğraşmak gerekiyor. Siz bunu evde denemelisiniz. Bu size minimum değeri verir ve bu sabiti biliyorsanız iyi sonuç elde edersiniz.

Fonksiyonun r’ye göre türevini alın ve bunu 0’ a eşitleyin. Ben bunu sezgisel olarak yapacağım, yani daha az titiz olacağım ama sonunda doğru yanıta ulaşacağım. Ve sonunda mutlaka bir üst sınıra ulaşacağım çünkü r’yi istediğim gibi seçebiliyorum. Sonunda da bu doğru cevaba dönüşecek. Şimdi büyümeyi r cinsinden düşünelim. Burada temelde iki terim var: Birisi b/r kere n ve diğeri b/r kere . Şimdi b/r kere n için, r’nin mümkün olduğu kadar büyük olması iyidir. r ne kadar büyük olursa tekrarlama turları o kadar azalacaktır. n’nin önündeki sayı yani n’nin katsayısı küçüleceğinden r’nin büyük olmasını istiyorum. Bu durumda b/r kere n, r’nin büyük olmasını ister. Ama r çok da büyük olmamalı çünkü bu basamakların içinde bir sürü bit olacak anlamına gelir. Çok büyük olmamalı çünkü burada bir de terimi var.

Eğer , n’den daha büyük olursa, o zaman terimi r’ye bağlı büyümeyi domine eder. Bu o zaman b kere bölü r haline gelir. r’den çok çok büyüktür ve bu durumda büyüme daha büyük bir süratle olur. Ama bu terim nedeniyle ben r’ nin çok da büyük olmasını istemiyorum. Bu durumda b/r çarpı , r’yi küçük ister. n teriminin teriminden büyük veya ona eşit olması halinde, ben r’yi bu terim için oldukca büyük seçebilirim. Yani istediğim şey, n’nin ’yi domine etmesi. Bu koşulu sağlamam halinde r’yi istediğim kadar büyük seçebilirim. Diyelim ki r’yi maksimum seçmek istiyorum ama öteki yandan n’nin ‘ye büyük-eşit olması koşulu karşılanıyor.

Bu için bir üst sınırdır ve aynı zamanda r için üst sınırdır. Diğer bir yaklaşımla ben r = lgn olmasını istiyorum. Bu belli sabitlere kadar doğru cevap olarak ortaya çıkar. İşte böyle. Ve ben r’yi lgn’e eşit seçersem, bu bana koşma süresinin üst sınırı için kesin bir değer verir, çünkü r’ yi istediğim gibi seçebiliyorum. Siz de bir türev işlemi yaparsanız aynı cevabı bulursunuz.

Bu çok formal bir yaklaşım değildi ama yakındı; çünkü büyük O neyin en hızlı büyüdüğüyle ilgilidir. Eğer buraya r = lgn’yi uygularsak bn/lgn elde ederiz. Ve n ile birbirine eşittir bu ikili bir faktördür, iki kere n’ dir, yani çok büyük bir değer farkı yaratmaz.

Bu sonuç aslında büyük O’ nun içinde değerlendirilir; elimizde bn/lgn var ve bu da r’ye eşit. Bunun ne anlama geldiğini düşünmeliyiz ve bunu değer kümesi açısından tercüme etmeliyiz. b bizim sayımızın içindeki bitlerin miktarıydı ve bu da sayının değer kümesine tanımlıyordu.

Geçen derste yirmi dakika az konuşmuştum, onun için bu dersi yirmi dakika uzatabilirim, değil mi? Hayır, hayır şaka yapıyorum, nerdeyse bitiriyorum. Diyelim ki sayılarımız tamsayılar ve değer kümemiz de 0’dan -1’e kadar olan bir değer kümesi. Burada değer kümemizi 0’dan ’ye kadar diye tanımlayacağım. Buralardaki değerlerin de -1 olması gerekiyor,

Elimde 0’dan -1’e kadar sıralanan sayılar varsa, burada d bir sabit veya bir parametre ise, bu n cinsinden bir polinomdur ve bunun koşma süresini hesaplayabilirsiniz. Bunun düzeyi dn’ dir. Bunu bu şekilde düşünmelisiniz çünkü şimdi bunu sayma sıralaması ile karşılaştırabiliriz. Sayma sıralaması 0’dan d çarpı bir sabite kadar doğrusal zamanda hesaplayabilir. Şimdi ben 0’ dan n’nin bir sabit kuvvetine kadar olan değerleri doğrusal zamanda hesaplayabilirim. Eğer d’nin değeri birinci düzeydeyse biz doğrusal sıralama algoritması elde ederiz. Ve d en fazla lgn olursa, çok da iyi olur. Eğer sayılarınız en çok lg n ise, elimizde bizim n lgn sıralama algoritmamızdan daha hızlı çalışan bir şey var demektir. Ve bu oldukça hoş bir şey.

Sayılarımızın uzunluğu log n bit düzeyindeyse mutlu oluruz çünkü burada düzgün bir tradeoff yani ödülleşim elde ederiz. Örneğin elimizde 32 bitlik sayılar varsa ve biz bunları 8 bitlik dilimler haline bölüyorsak, bu durumda sadece 4 tur atarız, bunların her biri doğrusal zamanda gerçekleşir ve sadece 256’ lık bir çalışma alanına ihtiyacımız olur. 32 bitlik sayılar için 4 tur tekrar yapıyorduk; Eğer bir n lgn algoritmasını kullanırsanız, bu durumda lgn kadar tur tekrarı yapmanız gerekir.

Örnek olarak n eğer 2000 ise bu en azından 11 tekrar turu demektir. Küçük sayılar için bu algoritmanın çok daha hızlı olacağını düşünebilirsiniz. Maalesef sayma sıralaması bir cash yada önbellek üzerinde o kadar hızlı çalışmaz. Pratikte radix sort yani taban sıralaması, sayılarınız gerçekten küçük değilse çok hızlı bir algoritma değildir. Çabuk sıralamaya benzer bir uygulama daha iyi bir sonuç verebilir. Bu aslında teorik olarak güzeldi ama pratikte aynı sonucu vermemesi oldukça üzücü. Öte taraftan bazı uygulamaların sıralanmasında bu doğru yol olabilir.

Son olarak da bir word uzunluğunda rastgele tamsayılarınız olma durumundan bahsetmek istiyorum. Burada her sözcüğün içinde b kadar bit olduğunu varsayıyoruz ve b’ ye bağlı indirek birtakım etkilerin olduğunu düşünüyoruz. Fakat genelde eğer elinizdeki tamsayıların hepsinin uzunluğu bir sözcük kadarsa ve siz o sözcüğü sabit zamanda işleyebiliyorsanız, bu durumda sıralama amaçlı bilinen en verimli algoritma n kere süresinde beklenen zamanı verir.

Bu rastgele bir algoritmadır. Ve bu algoritmayı bu derste işlemeyeceğiz. Oldukça karmaşıktır. Bu algoritmayı ileri algoritma dersini verirken bile öğretmemiştim. Eğer daha kolay bir şey istiyorsanız aslında n çarpı lglg n düzeyinde bir en kötü süre bulabilirsiniz. Ve bu makale okunabilir durumdadır. Bunu ileri algoritma dersinde vermiştim. Bu tip şeylere merakınız varsa o zaman gelecekte ileri algoritma dersini alın. O ders bu dersin bir devamıdır; derste çok daha karmaşık algoritmalar işlenir. Ama bunlar sizin sezginizi geliştirebilir.

Sonuçta siz b’nin en çok bir sözcük uzunluğunda olduğunu bilirseniz, b’ye bağlı olma koşulunu bile kırabilirsiniz. Ben burada durmak istiyorum. Ama sorularınız varsa sorabilirsiniz.

Gelecek derste görüşmek üzere.