BASIC PROGRAMLAR
Retro bilgisayarreceler bir tablo halinde gelecek. BASIC PROGRAMLAR
Karakter veya sayısal verilerin genellikle sıralanması gerekir. Sıralama işlemini gerçekleştirecek çeşitli yöntemler var. Bunlardan bir tanesi de BUBBLE SORT. İlk olarak bu sıralama yönteminin hangi mantıkla çalıştığına bakalım. Birbirini izleyen iki eleman birbiriyle karşılaştırılır. Karşılaştırılan çift sırasızsa dizideki yerleri değiştirilir. Dizideki karşılaştırma sona erdiğinde eğer elemanlar arasında yer değiştirme yapılmışsa işleme yeniden başlanır. Eğer hiçbir değiştirme yapılmamışsa dizi sıralanmış demektir. Şimdi anlattığımız yönteme bir örnek verelim. Bu yöntemi kullanarak aşağıdaki kelimeleri sıralayalım: Ani ağır evlat diş menü tır düş hür Karşılaştırmaya dizinin her iki yönünden de başlayabiliriz. Örneğimizde karşılaştırmayı soldan sağa doğru yapacağız. İlk olarak Ani ve ağır kelimelerini karşılaştırıyoruz. İki kelimenin sıralanışı doğru. Hiçbir değişiklik yapmadan ağır ve evlat kelimelerinin karşılaştırmasına geçiyoruz. Bu iki kelimede sıralı olduğundan değişiklik yapmıyoruz. Ancak diş ve evlat kelimeleri sırasız vaziyette olduklarından dizide bu iki kelimenin yerlerini değiştiriyoruz. Sıra evlat ve menü kelimelerine geliyor. (Bir evvelki karşılaştırmada evlat kelimesi yer değiştirmişti). Bu iki kelimede sıralı vaziyette. İlk turun sonunda dizimiz aşağıdaki hale geliyor: Ani ağır diş evlat menü düş hür tır İlk turun sonunda tır kelimesi en üste çıktı. Bir sonraki turda menü kelimesi sıralamada gelmesi gereken yere gelecek. Şimdi bu sıralama yönteminin dezavantajlarını inceleyelim. En basit sıralama metodları N üstü metodları olarak sınıflandırılır. Buna bir örnek verelim: Eğer dizimizde 10 eleman varsa 9 * 9 = 81 karşılaştırma yapmak zorunda kalırız. Ancak eleman sayımız 1000 taneyse 999 * 999 = 998001 karşılaştırma yapmamız gerekir. Bu sayıda karşılaştırma çok uzun zaman alacağından bu tür yöntem işimizi olumsuz yönde etkiler. Bu sorunu halletmek için HEAPSORT gibi başka sıralama yöntemleri geliştirilmiş. Bu yöntemlerde artan eleman sayısına karşın karşılaştırma sayısı daha az artıyor. Karşılaştırma sayısını bize N LOG N formülü veriyor. Mesela 10 elemanımız varsa sadece 10 karşılaştırma yapmamız gerekiyor. Bubble sort yönteminin bir başka dezavantajı da verileri fazlaca hareket ettirmesidir. Karşılaştırılan çiftler sıralı değilse yer değiştiriliyor. Yer değiştirme işlemi hem zaman kaybına, hem de Garbage Collection adını verdiğimiz, bilgisayarın uzun süre beklemesine sebep olan soruna yol açıyor. Ancak bu sorunu indeksleme yöntemi ile gidereceğiz. İndeksleme yöntemini kısaca açıklayalım. Dizideki elemanların yerlerini değiştirmek yerine bu elemanların yerini gösteren indekslerin yerlerini değiştireceğiz. Eğer verilerimiz gruplar halinde düzenlenmişse, mesela tarih, hesap numarası ve tutar şeklinde veri alanlarımız varsa, bu veri alanlarını gösteren indeksin yerini değiştirmek daha kolay olacaktır.
Şimdiye kadar bubble sort yönteminin dezavantajlarından bahsettik. Ancak bu yöntem bazı yönlerden çok kullanışlı. Eğer sıralamanın yapılacağı dizideki elemanlar hemen hemen sıralı durumdaysa sıralama işlemi çok çabuk biter.
En önemli avantajlardan birisi sıralama devam ederken ilk sıralanmış elemanları kullanıcıya verebilmektir. Birçok sıralama yönteminde sıralama bitene kadar kullanıcı beklemek zorundadır. Ancak bubble sort yönteminde sıralama işleminin başlaması ile birlikte derhal sonuç almaya başlarız.
Şimdi örneğimizdeki kelimeleri kullanarak bubble sort'un nasıl çalıştığını inceleyelim ANİ AĞIR EVLAT DİŞ MENÜ TIR DÜŞ HÜR Sıralamaya başlamadan evvel dizinin en altında ANİ kelimesi en üstünde HÜR kelimesi yer alıyor. Sıralama işleminde karşılaştırmayı üstten alta veya alttan üste doğru yapabiliriz. Ancak üstten alta karşılaştırma yapmak her seferinde en azından bir elemanı sonuç olarak ortaya çıkaracağından tercih edilebilir. Karşılaştırılan elemanlar arasında değişiklik yapıldığında yukarı çıkan elemanları işaretleyeceğiz. (Örneğimizde HÜR kelimesi hariç diğer kelimeleri büyük harfle yazarak işaretledik). Bir sonraki turda sadece yukarı doğru çıkan (işaretlenmiş kelimeler) elemanları karşılaştırmak yeterli olacak. Sıralama işlemine ilk başladığımızda en üstte bulunan HÜR kelimesi hariç tüm elemanları işaretliyoruz. Yukarıdan aşağıya doğru ilk olarak DÜŞ ve HÜR elemanlarını karşılaştırıyoruz. Bu iki eleman sıralı olduğundan bir sonraki karşılaştırmaya geçiyoruz. TIR ve DÜŞ elemanları sırasız olduğundan yerleri değişiyor. TIR kelimesi yukarı çıktığından bu kelimeyi işaretliyoruz (büyük harfle gösteriliyor). İlk turun sonunda dizinin durumu: AĞIR DİŞ EVLAT DÜŞ MENÜ TIR HÜR. EVLAT, MENÜ ve TIR kelimeleri yukarı doğru çıktıklarından işaretlendiler. Bir sonraki turda sadece bu üç kelime yukarıdaki kelimelerle karşılaştırılacaklar. EVLAT kelimesini de bir sonraki tur için en alt nokta olarak işaretleyebiliriz. Bu noktadan daha aşağı karşılaştırma yapmaya gerek yok. ANİ, AĞIR ve DİŞ kelimelerini kullanıcıya sonuç olarak verebiliriz çünkü dizi buraya kadar sıralandı. İkinci tura başladığımızda ilk olarak TIR ve HÜR kelimelerinin yerlerini değiştiriyoruz. MENÜ ve HÜR kelimeleri de yer değiştiriyor. DÜŞ kelimesi işaretlenmediğinden HÜR kelimesiyle karşılaştırılmıyor. EVLAT ve DÜŞ kelimeleri sırasız olduklarından yer değiştiriyorlar. İkinci turun sonunda dizimiz aşağıdaki hale geliyor: ANİ AĞIR DİŞ DÜŞ EVLAT HÜR MENÜ TIR. Bu noktada dizimiz sıralandı ancak biz bunu üçüncü turda anlıyoruz. Program döküm ekindeki program normal bubble sort programının geliştirilmişidir. Buna rağmen sıralama N log N kuralına göre çalışıyor. Ancak yeni eklemelerle bu yöntemin eskisine göre çok hızlandığını söyleyebiliriz
Şimdi programı biraz açıklayalım: İlk olarak dizideki eleman sayısı soruluyor. Daha sonra dizideki elemanları giriyoruz. Girilen veriler N$ adlı diziye yerleştiriliyor. Verileri kullanıcıdan almak yerine bir dosyadan da okuyabilirsiniz. 180 numaralı satırda sıralama işlemine başlıyoruz. J değişkeninde şimdiye kadar sıralaması bitmiş ve sonuç olarak kullanıcıya iletilmiş eleman sayısı saklanıyor. Bu değişkenin ilk değeri sıfır. 190-220 satırları arasında indeks dizisi hazırlanıyor. Sıralamaya başlamadan evvel indeks dizisindeki elemanların değeri çok basit: ilk eleman 1, ikinci eleman 2, üçüncü eleman 3.
İndeks dizisinde herhangi bir verinin bir üstteki veriyle kontrol edilip edilmemesi gerektiğini de saklıyoruz. Eğer indeks dizisindeki değer eksi işaretliyse, işaret ettiği elemanın bir üstteki elemanla karşılaştırılması gerekir. İlk turda tüm elemanların karşılaştırılmasını istediğimizden son eleman hariç diğerlerine eksi işaret veriyoruz. J8 değişkeninde dizide karşılaştırmanın yapılacağı en alt noktayı saklıyoruz. İlk turda tüm dizide karşılaştırma yapacağımızdan bu değişkenin ilk değeri birdir. 250-330 arasındaki satırlarda dizideki taramayı yapıyoruz. İki elemanın karşılaştırılması için X2 değişkeninin negatif olması gerekiyor. Eğer X2 değişkeni pozitifse karşılaştırma yapmadan 330 numaralı satırdaki NEXT komutuna atlıyoruz. Eğer J2 ve J3 değişkenlerinin işaret ettiği elemanlar sırasızsa bunlara karşılık gelen indekslerin yerini değiştirip yukarı çıkanı eksi olarak işaretliyoruz. Bir sonraki tura başlamadan evvel 360 numaralı satırda sıralanmış elemanı ekrana yazıyoruz. Bu kısa programı sıralama gerektiren programlarınızda kullanarak zamandan kazanabilirsiniz. Şimdilik hoşçakalın.