Radix Sort

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Radix Sort Overview

History

Radix sort was developed in the 1960s and is a non-comparison-based sorting algorithm. It sorts numbers by processing individual digits. Radix sort is efficient for sorting large sets of integers and has been utilized in various applications.

Current Uses

Large Integer Sets: Commonly used to sort large datasets of integers.
Specific Applications: Utilized in applications that require sorting of fixed-length strings or numbers.
Counting Sort Combination: Often used in combination with counting sort for efficiency.

Time and Space Complexity

Time Complexity

Best Case: O(nk) – Where n is the number of elements and k is the number of digits in the largest number.
Average Case: O(nk) – Efficiency depends on the number of digits.
Worst Case: O(nk) – Same as the average case.

Space Complexity

Space Complexity: O(n + k) – Requires additional space for the output array and counting array.

Pseudo Code

function radixSort(array)
    maxNumber = findMax(array)
    numberOfDigits = countDigits(maxNumber)
    
    for digit in 1 to numberOfDigits do
        applyCountingSort(array, digit)
    end for
end function

function applyCountingSort(array, digitPosition)
    create 10 buckets to represent each digit (0 to 9)
    
    for each element in array do
        digit = getDigit(element, digitPosition)
        place element into corresponding bucket based on digit
    end for
    
    merge all buckets in order to form the sorted array for this digit position
end function

function getDigit(number, position)
    return (number / 10^(position - 1)) % 10
end function

function findMax(array)
    maxNumber = array[0]
    for i = 1 to array.length - 1 do
        if array[i] > maxNumber then
            maxNumber = array[i]
        end if
    end for
    return maxNumber
end function

function countDigits(number)
    count = 0
    while number > 0 do
        number = number / 10
        count = count + 1
    end while
    return count
end function

Key Characteristics

Non-Comparison Sort: Radix sort does not compare elements directly.
Stable: Radix sort can be implemented as a stable sorting algorithm.

Summary

Radix sort is an efficient non-comparison sorting algorithm that processes individual digits to sort integers. Its time complexity of O(nk) makes it suitable for sorting large sets of data, particularly when the range of digits is small.

Radix Sort Code Implementation