1.10 Radix Sort

Category Algorithm

Radix sort is a non-comparative integer sorting algorithm that works by dividing integers into different digits based on their place value and then comparing each digit. Since integers can also represent strings (such as names or dates) and specific formatted floating-point numbers, radix sort is not limited to integers.

1. Radix Sort vs Counting Sort vs Bucket Sort

Radix sort has two methods:

These three sorting algorithms all utilize the concept of buckets, but they differ significantly in how they use the buckets:

• Radix Sort: Distributes numbers into buckets based on each digit of the key value.
• Counting Sort: Each bucket stores a single key value.
• Bucket Sort: Each bucket stores a range of values.

2. LSD Radix Sort Animation

Code Implementation

JavaScript

Example

// LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if (counter[bucket] == null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for (var j = 0; j < counter.length; j++) {
            var value = null;
            if (counter[j] != null) {
                while ((value = counter[j].shift()) != null) {
                    arr[pos++] = value;
                }
            }
        }
    }
    return arr;
}

Java

Example

/**
 * Radix Sort
 * For handling negative numbers, refer to: https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // Copy arr to avoid modifying the parameter content
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * Get the highest digit
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLength(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLength(long num) {
        if (num == 0) {
            return 1;
        }
        int length = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            length++;
        }
        return length;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // Considering negative numbers, we double the number of queues, where [0-9] corresponds to negative numbers and [10-19] to positive numbers (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * Auto-resize and save data
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

PHP

Example

function radixSort($arr, $maxDigit = null)
{
    if ($maxDigit === null) {
        $maxDigit = max($arr);
    }
    $counter = [];
    for ($i = 0; $i < $maxDigit; $i++) {
        for ($j = 0; $j < count($arr); $j++) {
            preg_match_all('/\d/', (string) $arr[$j], $matches);
            $numArr = $matches[0];
            $lenTmp = count($numArr);
            $bucket = array_key_exists($lenTmp - $i - 1, $numArr)
                ? intval($numArr[$lenTmp - $i - 1])
                : 0;
            if (!array_key_exists($bucket, $counter)) {
                $counter[$bucket] = [];
            }
            $counter[$bucket][] = $arr[$j];
        }
        $pos = 0;
        for ($j = 0; $j < count($counter); $j++) {
            $value = null;
            if ($counter[$j] !== null) {
                while (($value = array_shift($counter[$j])) !== null) {
                    $arr[$pos++] = $value;
                }
            }
        }
    }

    return $arr;
}

C++

Example

int maxbit(int data[], int n) // Helper function to get the maximum number of digits
{
    int maxData = data[0]; ///< Largest number
    /// First find the largest number, then find its digit count, which is slightly optimized over checking each number's digit count.
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        // p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; // Save the maximum digit count
    int p = 10;
    for (int i = 0; i < n; ++i)
    {
        while (data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d; */
}
void radixsort(int data[], int n) // Radix sort
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; // Counter
    int i, j, k;
    int radix = 1;
    for (i = 1; i <= d; i++) // Perform sorting d times
    {
        for (j = 0; j < 10; j++)
            count[j] = 0; // Clear the counter before each distribution
        for (j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; // Count the number of records in each bucket
            count[k]++;
        }
        for (j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; // Assign positions in tmp to each bucket
        for (j = n - 1; j >= 0; j--) // Re-sort the array based on the current digit
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for (j = 0; j < n; j++) // Copy tmp back to data
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete[] tmp;
    delete[] count;
}

for(j = n - 1; j >= 0; j--) // Collect all bucket records into tmp sequentially
{
    k = (data[j] / radix) % 10;
    tmp[count[k] - 1] = data[j];
    count[k]--;
}
for(j = 0; j < n; j++) // Copy the contents of the temporary array to data
    data[j] = tmp[j];
radix = radix * 10;
}
delete []tmp;
delete []count;
}

C

Example

#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10

void print(int *a, int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d\t", a[i]);
}
}

void radixsort(int *a, int n) {
int i, b[MAX], m = a[0], exp = 1;

for (i = 1; i < n; i++) {
if (a[i] > m) {
m = a[i];
}
}

while (m / exp > 0) {
int bucket[BASE] = { 0 };

for (i = 0; i < n; i++) {
bucket[(a[i] / exp) % BASE]++;
}

for (i = 1; i < BASE; i++) {
bucket[i] += bucket[i - 1];
}

for (i = n - 1; i >= 0; i--) {
b[--bucket[(a[i] / exp) % BASE]] = a[i];
}

for (i = 0; i < n; i++) {
a[i] = b[i];
}

exp *= BASE;

#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}

int main() {
int arr[MAX];
int i, n;

printf("Enter total elements (n <= %d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;

printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("\nARRAY : ");
print(&arr[0], n);

radixsort(&arr[0], n);

printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");

return 0;
}

Lua

Example

-- Get the number of digits in the table
local maxBit = function (tt)
local weight = 10; -- Decimal system
local bit = 1;

for k, v in pairs(tt) do
while v >= weight do
weight = weight * 10;
bit = bit + 1;
end
end
return bit;
end
-- Radix sort
local radixSort = function (tt)
local maxbit = maxBit(tt);

local bucket = {};
local temp = {};
local radix = 1;
for i = 1, maxbit do
for j = 1, 10 do
bucket[j] = 0; -- Clear the bucket
end
for k, v in pairs(tt) do
local remainder = math.floor((v / radix)) % 10 + 1;
bucket[remainder] = bucket[remainder] + 1; -- Each bucket count increases by 1
end

for j = 2, 10 do
bucket[j] = bucket[j - 1] + bucket[j]; -- Each bucket count = previous bucket count + own count
end
-- Sort by bucket position -- This is bucket sort, must use reverse order, because the sorting method is from small to large, in order, a large number will appear above a small number.
for k = #tt, 1, -1 do
local remainder = math.floor((tt[k] / radix)) % 10 + 1;
temp[bucket[remainder]] = tt[k];
bucket[remainder] = bucket[remainder] - 1;
end
for k, v in pairs(temp) do
tt[k] = v;
end
radix = radix * 10;
end
end;

>

Reference address:

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md

https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

#

-

** locenco

* zha**[email protected]

In the Java code, mod is multiplied by 10 in each loop, but the number of rows in counter does not need to change and can include [-9,9].

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// Consider negative numbers, here we double the number of queues, where [0-9] corresponds to negative numbers, [10-19] corresponds to positive numbers (bucket + 10)
int[][] counter = new int[20][0];

for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + 10;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}

int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}

** locenco

* zha**[email protected]

-

** Azirjiang

* bju**[email protected]

Azirjiang supplements the radix sort algorithm using C# as follows:

/// Radix Sort
static void RadixSort(List<int> list)
{
int maxValue = list.Max(); // Use the Max method from Linq
int it = 0; // Number of passes needed
// maxvalue 9-1 99-2 999-3
// 10^0<=9 10^1>9 it=1
// 10^0&lt;99 10^1&lt;99 10^2>99 it=2
while (Math.Pow(10, it) <= maxValue)
{
List<List<int>> buckets = new List<List<int>>(10); // Divide into 10 buckets corresponding to 0-9
for (int i = 0; i < 10; i++)
{
buckets.Add(new List<int>());
} // Initialize the list size
for (int i = 0; i < list.Count; i++) // Fill the buckets
{
// 989 it=0 989/10^it=989 989%10=9;
int digit = (int)((list[i]) / (Math.Pow(10, it)) % 10); // Get the corresponding bucket
buckets[digit].Add(list[i]);
} // All elements are in the buckets
list.Clear(); // Take them out in order
for (int i = 0; i < buckets.Count; i++)
{
list.AddRange(buckets[i]);
}
it += 1; // Continue to the next loop for filling and emptying the buckets
}
}

** Azirjiang

* bju**[email protected]

-

** Fighting Chang Laoshi

* 153**[email protected]

** Reference address

Supplement the radix sort code implementation in Python:

def radix_sort(data):

if not data:
return []
max_num = max(data) # Get the largest number in the current list
max_digit = len(str(abs(max_num))) # Get the maximum number of digits

dev = 1 # Which digit, ones place is 1, tens place is 10...
mod = 10 # Modulus division
for i in range(max_digit):
radix_queue = [list() for k in range(mod * 2)] # Consider negative numbers, we use double the queues
for j in range(len(data)):
radix = int(((data[j] % mod) / dev) + mod)
radix_queue[radix].append(data[j])

pos = 0
for queue in radix_queue:
for val in queue:
data[pos] = val
pos += 1

dev *= 10
mod *= 10
return data

* Fighting Chang Laoshi * 153*[email protected]

** Reference Address

-

** Autumn Moon

* luj**[email protected]

Here's a Go implementation:

// Radix Sort
func RadixSort(arr []int) {
    // Calculate the longest number
    var (
        maxVal int
        maxLen int
    )
    for _, v := range arr {
        if maxVal < v {
            maxVal = v
        }
    }
    for maxVal > 0 {
        maxLen++
        maxVal /= 10
    }

    // Loop for data distribution and collection
    var (
        base    = 1           // Modulus base, initially 1, used to extract the value of the i+1th digit from the end, formula: v / base % 10
        buckets = [10][]int{} // Radix buckets, 10 in total
    )
    for i := 0; i < maxLen; i++ { // Traverse digits
        for _, v := range arr { // Traverse array
            d := v / base % 10                 // Value of the current digit
            buckets[d] = append(buckets[d], v) // Store in corresponding bucket
        }

        // Restore elements from buckets to arr
        idx := 0
        for x, bucket := range buckets {
            if len(bucket) == 0 {
                continue
            }

            for _, v := range bucket {
                arr[idx] = v
                idx++
            }

            // Clear the bucket
            buckets[x] = []int{}
        }

        base *= 10 // Base * 10
    }
}

** Autumn Moon

* luj**[email protected]

-

** Lemon Tea

* 150**[email protected]

Here's the Python implementation:

def radixSort(nums):
    """
    Radix Sort, array elements must be positive integers
    >>> nums = [334, 5, 67, 345, 7, 99, 4, 23, 78, 45, 1, 3453, 23424]
    >>> radixSort(nums)
    >>> [1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424]
    """
    # Traverse the array to get the maximum value and its digit length
    maxValue = nums[0]
    for n in nums:
        maxValue = max(n, maxValue)
    # Iteration count
    iterCount = len(str(maxValue))
    for i in range(iterCount):
        # Define buckets, size 10, corresponding to 0-9
        bucket = [[] for _ in range(10)]
        for n in nums:
            index = (n // 10**i) % 10
            bucket[index].append(n)
        # Clear the nums array and merge elements from buckets into nums
        nums.clear()
        for b in bucket:
            nums.extend(b)
        print(nums)
    return nums

nums = [334, 5, 67, 345, 7, 99, 4, 23, 78, 45, 1, 3453, 23424]
radixSort(nums)

** Lemon Tea

* 150**[email protected]

-

** Stroll with Fragrance

* she**[email protected]

The above Java version has some issues:

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    // Considering negative numbers, the queue size is doubled, where [0-9] corresponds to negative numbers and [10-19] to positive numbers (bucket + 10)
    int[][] counter = new int[mod * 2][0];
....
}

The definition of the counter array will become larger as mod multiplies by 10. Theoretically, the counter array only needs a capacity of 20 to represent all digit characters of negative and positive numbers.

Additionally, the method getMaxDigit calculates the maximum length of the number, only considering the length of the maximum value, without considering that the character length of the minimum negative value could also be the maximum length.

Updated version:

/** Radix Sort */
public class RadixSort {

  public int[] sort(int[] arr) {
    int maxDigit = getMaxDigit(arr);
    return radixSort(arr, maxDigit);
  }

  /** Get the highest digit */
  private int getMaxDigit(int[] arr) {
    int maxValue = getMaxValue(arr);
    int minValue = getMinValue(arr);
    return Math.max(getNumLength(maxValue), getNumLength(minValue));
  }

  private int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
      if (maxValue < value) {
        maxValue = value;
      }
    }
    return maxValue;
  }

  private int getMinValue(int[] arr) {
    int minValue = arr[0];
    for (int value : arr) {
      if (minValue > value) {
        minValue = value;
      }
    }
    return minValue;
  }

  protected int getNumLength(long num) {
    if (num == 0) {
      return 1;
    }
    int lenght = 0;
    for (long temp = num; temp != 0; temp /= 10) {
      lenght++;
    }
    return lenght;
  }

  private int[] radixSort(int[] arr, int maxDigit) {
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
      // Considering negative numbers, the queue size is doubled, where [0-9] corresponds to negative numbers and [10-19] to positive numbers (bucket + 10)
      int[][] counter = new int[20][0];

      for (int j = 0; j < arr.length; j++) {
        int bucket = ((arr[j] % mod) / dev) + 10;
        counter[bucket] = arrayAppend(counter[bucket], arr[j]);
      }

      int pos = 0;
      for (int[] bucket : counter) {
        for (int value : bucket) {
          arr[pos++] = value;
        }
      }
    }

    return arr;
  }

  /** Auto-resize and save data */
  private int[] arrayAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
  }
}

** Stroll with Fragrance

* she**[email protected]

** Click to Share Notes

Cancel

-

-

-

• 1.0 Ten Classic Sorting Algorithms
• 1.1 Bubble Sort
• 1.2 Selection Sort
• 1.3 Insertion Sort
• 1.4 Shell Sort
• 1.5 Merge Sort
• 1.6 Quick Sort
• 1.7 Heap Sort
• 1.8 Counting Sort
• 1.9 Bucket Sort
• 1.10 Radix Sort

Follow on WeChat

English: