Radix Sort: Απλή Εξήγηση

Τι είναι το Radix Sort;

Ο Radix Sort είναι ένας αλγόριθμος ταξινόμησης που χρησιμοποιείται για την ταξινόμηση ακέραιων αριθμών. Λειτουργεί με την ταξινόμηση των αριθμών ψηφίο προς ψηφίο, από το λιγότερο σημαντικό ψηφίο (LSD) προς το πιο σημαντικό ψηφίο (MSD).

Πώς Λειτουργεί;

Ψηφιοί Διαχωριστές: Χρησιμοποιεί μια στατική μέθοδο (όπως Counting Sort) για να ταξινομήσει τους αριθμούς βάσει κάθε ψηφίου.
Επανάληψη: Επαναλαμβάνει τη διαδικασία για όλα τα ψηφία, μέχρι να ταξινομηθούν πλήρως οι αριθμοί.

Βήματα του Radix Sort

Ακολουθεί η ψευδογλώσσα για να κατανοήσεις τη διαδικασία:

ΛΕΞΗ RadixSort(A)
    max = μέγιστο_αριθμό_στον_πίνακα(A)
    digit = 1 // Ψηφίο που εξετάζουμε

    ΕΩΣ digit ≤ max
        CountingSort(A, digit)
        digit = digit * 10
    ΤΕΛΟΣ_ΕΩΣ
ΤΕΛΟΣ

Υλοποίηση του Counting Sort

Για να ταξινομήσουμε με βάση ένα ψηφίο, χρησιμοποιούμε τον Counting Sort. Η ψευδογλώσσα είναι η εξής:

ΛΕΞΗ CountingSort(A, digit)
    n = μήκος(A)
    output = νέο_πίνακα(n)
    count = νέο_πίνακα(10) // Για 10 ψηφία (0-9)

    // Αρχικοποίηση του count
    ΓΙΑ i ΑΠΟ 0 ΕΩΣ 9
        count[i] = 0
    ΤΕΛΟΣ_ΓΙΑ

    // Μετρήσεις
    ΓΙΑ i ΑΠΟ 0 ΕΩΣ n-1
        index = (A[i] / digit) % 10
        count[index]++
    ΤΕΛΟΣ_ΓΙΑ

    // Συσσώρευση
    ΓΙΑ i ΑΠΟ 1 ΕΩΣ 9
        count[i] += count[i - 1]
    ΤΕΛΟΣ_ΓΙΑ

    // Δημιουργία του output πίνακα
    ΓΙΑ i ΑΠΟ n-1 ΕΩΣ 0
        index = (A[i] / digit) % 10
        output[count[index] - 1] = A[i]
        count[index]--
    ΤΕΛΟΣ_ΓΙΑ

    // Αντιγραφή του output στον αρχικό πίνακα
    ΓΙΑ i ΑΠΟ 0 ΕΩΣ n-1
        A[i] = output[i]
    ΤΕΛΟΣ_ΓΙΑ
ΤΕΛΟΣ

C# Υλοποίηση

Ακολουθεί η υλοποίηση του Radix Sort στην C#:

using System;

class Program
{
    public static void RadixSort(int[] arr)
    {
        int max = GetMax(arr); // Βρίσκουμε το μέγιστο αριθμό
        for (int digit = 1; max / digit > 0; digit *= 10)
        {
            CountingSort(arr, digit); // Ταξινόμηση με βάση το τρέχον ψηφίο
        }
    }

    public static void CountingSort(int[] arr, int digit)
    {
        int n = arr.Length;
        int[] output = new int[n];
        int[] count = new int[10];

        // Αρχικοποίηση του count
        for (int i = 0; i < 10; i++)
        {
            count[i] = 0;
        }

        // Μετρήσεις
        for (int i = 0; i < n; i++)
        {
            int index = (arr[i] / digit) % 10;
            count[index]++;
        }

        // Συσσώρευση
        for (int i = 1; i < 10; i++)
        {
            count[i] += count[i - 1];
        }

        // Δημιουργία του output πίνακα
        for (int i = n - 1; i >= 0; i--)
        {
            int index = (arr[i] / digit) % 10;
            output[count[index] - 1] = arr[i];
            count[index]--;
        }

        // Αντιγραφή του output στον αρχικό πίνακα
        for (int i = 0; i < n; i++)
        {
            arr[i] = output[i];
        }
    }

    public static int GetMax(int[] arr)
    {
        int max = arr[0];
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i] > max)
            {
                max = arr[i];
            }
        }
        return max;
    }

    static void Main()
    {
        int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
        RadixSort(arr);
        Console.WriteLine("Ταξινομημένος πίνακας:");
        Console.WriteLine(string.Join(", ", arr));
    }
}

Πώς Λειτουργεί ο Κώδικας

RadixSort: Καλεί τον Counting Sort για κάθε ψηφίο.
- Ξεκινά από το λιγότερο σημαντικό ψηφίο (1) και προχωρά.

CountingSort: Ταξινομεί με βάση το συγκεκριμένο ψηφίο.
- Δημιουργεί ένα πίνακα μετρήσεων και ένα output πίνακα.

GetMax: Βρίσκει το μέγιστο αριθμό στον πίνακα, για να ξέρουμε πόσα ψηφία πρέπει να εξετάσουμε.

Παράδειγμα

Ας δούμε πώς λειτουργεί ο αλγόριθμος με ένα παράδειγμα:

C# Learning

Radix Sort (Ακτίνα)