Veri Yapısında Radix Sıralama Algoritması

Radix Sıralama Algoritması nedir?

Radix Sort, karşılaştırmalı olmayan bir sıralama algoritmasıdır. Sıralanacak öğelerin tek tek rakamlarını gruplayarak çalışır. Daha sonra öğeleri tabanlarına göre düzenlemek için kararlı bir sıralama tekniği kullanılır. Doğrusal bir sıralama algoritmasıdır.

Sıralama işlemi aşağıdaki özellikleri içerir:

Maksimum elemanı bulma ve o elemanın basamak sayısını elde etme. Bize sıralama sürecinin takip edeceği yineleme sayısını verir.
Her yinelemede öğelerin tek tek rakamlarını aynı anlamlı konumda gruplayın.
Gruplama işlemi en az anlamlı rakamdan başlayıp en anlamlı rakamda bitecektir.
Öğeleri bu önemli konumdaki rakamlara göre sıralamak.
Aynı anahtar değere sahip öğelerin göreceli sırasını korumak. Taban sıralamasının bu özelliği onu kararlı bir sıralama yapar.

Son yineleme bize tamamen sıralanmış bir liste verecektir.

Radix Sıralama Algoritmasının Çalışması

Yukarıdaki şekildeki tamsayıların listesini Radix Sort algoritmasını kullanarak artan şekilde sıralamaya çalışalım.

Radix Sıralama işlemini gerçekleştirme adımları şunlardır:

) 1 Adım Listedeki maksimum değere sahip öğeyi tanımlayın. Bu durumda 835'tir.

) 2 Adım Maksimum öğenin basamak sayısını hesaplayın. 835'in tam olarak 3 rakamı var.

) 3 Adım 2. adıma göre yineleme sayısını belirleyin. 835'in 3 hanesi vardır, yani yineleme sayısı 3 olacaktır.

) 4 Adım Elemanların tabanını belirleyin. Bu ondalık bir sistem olduğundan taban 10 olacaktır.

) 5 Adım İlk yinelemeyi başlatın.

a) İlk yineleme

İlk yinelemede her elemanın birim basamak değerini dikkate alıyoruz.

) 1 Adım Elemanların birim basamağını elde etmek için tamsayıyı 10'a kadar değiştirin. Örneğin 623 mod 10 bize 3 değerini, 248 mod 10 ise 8 değerini verir.

) 2 Adım Tamsayıları en az anlamlı basamaklarına göre düzenlemek için sayma sıralamasını veya başka herhangi bir kararlı sıralamayı kullanın. Şekilden görüldüğü gibi 248. kovaya 8 düşecektir. 623 3. kovaya düşecek ve bu böyle devam edecek.

İlk yinelemeden sonra liste artık şu şekilde görünüyor.

Yukarıdaki şekilden de görebileceğiniz gibi liste henüz sıralanmamıştır ve tam olarak sıralanması için daha fazla yineleme gerekmektedir.

b) İkinci yineleme

Bu yinelemede, 10'daki rakamı ele alacağız.^th sıralama işlemi için yer.

) 1 Adım Tam sayıları 10'a böleriz. 248'in 10'a bölünmesi bize 24 sonucunu verir.

) 2 Adım Adım 1'in çıktısını 10'a kadar modlayın. 24 mod 10 bize 4'ü verir.

) 3 Adım Önceki yinelemedeki 2. adımı izleyin.

İkinci tekrardan sonra liste şu şekilde görünüyor

Yukarıda verilen şekilden, listenin henüz tam olarak sıralanmadığını, büyükten küçüğe doğru sıralanmadığını görebilirsiniz.

c) Üçüncü yineleme

Son yineleme için en anlamlı rakamı elde etmek istiyoruz. Bu durumda 100^thListedeki tamsayıların her biri için yer.

) 1 Adım Tam sayıları 100'e böleriz... 415'i 100'e bölersek 4 veririz.

) 2 Adım 1. adımdaki sonucu 10'a değiştirin. 4 mod 10 bize yine 4 verir.

) 3 Adım Önceki yinelemedeki 3. adımı izleyin.

Gördüğümüz gibi liste artık artan sırada sıralanıyor. Son yineleme tamamlandı ve sıralama işlemi artık tamamlandı.

Radix Sıralama Algoritmasının Sahte Kodu

İşte Radix Sıralama Algoritmasının sözde kodu

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the j^th place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the j^thplace
   arr = sorted elements

C++ Radix Sıralamasını Uygulama Programı

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Çıktı:

162 248 415 623 835

Python Radix Sıralama Algoritması Programı

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Çıktı:

[162,248,415,623,835]

Radix Sort'un karmaşıklık analizi

Dikkate alınması gereken iki tür karmaşıklık vardır: uzay karmaşıklığı ve zaman karmaşıklığı.

Uzay karmaşıklığı: O(n+b) burada n dizinin boyutu, b ise dikkate alınan tabandır.
Zaman karmaşıklığı: O(d*(n+b)) burada d, dizideki en büyük elemanın basamak sayısıdır.

Radix Sort'un Uzay Karmaşıklığı

Uzay karmaşıklığı için odaklanılacak iki özellik

Dizideki eleman sayısı, n.
Elemanları temsil etmek için temel, b.

Bazen bu taban dizinin boyutundan daha büyük olabilir.

Dolayısıyla toplam karmaşıklık O(n+b)'dir.

Listedeki elemanların aşağıdaki özellikleri, taban sıralaması alanını verimsiz hale getirebilir:

Çok sayıda basamak içeren öğeler.
Elemanların tabanı 64 bitlik sayılar gibi büyüktür.

Radix Sort'un Zaman Karmaşıklığı

Her yineleme zaman alacağından sayma sıralamasını bir alt yordam olarak kullanabilirsiniz.e O(n+b) zaman. Yinelemeler mevcutsa, toplam çalışma süresi şu şekilde olur: Ö(d*(n+b)). Burada “O” karmaşıklık fonksiyonunu ifade etmektedir.

Taban Sıralamasının Doğrusallığı

Radix Sıralaması şu durumlarda doğrusaldır:

d sabittir; burada d, en büyük öğenin basamak sayısıdır.
b ile karşılaştırıldığında çok daha büyük değil n.

Radix Sort'un diğer karşılaştırmalı algoritmalarla karşılaştırılması

Gördüğümüz gibi, Radix sıralamasının karmaşıklığı bir kelime veya sayı boyutuna dayanır. Ortalama ve en iyi durumlar için aynı karmaşıklığa sahip olacaktır. Ve bu O(d*(n+b))'dir. Ayrıca, ortada kullandığınız sıralama tekniğine göre farklılık gösterir. Örneğin, Radix sıralaması içinde ara sıralama algoritması için sayma sıralamasını veya hızlı sıralamayı kullanabilirsiniz.

Radix Sıralama Algoritmasının Uygulamaları

Radix Sıralamanın Önemli Uygulamaları şunlardır:

Radix Sort, geniş değer aralıklarının kullanıldığı bir konum bulma algoritması olarak kullanılabilir.
DC3 algoritmasında sonek dizisinin oluşturulmasında kullanılır.
Kayıtların anahtarlandığı tipik bir bilgisayarda bulunan sıralı, rastgele erişimli bir makinede kullanılır.

Beğenebilirsin: