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

Radix Sıralama Algoritması nedir?

Radix sıralama, karşılaştırmalı olmayan bir sıralama algoritmasıdır. Gruplara ayırma yöntemiyle çalışır.ping Sıralanacak elemanların tek tek rakamları kullanılır. Daha sonra, elemanları tabanlarına göre düzenlemek için kararlı bir sıralama tekniği kullanılır. Bu, doğrusal bir sıralama algoritmasıdır.

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

• En büyük elemanı bulmak ve o elemanın basamak sayısını elde etmek. Bu, sıralama işleminin gerçekleştirdiği yineleme sayısını verir.
• Grouping Her yinelemede aynı anlamlı konumdaki elemanların tek tek rakamları.
• Grupping İşlem en düşük anlamlı basamaktan başlar ve en yüksek anlamlı basamakta sona erer.
• Öğeleri, o önemli konumdaki rakamlara göre sıralamak.
• Aynı anahtar değerine sahip elemanların göreceli sıralamasını korumak. Radix Sort'un bu özelliği onu kararlı bir sıralama algoritması yapar.

Son yineleme tamamen sıralanmış bir liste döndürür.

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

Sıralanacak tam sayıların listesi

Yukarıdaki şekildeki tamsayı listesini Radix Sort kullanarak artan sırada sıralayalım.

Radix Sıralama işlemini gerçekleştirmek için izlenecek adımlar şunlardır:

) 1 Adım Listedeki en büyük elemanı bulun. Burada 835'tir.

) 2 Adım Rakamlarını sayın. 835'in 3 rakamı vardır, dolayısıyla yineleme sayısı 3'tür.

) 3 Adım Tabanı belirleyin. Bu ondalık sayı olduğu için taban 10'dur.

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

a) İlk yineleme

Son haneye göre sıralama

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

) 1 Adım Sayıyı 10'a göre mod alarak elemanların birler basamağını elde edin. Örneğin, 623 mod 10 3, 248 mod 10 ise 8 verir.

) 2 Adım Sayıları en düşük anlamlı basamaklarına göre düzenlemek için sayma sıralaması veya başka bir kararlı sıralama algoritması kullanın. Şekilden de görüldüğü gibi, 248 8. kovaya, 623 3. kovaya ve benzer şekilde diğer sayılar da aynı sıraya girer.

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

İlk yinelemeden sonraki liste

Liste henüz sıralanmadı ve daha fazla yineleme gerektiriyor.

b) İkinci yineleme

Onlar basamağındaki rakamlara göre sıralama

Bu aşamada, sıralama işlemi için onlar basamağındaki rakamı dikkate alıyoruz.

) 1 Adım Sayıları 10'a bölün. Örneğin, 248'i 10'a bölerseniz 24 elde edersiniz.

) 2 Adım 1. adımın sonucunu 10'a göre mod alın. 24 mod 10, 4'ü verir.

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

İkinci yinelemeden sonra liste artık şöyle görünüyor:

İkinci yinelemeden sonraki liste

Liste henüz artan sırada olmadığı için tamamen sıralanmış değil.

c) Üçüncü yineleme

Yüzler basamağındaki rakamlara göre sıralama

Son yinelemede, en anlamlı basamağı elde etmek istiyoruz. Bu durumda, listedeki her bir tamsayının yüzler basamağını elde ediyoruz.

) 1 Adım Sayıları 100'a bölün. Örneğin, 415'i 100'a bölerseniz 4 elde edersiniz.

) 2 Adım 1. adımdaki sonucu 10'a göre mod alın. 4 mod 10, 4'ü verir.

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

Üçüncü yinelemeden sonraki liste

Liste artık artan sırada sıralandı. Son yineleme tamamlandı ve sıralama işlemi sona erdi.

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 jth 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 in the jth place
    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 integer
    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 in 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

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

Çıktı:

[162, 248, 415, 623, 835]

Radix Sıralama Algoritmasının Karmaşıklık Analizi

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

• Alan karmaşıklığı: O(n + b) burada n dizinin boyutu ve b 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ığı

Alan karmaşıklığı için odaklanılması gereken iki özellik:

• Dizideki eleman sayısı, n.
• Öğeleri temsil etmek için kullanılan taban, b.

Bazen bu taban, dizinin boyutundan daha büyük olabilir. Dolayısıyla genel karmaşıklık O(n + b) olur.

Listedeki elemanların aşağıdaki özellikleri, Radix Sıralama algoritmasını alan kullanımı açısından 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ığı

Sayma sıralama algoritmasını alt program olarak kullanarak, her yineleme şu kadar sürer: O(n + b) zaman. Yinelemeler mevcutsa, toplam çalışma süresi şu şekilde olur: O(d * (n + b))Burada "O" karmaşıklık fonksiyonunu ifade etmektedir.

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

Radix Sort algoritması şu durumlarda doğrusaldır:

• d sabittir; burada d, en büyük öğenin basamak sayısıdır.
• b önemli ölçüde daha büyük değildir n.

Radix Sıralama Algoritmasının Diğer Sıralama Algoritmalarıyla Karşılaştırılması Algorithms

Radix Sort'un karmaşıklığı sayının büyüklüğüne bağlıdır. En iyi durum ve ortalama durum her ikisi de O(d * (n + b))'dir. Performans, iç sıralama algoritmasına göre değişir; sayma sıralaması standarttır, ancak herhangi bir kararlı sıralama algoritması da işe yarar.

Radix Sıralama Algoritmasının Uygulamaları

Radix Sort algoritmasının önemli uygulama alanları şunlardır:

• Radix sıralama algoritması, geniş değer aralıklarının söz konusu olduğu durumlarda konum bulma algoritması olarak kullanılabilir.
• DC3 algoritmasında sonek dizisi oluşturmak için kullanılır.
• Kayıtların sabit genişlikli tanımlayıcılarla anahtarlandığı sıralı, rastgele erişimli makinelerde kullanılır.

SSS