coderz.py

What is Radix Sort?

Radix sort is an integer-based linear sorting method that groups items depending on their location or radix. It sorts the components in each iteration by the value of the digit at the current place, from least significant to most significant.

Algorithm:

The steps involved in radix sort are:

1. Find the maximum element in the array and determine the number of digits in it.
2. For each digit position, from the least significant to the most significant, do the following:
   • a. Group the elements based on the digit in the current position.
   • b. Sort the elements in each group based on the value of the digit in the current position.
   • c. Merge the groups back into a single array.
3. After all digit positions have been processed, the array is sorted.

Time Complexity:

• Worst case: O(nk)
• Best case: Ω(nk)
• Average case: Θ(nk)

where, n is the number of elements to be sorted, and k is the maximum number of digits or characters in the input.

Implementation of the algorithm in Java:

public static void radixSort(int[] arr) {
    int n = arr.length;
    int maxVal = getMaxValue(arr);
    
    // Perform counting sort for each digit position
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

private static int getMaxValue(int[] arr) {
    int maxVal = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}

private static void countingSort(int[] arr, int n, int exp) {
    int[] count = new int[10];
    int[] output = new int[n];
    
    // Count the number of occurrences of each digit
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }
    
    // Calculate the prefix sum of count array
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // Build the output array by placing elements in their sorted positions
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    // Copy the output array to the input array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

The primary driver function that performs radix sort on the input array is the radixSort method. It first uses the getMaxValue to discover the largest value in the array, and then does a counting sort for each digit position, beginning with the least significant digit and progressing to the most significant digit. The countingSort method is a helper function that performs counting sort on the input array for a specific digit position specified by the exp parameter.

Problems based on Radix sort:

• Given an array of integers, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example:

Input: array = {455, 61, 63, 45, 67, 135, 74, 49, 15, 5}
Output: 5 15 45 49 61 63 67 74 135 455
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Solution:

import java.util.Arrays;

public class RadixSort {
    public static void countingSort(int[] array, int sizeArray, int placeValue) {
        final int base = 10;
        int[] sortedArray = new int[sizeArray];

        int[] count = new int[base];

        for (int i = 0; i < sizeArray; i++) {
            int digitAtPlaceValue = (array[i] / placeValue) % base;
            count[digitAtPlaceValue]++;
        }

        for (int i = 1; i < base; i++) {
            count[i] += count[i - 1];
        }

        for (int i = sizeArray - 1; i >= 0; i--) {
            int digitAtPlaceValue = (array[i] / placeValue) % base;
            int sortedIndex = count[digitAtPlaceValue] - 1;
            sortedArray[sortedIndex] = array[i];
            count[digitAtPlaceValue]--;
        }

        for (int i = 0; i < sizeArray; i++) {
            array[i] = sortedArray[i];
        }
    }

    public static void radixSort(int[] array, int sizeArray) {
        int maxim = Arrays.stream(array).max().getAsInt();

        for (int placeValue = 1; maxim / placeValue > 0; placeValue *= 10) {
            countingSort(array, sizeArray, placeValue);
        }
    }

    public static void main(String[] args) {
        int[] array = {455, 61, 63, 45, 67, 135, 74, 49, 15, 5};
        int sizeArray = array.length;

        radixSort(array, sizeArray);

        for (int i = 0; i < sizeArray; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

The radixSort function first finds the maximum value in the array using Arrays.stream(array).max().getAsInt() to determine the number of digits in the largest element, which will be used to determine the number of iterations of the countingSort function. countingSort takes three arguments: the unsorted array, its length, and the place value that represents the current digit being sorted sorts the array based on the digit at the current place value, using the Counting Sort algorithm.

Note: also read about Heap Sort

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py