Radix Sort - Sıralama Algoritmaları - burakkose:blog

Türkçe'de taban sıralaması , basamaklı sıralama , kök sıralaması veya hane sıralaması olarak geçen bu algoritmada sıralanacak olan veriler hanelerine göre sıralanır.En değersiz olan haneden en değerli haneye doğru sıralama işlemi yapılır.

Sıralanacak verilerin tamsayı olduğu durumlarda kullanılan bu algoritma işlenirken ilk olarak sıralanacak olan veri kümesindeki elemanların en büyük elemanının kaç basamaklı olduğu tespit edildikten sonra sayıların en değersiz olan basamağından itibaren incelenmeye başlanır ve yeni bir diziye yerleştirilir.Bu işlem dizinin en büyük elemanının basamak sayısı kadar tekrar edilir.

Bu algoritmanın çalışma zamanı O(nk) ve yer karmaşıklığı O(n+k) olacaktır.Gayet iyi bir çalışma zamanına sahip olmasının nedeni bu algoritmanın karşılaştırmalı bir sıralama algoritması olmamasıdır.En büyük dezavantajı ise her basamak işlemi için yeni bir bellek alanı gerektirmesidir.

Direkt Basamaklı SIralama ( Straight Radix Sort) algoritmasına bir örnek verelim.

Sayılarımız : 32 , 224 , 16 , 15 , 31 , 169 , 123 , 252 olsun ve çözümümüz için aşağıdaki gibi bir tablo ile daha rahat işlemlerimiz anlaşılır.

İlk olarak sayılar aşağıdaki gibi tabloya yerleştirildi.


Hane3,Hane2,Hane1
0,3,2
2,2,4
0,1,6
0,1,5
0,3,1
1,6,9
1,2,3
2,5,2

Hane1'e göre sıralama gerçekleştirildi.


Hane3,Hane2,Hane1
0,3,1
0,3,2
2,5,2
1,2,3
2,2,4
0,1,5
0,1,6
1,6,9

Hane1 sıralaması bittikten sonra Hane2 sıralaması gerçekleştirildi.


Hane3,Hane2,Hane1
0,1,5
0,1,6
1,2,3
2,2,4
0,3,1
0,3,2
2,5,2
1,6,9

ve son olarak maksimum sayımızın hane sayısına ulaşıldı ve Hane3'e göre sıralama gerçekleştirildi.


Hane3,Hane2,Hane1
0,1,5
0,1,6
0,3,1
0,3,2
1,2,3
1,6,9
2,2,4
2,5,2

Her şey güzel peki sayının kaç basamaklı olduğunu nereden anlayacağız diyorsanız.

basamak sayısı = int(log(taban,max) + 1)

Örneğin üstteki örneğimizde en büyük eleman 252 sayısı ve bu sayılar 10 tabanındadır.Dolayısı ile
log(10,252) + 1 = 3,401 olur ve bunu int çevirirsek = 3 çıkar.Şimdi bu algoritmamızın örnek kodlarına gelelim.

from math import log def getEmptyList(size): # Boş bir liste döndürür return [ [] for i in range(size) ] def getDigit(num, base, digit_num): # Hanelere göre değeri seçer # Örnek 123 sayısının ilk hanesi = 3 return (num // base ** digit_num) % base def maxWithAbs(p_list): # Maksimum sayıyı işaret farkı olmadan döndürür return max(abs(dig) for dig in p_list) def mergeList(p_list): # Parametre olarak aldığı listeyi birlştirir new_list = [] for sub in p_list: new_list.extend(sub) return new_list def split(s_list , base , digitNum): temp_list = getEmptyList(base) for number in s_list: temp_list[getDigit(number, base, digitNum)].append(number) return temp_list def splitBySign(p_list): # işaretli sayıları gruplar buffer = [[], []] for num in p_list: if num < 0: buffer[0].append(num) else: buffer[1].append(num) return buffer def radixSort(_list,base): digitNum = int(log(maxWithAbs(_list),base) + 1) for dig in range(digitNum):#İşaretlere bakmaksızın sıralıyor _list = mergeList(split(_list, base, dig)) return mergeList(splitBySign(_list))#işaretleri dikkate alıyor ve düzenliyor liste = [123,113,55,11,56,7,1,-1,2] print(radixSort(liste, 10))

Basamaklı Yer Değiştirme Sıralaması(Radix Exchange Sort)

Şimdi direkt yerleştirmeli sıralamanın düzenlemiş hali olan Basamaklı Yer Değiştirme Sıralaması'nı inceleyelim.Kısaca farkları şudur.Direkt basamaklı sıralama algoritmasında sağdan-sola doğru yol alınırken bu yaklaşımda soldan-sağa doğru yol alınır ve en önemli avantajı bu algoritmada her basamak için özel bir bellek alanına ihtiyaç duyulmayacaktır.Bu algoritma içerisindeQuick Sort(Hızlı Sıralama) algoritması kullanılmıştır.

Sayılar ikili(binary) olarak tutulduğundan taban değişimi için ek bir işlem yapılmasına gerek yoktur.Algoritmanın kodunu verirken biraz modifiye ettiğimden söz etmeliyim.Ufak değişiklikler ile negatif sayılar içinde işleyebilmesi için düzenledim.

from math import log def swap(n1,n2): return n2 , n1 def getDigit(num, digit_num): return (num >> digit_num) & 0x01 def splitBySign(p_list): # işaretli sayıları gruplar buffer = [[], []] for num in p_list: if num < 0: buffer[0].append(num) else: buffer[1].append(num) return buffer def exchange(liste,down,up,digit): if up > down and digit >= 0: _down , _up = down , up while(_up > _down): while(getDigit(liste[_down], digit) == 0 and _down < _up): _down += 1 while(getDigit(liste[_up], digit) == 1 and _down < _up): _up -= 1 liste[_down] , liste[_up] = swap(liste[_down], liste[_up]) if(getDigit(liste[up], digit) == 0): _up += 1 exchange(liste,down,_up -1,digit -1) exchange(liste,_down,up,digit-1) def RadixExchangeSort(p_list): temp_buffer = splitBySign(p_list) #sayıları işaretine göre gruplandırdık negative_list , possitive_list = temp_buffer[0] , temp_buffer[1] if len(negative_list) > 0:#Eğer negatif sayı varsa exchange(negative_list,0,len(negative_list)-1,int(log(abs(min(negative_list)),2) + 1)) if len(possitive_list) > 0:#Eğer pozitif sayı varsa exchange(possitive_list,0,len(possitive_list)-1,int(log(max(possitive_list),2) + 1)) return negative_list + possitive_list #Deneme liste = [31,30,29,-10,3,1,6,8,-123,-1233,-999] print(RadixExchangeSort(liste))

BURAK KÖSE

Comments