Bilgi Akışı

Sayarak Sıralama (Counting Sort) Algoritması

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:

Yazar

İlgili Makaleler

Bir Cevap Yazın

Göz Atın
Kapalı
Başa dön tuşu
%d blogcu bunu beğendi: