Bu sayfadaki yazılar
Sayfanın metni
Sayfa 15
Kabarcık Sıralama
Kabarcık sistemi, sıralama metodlarının en çok bilinenidir. Ancak bu programı bile yanlış hazırlayıp süreyi uzatmak mümkündür. Bu sistem nasıl çalışır? Kabarcık sıralama en çok bilinen sistem olmasının yanında en kolay algoritmaya da sahiptir. Program adımları şöyle özetlenebilir: 1. Data grubu içinden en yüksek olanı bul.
2. En büyük elemanı ilk elemanla değiştir. 3. Elemanlar istenen sıraya girene kadar 1. ve 2. adımları tekrarla. Programlar genel olarak biri diğerinin içinde yer alan iki FOR-NEXT döngüsünden oluşur. Dış döngü birden başlar ve sıralanacak data sayısından bir düşüğe kadar gider. İç döngü ise, dış döngünün değerinin bir fazlasından başlar ve toplam değer sayısına kadar gider. Böylece küçük değerler yavaş yavaş data grubunun başına doğru giderler. Değerler su “kabarcıkları” gibi yükselir. Kabarcık sıralama basit ve kolay uygulanabilir olmasına rağmen büyük data grupları için çok yavaş kalır. Bunun sebebi de tüm grup içinden geçiş yapılması gerektiğidir. Bunu bir formül yardımıyla da anlayabiliriz. Program şu formda bir karar komutuna sahiptir:
IF — THEN ...
Bu komutun kaç defa işletileceği şu formülle anlaşılabilir: (n-1)+(n-2)+...+2+1 = n(n-1) / 2 = k (karşılaştırma) Başka bir deyişle bu komutun işlenme sayısı sıralanacak grup elemanlarının (n) karesine bağlı olarak artar. Ancak bir süre sonra bu komuta ihtiyacımızın kalmadığını göreceksiniz. Basit bir kabarcık sıralama programı şöyledir:
30000 REM 30010 REM ***KABARCIK SIRALAMA RUTİNİ*** 30020 REM 30030 FOR I-İ TO N-İ 30040 ::FOR J-İ41 TON 30050 ::::1F — X(J) THEN 30090 30060 ::::B — X() 30070 ::::X(D) — 30080 ::::X()) — B 30090 ::NEXT J 30100 NEXT I 30110 RETURN
Daha önce bahsettiğimiz satırı değiştirecek kabarcık sıralamayı biraz geliştirelim. Böylece değiştirdiğimiz program şu hale gelir:
30000 REM 30003 REM ***GELİŞTİRİLMİŞ KABARCIK SIRALAMA RUTİNİ*** 30006 REM
30010 FORI-1 30020 ::B - | 30030 ::FOR J-İ41 TON
30040 — X(J) THEN 30060 30050 ::::B — : J 30060 J 30070 ::X(K) — 30080 ::X() - B 30090 NEXT I
30100 RETURN
Bu rutin de ilk örnekteki “değiştirerek sıralama” sistemine dayanır. 30040. satırdaki karşılaştırma komutu değiştirilerek sıralamanın yönü de (artan veya azalan) ayarlanabilir. İyi de niye ikinci program daha hızlı? Bu cevabı, ikinci versiyonda dış döngüde sadece bir X değiştirilmesi yapılmasıdır. Rutin bu değerin daha önce değiştirilip değiştirilmediğini kontrol eder, bunun için de geçici B değişkeni kullanılmaktadır. Böylece toplam işlem
Klavyeyle gezinmek için ← ve → tuşları.
Sayfa 14
Sinan Vural Commodore 64 piyasaya ilk çıktığı günden beri kendi alanındaki rakipleri arasında hep yükselmiştir. Her alanda kullanılabilecek kadar esnek olan bu müthiş alet şimdiye kadar ülkemizde eğitim alanında çok sınırlı olarak kullanılmış, ancak bazı ortaokul ve liselerimizde bilgisayar dilleri öğretilmiştir. Birçok bilgisayar sahibi öğrenci Commodore 64'leri ile oyun oynamaktadır. Program yapıp kendini geliştirmeye çalışanların ise ancak küçük bir kısmı kendi dersleriyle ilgili programları yazabilmektedir. Bu yazı boyunca sizlere genel matematik ve bilimsel hesaplamalar konusunda programlar ve algoritmalar anlatacağız, rutinlerden örnekler vereceğiz. Bu kadar geniş bir konuyu işlerken elbette atladığımız birçok detay olacaktır ama bu konuların her biri hakkında birer kitap yazılabilir. Bu yazı dizisinde bilgisayarların, özellikle Commodore 64'ün matematik ve bilimsel hesaplamalar alanında nasıl kullanılabileceğini göstereceğiz. Yazı dizimiz boyunca verdiğimiz programlar BASIC ile hazırlanmış olacak. Programları direkt olarak yazıp kullanmak için hiçbir ön bilgiye sahip olmanız gerekmiyor, ama eğer bilgisayar konusunda biraz deneyimliyseniz kendi amaçlarınız doğrultusunda programları değiştirebilirsiniz. Vereceğimiz programlar kısa rutinler halinde yazılmış olacak ve başka bir program tarafından hemen çağrılabilecek durumda olacaklar. Ayrıca bir konu sonunda o konuyla ilgili rutinler birleştirilmiş olarak ve karşılaştırmalı bir halde yazılacak.
Sıralama Sistemleri ve Programları
Doğal bilimlerle uğraşırken ölçülmüş dataların sıralanması gerekir. Sıralama programları da bu iş için kullanılırlar.
Bu programların birçoğu da altprogram (subroutine) olarak kullanılır. Sıralama sistemlerinden özellikle bazıları çok yaygındır. Burada inceleyeceğimiz sistemler yaygın olarak kullanılanlardan bazılarıdır. Sıralama algoritmalarının sistemleri ve sistemler kullanılarak hazırlanmış olan programların isimleri aşağıda sıralanmıştır. Bu sıralama programların verimlilikleri hakkında da genel bir fikir edinmenizi sağlayabilir: 1. Araya sıkıştırmalı sıralama (insertion). Örnek: doğrusal (linear) sıralama ve dalgacık (ripple) sıralama. 2. Değiştirmeli sıralama (exchange). Örnek: kabarcık (bubble) sıralama. 3. Seçimli sıralama (selection). Örnek: Shell sıralama. 4. Karışık ve özel yöntemler. Örnek: hızlı (quick) sıralama. Datalarımızın sayısal olduğunu varsayacağız. Yani sıralanacak olan bilgiler sayılardan oluşacak ve bir dizi içinde saklanacak. Bu bölümde anlatılanlardan daha verimli sıralama programları mutlaka vardır, ancak bunlar daha kısıtlı alanlarda kullanılabilirler veya çok daha karmaşıktırlar. Bunların dışında, sadece floppy diskler gibi dış kayıt ortamlarında sıralama yapmak için hazırlanmış algoritmalar da vardır. En çok bilinen sıralama algoritmaları doğrusal, kabarcık, hızlı ve Shell-Metzner sıralamalarıdır. Bu metodları anlatmaya çalışacağız, çünkü bu sistemler en yaygın olarak kullanılan algoritmalara dayanırlar. Bu konudan bahsederken, bir yandan da metodların hızlarının karşılaştırmasını yapacağız. Ancak programlara getireceğimiz bazı sınırlamalar olacak, örneğin recursive, yani kendi kendini çağıran algoritmalar kullanmayacağız. Belirtmemiz gerekir ki, özellikle Pascal gibi diğer programlama dillerinde bu sistemler dilin yapısında vardır. Sıralama rutinlerini, kendi programlarınızda istediğiniz gibi kullanabilirsiniz. Örneğin bir grafik çizmek için verilmiş olan bir grup datanın sıralanması gerekebilir. Temel bazı değişkenleri tanımladıktan sonra bu rutinleri çağırarak kendi işleriniz için kullanabilirsiniz. Sıralama algoritmalarını daha da iyileştirebilirsiniz. Programların hızlı çalışmasının zararı değil yararı vardır. Şimdi ilk örneğimize bakalım: kabarcık sıralama.