Radix Sort Algoritması


Radiks sort algoritması, 1887 yılında Herman Hollerith’in geliştirdiği “tabulating machine” için kullandığı yönteme dayanır.

  • Yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir.
  • Algoritma O(n) zaman karmaşıklığına sahiptir.
  • Alan maliyeti yüksektir.
  • Çok fazla miktarda sayı sıralanacaksa yönetimi zordur.
  • İki farklı şekilde kullanılabilir. En anlamlı basamağa göre(most significant digit) sıralama ve en anlamsız basamağa göre(least significant digit) sıralama.

Örnek vermek gerekirse;

156,38,147,159,254,300,29,79 sayılarını hep birlikte sıralayalım

1. adımda tüm sayılarımızın aynı sayıda haneden oluşması gerekir. Bunun için iki basamaklı sayılarımızın başına 0 yazıyoruz.

156,038,147,159,254,300,029,079

2. adımda sıralamamıza başlıyoruz .(ben en değersiz basamağa göre sıralama yapacağım) birler basamağındaki sayıların değerlerine göre sıralamaya başlıyorum.

300,254,156,147,38,159,029,079

3. adımda onlar basamağına göre sıralamamızı yapıyoruz.

300,029,038,147,245,156,159,079

4.adımda yüzler basamağına göre sıralamamızı yapıyoruz.

029,038,079,147,156,159,254,300

 

radix_sort

Çıktı:

radix_sort2

 

Yararlandığım kaynaklar:

http://www.geeksforgeeks.org/radix-sort/

https://en.wikipedia.org/wiki/Radix_sort

 

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.