Sayarak Sıralama (Counting Sort) Algoritması Ve QBasic Programa Dili İle Kodlanması
Algoritma Hakkında Bilgiler
- Counting sort veri kümesinde yer alan elemanların aralığını kullanarak sıralama yapan bir sıralama algoritmasıdır.
- Saymalı sıralama algoritması verilerin aralığını kullanarak sıralama yapar.
- 1954 yılında Harold H. Seward tarafından yapılmıştır.
- Sayarak sıralama algoritması güvercin yuvası sıralamasından (Pigeonhole Sort) daha verimsiz bir algoritmadır.
Avantajları
- n ve k da doğrusaldır (lineer).
- Kolay uygulanır.
Dezavantajları
- Yerinde sıralama yapmaz. Ekstra depolama alanına ihtiyaç duyar.
- Sayıların küçük tam sayı olduğu varsayılır.
- Byte ise ek dizinin boyutu en fazla 28= 256 olur fakat sayılar int ise yani 32 bit lik sayılar ise 232= 4.2 milyar sayı eder oda yaklaşık 16 Gb yer tutar.
Çalışma Mantığı
- Sayarak sıralama algoritması dizideki değerlerin aralık bilgilerini yeni bir dizi oluşturmak için kullanır. Oluşturulan yeni dizinin her bir satırı ana dizide o satır numarasının değerine sahip ögelerin sayısını gösterir. Yeni dizideki öge değeri sayıları daha sonra ana dizideki tüm değerlerin doğru konuma konulması için kullanılır.
ALGORİTMANIN ANALİZİ
En iyi durum mevcut değildir.
Ortalama ve En Kötü Durum: O(n+r) dir.
Potansiyel değerler aralığı büyükse, sıralama sayımı çok fazla alan gerektirir
QBasic Kodları
COLOR 5, 9
CLS
‘Dizi degerinin boyutunu tutmak icin tamsayi olustur
DIM diziboyutu AS INTEGER
diziboyutu = 7 ‘Dizi boyutunu ayarla
‘Siralanacak dizi olustur
DIM dizisiralanmasi(diziboyutu) AS INTEGER
‘Diziyi siralanmamis degerlerle baslat
dizisiralanmasi(diziboyutu – 7) = 1 ‘4
dizisiralanmasi(diziboyutu – 6) = 6 ‘2
dizisiralanmasi(diziboyutu – 5) = 8 ‘2
dizisiralanmasi(diziboyutu – 4) = 3 ‘3
dizisiralanmasi(diziboyutu – 3) = 5 ‘3
dizisiralanmasi(diziboyutu – 2) = 1 ‘3
dizisiralanmasi(diziboyutu – 1) = 10 ‘1
‘Dizinin icerigini siralamadan once yazdir
COLOR 10
PRINT “Siralamadan once dizi islemi:”
CALL diziyazdir(dizisiralanmasi(), diziboyutu)
‘Diziyi sirala
CALL count_sort(dizisiralanmasi(), diziboyutu)
‘Dizinin icerigini siraladiktan sonra yazdir
COLOR 12
PRINT “Siralamadan sonra dizinin icerigi:”
CALL diziyazdir(dizisiralanmasi(), diziboyutu)
SUB count_sort (pArraySort() AS INTEGER, pArraySizeSort AS INTEGER)
‘Diziyi siralama islevi
DIM i, max AS INTEGER
DIM cikandizi(pArraySizeSort + 3), dizimiktari(pArraySizeSort) AS INTEGER
max = pArraySort(0)
‘Dizideki en buyukk elemani bul
FOR i = 0 TO pArraySizeSort – 1
IF pArraySort(i) > max THEN
max = pArraySort(i)
END IF
NEXT
‘Sayimin boyutu en az max + 1 olmalidir
REDIM dizimiktari(max + 1)
‘Diziyi sifirlarla baslat
FOR i = 0 TO max
dizimiktari(i) = 0
NEXT
‘Birikimli sayimini depola
FOR i = 1 TO max
dizimiktari(i) = dizimiktari(i) + dizimiktari(i – 1)
NEXT
‘Sayim dizisindeki orijinal dizinin her ogesinin dizinini bul ve ogeleri cikis dizisine yerlestir
FOR i = pArraySizeSort – 1 TO 0 STEP -1
cikandizi(dizimiktari(pArraySort(i)) – 1) = pArraySort(i)
dizimiktari(pArraySort(i)) = dizimiktari(pArraySort(i)) – 1
NEXT
‘Siralanan ogeleri orijinal diziye kopyala
FOR i = 0 TO pArraySizeSort – 1
pArraySort(i) = cikandizi(i)
NEXT
END SUB
SUB diziyazdir (pArrayPrint() AS INTEGER, pArraySizePrint AS INTEGER)
‘Diziyi yazdirma islevi
DIM x AS INTEGER
FOR x = 0 TO pArraySizePrint – 1
PRINT pArrayPrint(x)
NEXT
END SUB
Çözümlü Örnekler
- Sıralanmak İstenen Veriler:1,6,8,3,5,1,10
Sıralanmış hali:1,1,3,5,8,8,10
- Sıralanmak İstenen Veriler:8,9,1,2,2,5
Sıralanmış hali:1,2,2,5,9
- Sıralanmak İstenen Veriler:8,6,7,7,5,1,3,3
Sıralanmış hali:1,3,3,6,7,78
NOT:
Ödev amaçlı olduğu için farklı kaynaklardan faydalanılıp derlenmiştir.
Kaynakça:
- Avantaj ve Dezavantaj:https://isakordis.wordpress.com/2019/03/31/counting-sort-yapisi-algoritmasi-ve-calisma-zamani/
- ALGORİTMANIN ANALİZİ:https://buraktahtacioglu.blogspot.com/2016/03/algoritma-tasarm-ve-analizi-algorithm_22.html
- Çalışma Mantığı:https://www.ismailbasoglu.com.tr/algoritmalar/couting-sort-saymali-siralama-algoritmasi.html
- Videodaki online site :https://www.cs.usfca.edu/~galles/visualization/CountingSort.html
- Kodlar https://www.programiz.com/dsa/counting-sort?fbclid=IwAR2hWz2IoBts_a5r-Q5KjO_0icMLlgblPCx71wskXFHVygMQnBW006CxER0 sitesinde ‘’c ‘’ dilinden çevrilmiştir.
