Sıra Sıra Sıralamalar

• Programlama teknikleri

Diyelim ki ayrı insanlara sık sık mektup, broşür vb. göndermek durumundasınız. Bu yüzden adres defterinizi bilgisayara girmek istiyorsunuz. Ya da bir araştırmacısınız; bir kaynakça hazırlamak istiyorsunuz, ya da bilgisayarınızda yabancı dil öğrenirken başvuracağınız bir sözlük yaratmak istiyorsunuz. Ne yapacaksınız? Bilgilerin rastgele bir sıra içerisinde makineye girilmesi sorun değil. Ancak rastgele girilmiş bilgilere düzenli bir biçimde erişilmesi gerekir. Bunu nasıl mı sağlayacaksınız? Buyurun size Sıra Sıra Sıralamalar.

Sıralamanın sıkça başvurulan bir bilgi işlem uygulaması olduğunu biliyoruz. Bir dosyanın aramalara yanıt verebilmesi ya da en azından eli yüzü düzgün basılı örnekler (print-out) elde edebilmesi için, fiziksel durumundan (bilginin sıra gözetilmeksizin girilmesi gibi) kurtarılarak mantıksal bir düzene sokulması, yani sıralanması gerekmektedir. En sık başvurulan sıralama yöntemlerinin alfabetik yöntemler olduklarını görüyoruz. Peki karşımıza çıkacak özel bir durumda hangi sıralamayı kullanacağımıza nasıl karar vereceğiz? Aşağıdaki satırlarda birkaç harfsayısal (alfanumerik) sıralama yönteminin kısa çözümlemelerini vererek bu konuda size yardımcı olmayı umuyoruz.

Kabarcık Sıralama

Basit ve kolay uygulanabilir olması nedeniyle bildiğimiz sıralama yöntemleri arasında belki de en yaygın olanı budur. Adından da anlaşılabileceği gibi, veri ögeleri (data items), amaçlanan dizeydeki (array) doğru hanelere, komşu ögelerle kıyaslamalar yapılarak dipten su yüzeyine yükselen hava kabarcıkları gibi gönderilirler. Her bir veri ögesi doğru haneye gönderilmiş ve yerleştirilmiş olana dek, başka bir deyişle dizi bütünüyle sıralanmış olana dek sonlu bir sayıda taranır. Çizim-1'de gösterilen diziyi incelerseniz anlatmak istediğimizi daha iyi kavrayabileceğinizi sanıyoruz. Göründüğü üzere bir program örneğini içermektedir. Matematikçi okurlarımız için burada küçük bir noktayı belirtmekte yarar var. Program örneğimiz n-1 kez kıyaslamaları yapmaktadır; ancak biz bu noktayı diğer sıralama yöntemlerine göz atarken hesaba katacağız. Kabarcık sıralama, bilinen en basit sıralama yöntemi olmasının yanı sıra aynı zamanda en yavaşlarından biridir. Bununla birlikte kabarcık sıralamanın en belirgin üstünlüklerinden biri hali hazırda sıralanmış bir dosyaya tek bir kaydın yazılacağı durumlarda en etkin sonucu vermesidir. Yeni kayıt kütüğün sonundan gönderilir ve sıralamada doğru yere gelene kadar bir hava kabarcığı gibi yükselir (yani yeni kaydın hemen üstündeki ögeyle yer değiştirmesi diye bir durum söz konusu değildir.)

Dalgacık Sıralama

İlke olarak kabarcık sıralamadan farklı değildir. Ancak bu yöntemde ögeler, yükselen hava kabarcıkları gibi dizey ya da dosya boyunca aşağıdan yukarıya değil de, dalgacıklar halinde yukarıdan aşağıya gönderilirler.

Ne ki bu programla biz MARKER adını verdiğimiz bir çentik (flag) takdim ediyoruz. MARKER'in görevi dizinin herhangi bir taranmasında bir yer değişimi gerçekleşmesi halinde bunu haber vermek olacak. Hiçbir değiş tokuşun yapılmadığı durumda MARKER “çentiği atılmayacak”, yani değişken ilk değerini koruyacak, bu da dizinin sıralanmış olduğu anlamına gelecektir. Dolayısıyla program yürütümünden (execution) erken bir çıkış yapılabilecek, böylece işleme süresi (run time) de kısaltılmış olacaktır. Özgün örneğimize dönersek

Dalgacık Sıralamanın nasıl çalıştığını görebilir ve önerdiğimiz çentiğin yöntemi anlamak açısından kullanışlılığına tanık olabiliriz. Çizim-2) Elimizdeki örnekte program yürütümünden erken çıkış fazla bir fark yaratmamakla birlikte (ancak tek bir kıyaslamadan kurtulunabiliyor) daha geniş kapsamlı dosyalarda çalışırken sıralama için gereken zamandan hatırı sayılır ölçüde ekonomi yapılabilmektedir. Özellikle de ele aldığımız dosya sadece kısmi bir sıralamadan geçecekse (yalnızca tek bir kayıt doğru hanede değilse); n-1 kıyaslamalarının maksimumu düşer ve sıralama zamanı son derece kısalır. Ancak kıyaslamaların tümünün de yapıldığı durumlarda bu sıralama yöntemi en azından bir bölümüyle Kabarcık sıralamadan daha yavaş çalışmaktadır. Bunun nedeni de içiçe döngülerde (nested loops) MARKER'in görevlendirilmesi ve test edilmesi için gereken fazla zamandır.

Ayıklamalı Sıralama

Ayıklamalı sıralamanın yukarıda sözünü ettiğimiz diğer iki yöntemden biraz daha üstün olduğunu söyleyebiliriz. Bu yöntemde de üstünde çalışılan dizinin belli sayıda taramaları

(pass) yapılmakta ve sıralama ilerledikçe taramalar giderek kısalmaktadır. Ancak bu kez eldeki öge onun hemen üstündekiyle kıyaslanmak yerine o özel (particular) taramada en üstte

bulunan öge ile kıyaslanmakta ve eğer gerekiyorsa söz konusu ögenin yeri değiştirilmektedir. Bu işleme biçiminin tam da “Ayıklamalı Sıralama” deyişine uygun düştüğünü söyleyebiliriz;

SOLDAKİNİ |...

zira dikkat edildiğinde her taramada listenin en üstünde bulunan ögenin bütün listenin içinden (buna en üstteki de dahil) seçilip alındığı görülebilir. Çizim-3'te gösterilen minyatür dizinin incelenmesi halinde bu söylediğimiz daha iyi anlaşılabilir. Sonuç olarak Ayıklamalı Sıralamada da Kabarcık sıralama ile aynı sayıda kıyaslama yapılması gerekmekte ancak gerçekleştirilen yer değiş tokuşu daha az sayıda kalmaktadır. Bu nedenledir ki aynı sayıda kaydın söz konusu olduğu bir durumda Ayıklamalı Sıralama daha kısa zamanda sonuç verir.

Çabuk ya da İkili Sıralama

Buraya dek sözünü ettiğimiz ve bir veriler dizisini sıralamaya yarayan her üç yöntem de temelde aynı ilkeye dayanmaktaydılar. Programın veriler üstünden sonlu bir sayıda tarama yapmasını sağlayan, içiçe yerleştirilmiş iki döngü kullanılır ve her taramanın sonunda tek bir eleman doğru haneye yerleştirilerek sonraki taramalarda hesaba katılmaz. Bu, yerleştirilmesi gereken hiçbir öge kalmayana kadar devam eder. Çabuk sıralama ise değişik bir kavrama dayanılarak geliştirilmiş bir yöntemdir. Dizideki ilk öge bir tür “başlama öbeği” ya da bir başka deyişle “pivot” olarak alınır ve diğer ögeler onunla kıyaslanırlar. Bu eldeki pivottan daha küçük olan bütün ögeler pivotun üstüne, daha büyük olanlarsa altına yerleştirilirler. Bu yolla, dizinin eski halinde en başta bulunan kayıt doğru haneye yazılmış olur ve diğer kayıtlarda ona göre doğru tarafta (altında ya da üstünde) yerlerini almış olurlar. Aynı prosedür (yordam) şimdi bu kaydın üstünde ve altında kalan kümelere ayrı ayrı uygulanır. Prosedür bu şekilde giderek küçülen alt kümelere uygulanmaya devam edilir ve sıralanacak alt küme tek bir ögeden ibaret kaldığında durdurulur. Sıralanacak hiçbir alt küme kalmadığında (ya da bütün alt kümeler tek bir ögeye indirgendiklerinde) dizinin bütünü de sıralanmış olacaktır. Sanırız bu yöntemin en iyi açıklamasını Çizim-4'te bulacaksınız.

Çizimi incelediğinizde iki gösterge (pointer) kullanılmış olduğunu göreceksiniz. Bunlardan biri gündemdeki kaydı gösterirken diğeri de dizideki kullanılabilir alanı gösterir. İlk aşamada göstergeler kümenin her iki ucuna yerleştirilmiştir. P1 göstergesi tarafından gösterilen eleman, doldurduğu hanenin üstüne yeni kayıt yapılabilecek biçimde, ayrı bir değişkene saklanmıştır. Kıyaslamalar şimdi P2 göstergesi tarafından gösterilen elemandan başlar: TAVUK KURT böylece P2 göstergesi eksiltilir. FARE KURT, böylece ZEBRA yerleştirilir ve bu noktadan aşağıya doğru işlem sürdürülür. ZEBRA KURT, bu yolla ZEBRA P2'ye yerleştirilir. Şimdi de işleme P2'den yukarıya doğru devam edilecektir. ARI KURT, böylece ARI P1'e yerleştirilir. Göstergeler artık buluşmuşlardır ve pivot, yani KURT bu noktaya yerleştirilebilir. Bu noktanın biri üstünde, biri de altında olmak üzere iki alt küme çıkmıştır ortaya ve her ikisine de şimdi ayrı ayrı Çabuk sıralama yordamını (routine) uygulamak gerekmektedir.

Programın çapından da görülebileceği gibi (liste 4) bu yöntem az önce ele aldığımız diğer yöntemlerden daha karmaşıktır. Her şeyden önce böyle bir sıralama yöntemi için daha fazla bellek gerekmektedir. Bunun nedeni, sadece programın göreceli olarak daha fazla yer tutması değil, aynı zamanda daha fazla değişken kullanmasıdır da. Söz gelimi henüz sıralanmamış alt kümelerin parametrelerinin saklanması için başlı başına bir deste-bellek (stack) görevlendirilmektedir. (Bir kerede ancak bir tek alt kümenin ele alınabileceğini anımsayın.) Bunların yanısıra Çabuk sıralamanın asıl çekiciliği tartışılmaz hızıdır. (Tablo-1'deki zamanlamalara bkz.) Sıralanacak ögelerin sayısı arttıkça diğer üç sıralama yönteminin gereksindikleri zaman üst sayısal (exponential) bir biçimde artarken, Çabuk sıralamanın öge başına harcadığı zaman, listenin çapı büyüse de, hemen hemen aynı kalmaktadır. Bu özellik denenmemiş bir listenin Çabuk sıralama ile ne kadar bir zamanda düzenlenebileceğini önceden kestirme olanağını verir. Bu tür bir sıralama baştan aşağı karışık yazılmış kütükleri sıralarken en etkin sonucu verecektir; ancak kısmi olarak düzenlenmiş bir kütüğe uygulandığında biraz daha yavaş çalışacağı söylenebilir. Ve dikkat! Bu seçmeye aldığımız sıralama yöntemlerinin tümü de aynı ögenin tekrarlandığı (duplicate) durumları işleme yeteneğine sahiptirler.

Uyarlamalar İçin İpuçları

Burada dikkat edilmesi gereken nokta, yukarıda listesi çıkarılmış programlarda bütün dizi alt indislerinin (subscript) sıfırdan başlamalarıdır.

Sözgelimi DIM IMFS(10) ifadesi IMFS$ için on bir hane ayırmış olmaktadır (on hane değil). Bütün sıfır elemanlar belleği tutumlu kullanmak amacıyla hesaba katılmışlardır ve bu noktanın özellikle alt indisleri 1'den başlatan aygıtlara uyarlama yaparken gözetilmesi gerekir. Gözden kaçırılmaması gereken bir başka nokta da SWAP ifadesinin (statement) kullanılışıdır. Bu ifade ardından gelen iki değişkenin içerdiklerini değiş tokuş ettirir. Böyle bir ifadeye sahip olmayan aygıtlar için “SWAP IMES(X), IMFS(Y)” satırı aşağıda gösterildiği gibi yeniden yazılabilir:

TEMP$ —- —
- TEMP$

Özet Olarak Söylenebilecekler

Kabarcık sıralama: • Kısmi sıralanmış kütükler için • Dar hacimli kütükler için • Bellek kapasitesinin daha yetkin yöntemleri uygulamaya yetmediği durumlarda. Dalgacık sıralama: • Kabarcık sıralamanın kullanıldığı yerlerde Ayıklamalı sıralama: • Dar/orta hacimli kütükler için • Bellek kapasitesinin daha yetkin yöntemleri uygulamaya yetmediği durumlarda Çabuk sıralama: • Orta/büyük hacimli kütükler için • Özellikle de kısmi olarak sıralanmamış olanlar için

Çizim-1 Kabarcık Sıralama

(a)

Kurt Zebra Arı Fare — Tavuk < Fare Tavuk — - Değiştirme yok

Kurt

Zebra — Arı < Zebra Arı — - Değiştirme var

Fare Tavuk

(b)

Arı (sıralanmış) Kurt

Zebra Fare Tavuk Fare Tavuk yok

Arı (s) Kurt — Fare < Kurt - Değiştirme var Zebra Tavuk

(c)

Arı (s) Fare (s)

Kurt Zebra Tavuk < Zebra

Tavuk < - Değiştirme var

(d)

Arı (s) Fare (s) Kurt (s) Tavuk, Zebra < Tavuk - Değiştirme yok

Kurt Zebra Fare Arı Fare - Değiştirme yok Tavuk

Kurt - Arı < Kurt Zebra - Değiştirme var Arı Fare Tavuk

Arı(s) Kurt Fare < Zebra Fare Değiştirme var Tavuk

Arı(s) Fare(s) Kurt - Tavuk < Kurt Tavuk yok Zebra

Dizi sıralanmıştır.

Çizim-2 Dalgacık Sıralama

(a)

Kurt - Kurt > Zebra Zebra - Değiştirme yok Arı Fare Tavuk

Kurt Arı

Zebra > Fare Fare Değiştirme var Tavuk

Kurt Zebra - Zebra > Arı - Değiştirme var Fare Tavuk

Kurt Arı Fare Zebra , Tavuk Tavuk - Değiştirme var

Kurt - Kurt > Arı - Değiştirme var

Fare Kurt Kurt > Tavuk - Değiştirme yok

(Cc)

Arı > Arı ? Fare Fare - Değiştirme yok Kurt Tavuk(s) Zebra(s)

Arı Kurt > Fare Fare - Değiştirme var Tavuk Zebra(s) MARKER = 1, bu nedenle bir sonraki taramaya geçiliyor. Arı

Fare - Fare > Kurt Kurt - Değiştirme yok Tavuk(s) Zebra(s)

MARKER = 0, demek ki dizi sıralanmıştır, çıkılır.

Çizim-3 Seçmeli Sıralama

(a) Kurt Zebra < Kurt

Zebra - Değiştirme yok Arı - Değiştirme var Fare Tavuk Arı - Fare $ Arı Zebra Kurt Fare - Değiştirme yok

Tavuk

(b)

Arı(s) Zebra - Kurt < Zebra - Değiştirme var Fare Tavuk

Arı(s)

Fare Tavuk

(c)

Arı(s) Fare(s) Zebra - Kurt < Zebra Kurt - Değiştirme var Tavuk

Kurt Tavuk < Fare a - Değiştirme yok

Kurt - Arı < Kurt Zebra Arı A Fare Tavuk

Tavuk Arı Zebra

Kurt Fare Tavuk - Değiştirme yok

Arı(s) Tavuk < Fare Fare - Zebra Kurt - Tavuk - Değiştirme yok

Arı(s) Fare(s) Kurt - Tavuk & Kurt Zebra - Değiştirme yok Tavuk

(d) Arı(s) Arı(s) Fare(s) Fare(s) Kurt(s) Kurt(s) Dizi Zebra - Tavuk < Zebra sıralanmıştır Tavuk - - Değiştirme var Zebra(s)

Çizim-4 Çabuk ya da İkili Sıralama

(a) Kurt Kurt-P1 Fare-P1 Fare Fare Zebra Zebra Zebra-P1 Arı Arı Arı Arı Fare Fare-P2 Zebra-P2 Zebra Tavuk-P2 Tavuk Tavuk Tavuk Tavuk < Kurt Zebra Kurt Arı < Kurt Fare < Kurt (b) Fare Fare-P1 Arı - Tek bir kayıt uzunluğunda Arı-P2 Arı-PA Fare küme Arı < Fare (Sıralanmış kabul edilir) (c) Zebra Zebra-P1 Tavuk - Tek bir kayıt uzunluğunda altküme Tavuk < Zebra Son durum: Arı Fare | 2 Kurt 1 Tavuk Zebra 3

PROGRAM ADI SORT

00085 REM >
680816 INPUT DIZINIZ KAC ELE
MANLI” <244>
006015 REM ACIYORUZ kkk <164>
660206 DIM IİM$<NU) <168>
88025 REM DOLDURUYORUZ <663>
68830 FOR TO “<eRİGHT>";LO
3". ELEMANI INPUT İM$<LOOP)
<867>
80635 REM BASLADI&&** <a14>
0860646 FOR Lz86 TO NU
608650 Ts8
66866 FOR L2z86 TO NU-1
IF IM$<L2)>1M$<L24*1) THEN
Tzi1 <088)>
686880 NEXT >
06890 IF THEN 108 <ı24>
66188 NEXT
808185 REM BITTI***
681867 REM YAZDIRIYORUZ <236)>
88188 PRINT ISTE SIRALI DIZI
<a23>
88116 FOR LOsi TO NU:PRİNT
SEND

PROGRAM ADI :

000801
66005
088007
600618

06026
60036

00833
00035
00837
60045
00046
08668

00878
00075
A8877
00680

66098

66108

PROGRAM ADI :

60805
00016

80015
08028
086025
000386

088035
00048
006858
608060

080878
086075
086076

00088

06088

06618
06028
06038
86040

06078

66688

26090
86108
06118

06128
06138
66148
06158
66160
06188

BUBBLE SORT

SORT**k
GİRİYORUZ &&&
INPUT "<2SPACE>KAC KELİME SIRALIYO
RUZ
DIM S$<NU)
FOR Lzi TO NU:PRİNT L?".
"3 1 INPUT
REM #*&*xDATALAR
Ni-NU
REM #k&kSİIMDİ SIİRALIYORUZ
SS$z"N"
FOR TO
IF THEN
tL

REM
REM
PRINT

KELİMEYİ

NEXT
IF SS$-"Y" THEN 45
REM
PRINT ISTE SIRALI DIZI
NIZ:”
FOR TO
L
END

SELECTION SORT

REM
INPUT KAC E
REM ACIYORUZ «kt
DIM
REM DOLDURUYORUZ
FOR Izi TO NiPRİNT
ELEMANI VERİN"? INPUT |
REM SIRALIYORUZ
FOR TO N-i
FOR TO N
IF THEN D$-5S$<L2)15$X
NEXT L2,L
REM
REM
PRİNT SIRA
LI DIZI:"
FOR TO G".
G

ELEMAN : “;S

REM YAPAN ALT PROGRAM
*kk
IF SSz1 THEN 6838
DIM
YYEBBIZZSALLBB)
IF THEN 6098
IF THEN SAS
8
IF THEN 605
g
OTO 6858
IF THEN 6148
iPPsPP43
68648
IF BB-XX<-1 THEN 6178
ON SSA<PP-1)GOTO 6180,6130,6168
RETURN

6040

<212>
<081>
<a51>

<117>

<116>
<846>
<046>
<125>

<137>
<213>
<184>

<001>

<171>

<164>
<063>

<a24>
<128>
<046>

<189>
<882>

<150>

<836>
<018>
<173>
<183>

<188>

<088>

<207>
<134>
<163>

<83939>
<184>

ile elde ettiğimiz listenin en sonunda gördüğümüz “XXX BLOCKS FREE” sözünden başlayalım. Buradan da kolayca anlaşılacağı gibi, VC-1541 bilgileri bloklar halinde saklıyor. Her bir blok 256 byte'dan oluşur ve bir diskette 683 adet blok vardır. Bunların 19 tanesini, daha sonra ayrıntısıyla göreceğimiz Directory kaplar. Böylece programlar ve veriler için disket üzerinde 664 blok kalmaktadır. Olaya daha fiziksel bir gözle bakarsak, disketin üzerinde TRACK'ların var olduğunu ve her bir TRACK'ın da belli, ancak her TRACK için farklı sayıda SECTOR'e sahip olduğunu görürüz. Şimdi TRACK ve SECTOR deyimlerini biraz açalım.

Disketin içi

Normalde kare şeklinde bir koruyucu içinde bulunan disket, aslında bir plak görüntüsüne sahiptir. Ve tıpkı plakların üzerindeki çizgiler gibi dairesel bölümlere ayrılmıştır. Ancak bunlar manyetik oldukları için belirgin olarak görünmezler. İşte bu dairelerin her birine TRACK adı verilir. VC-1541, en büyük çapa sahipse TRACK'ı 1, en içteki en küçük ise 35 ile numaralandırır. Yani toplam 35 TRACK vardır. 35-41 arasındaki TRACK'lara normal DOS komutları aracılığıyla ulaşmak mümkün değildir ve makine dilinde gelişmiş bir bilgi ile VC-1541'i çok iyi tanımayı gerektirir. Bu TRACK'lar, profesyonel

Programlarınızı, elinizdeki bilgileri emanet ediyorsunuz, ama...