Radix Sort

Definition

Definition

Radix Sort is a non-comparative sorting algorithm that sorts integers by grouping them based on individual digits or radix (base). It works by iterating through each digit of the numbers, starting from the least significant digit (rightmost) to the most significant digit (leftmost). Radix Sort can be implemented using different approaches like LSD (Least Significant Digit) or MSD (Most Significant Digit)

Explanation

Radix Sort sorts numbers by placing them into buckets based on the value of their digits at a specific position. It starts from the least significant digit, placing each number into its respective bucket based on that digit. Then, it gathers the numbers from the buckets and repeats the process for the next significant digit until all digits have been considered. This process sorts the numbers effectively, as at each iteration, the numbers are arranged based on increasingly significant digits, leading to the final sorted sequence

Guidance

• Identify the maximum number of digits in the given list of integers to determine the number of iterations required
  • start from the least significant digit and iterate through each digit position
  • for each iteration, create buckets for each digit (0-9)
  • iterate through the list of integers and place each number into the corresponding bucket based on the digit at the current position
  • gather the numbers from the buckets in the order they were placed and overwrite the original list with the sorted sequence
  • repeat steps for each digit position until all digits have been considered

Tips

• ensure proper handling of negative numbers and zero-padding to maintain the significance of digits
• choose the appropriate approach (LSD or MSD) based on the characteristics of the data to optimize performance
• implement efficient bucketing and gathering strategies to minimize overhead
• consider the range of integers in the input data to optimize bucket sizes and reduce memory consumption

Practice

Practice

radix_sort(arr):
  max_digit = getMax(arr)
  exp = 1
  while max_digit // exp > 0:
    counting_sort(arr, exp)
    exp *= 10

counting_sort(arr, exp):
  n = len(arr)
  output = [0] * n
  count = [0] * 10

  for i in range(n):
    index = arr[i] // exp % 10
    count[index] += 1

  for i in range(1, 10):
    count[i] += count[i - 1]

  i = n - 1
  while i >= 0:
    index = arr[i] // exp % 10
    output[count[index] - 1] = arr[i]
    count[index] -= 1
    i -= 1

  for i in range(n):
    arr[i] = output[i]

getMax(arr):
  max_num = max(arr)
  max_digit = len(str(max_num))
  return max_digit

Solution

package main

import (
    "strconv"
)

func getMax(arr []int) int {
    max := arr[0]
    for _, val := range arr {
        if val > max {
            max = val
        }
    }
    return max
}

func countSort(arr []int, exp int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10)

    for i := 0; i < n; i++ {
        count[(arr[i]/exp)%10]++
    }

    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }

    for i := n - 1; i >= 0; i-- {
        output[count[(arr[i]/exp)%10]-1] = arr[i]
        count[(arr[i]/exp)%10]--
    }

    for i := 0; i < n; i++ {
        arr[i] = output[i]
    }
}

func radixSort(arr []int) {
    max := getMax(arr)
    for exp := 1; max/exp > 0; exp *= 10 {
        countSort(arr, exp)
    }
}

import java.util.Arrays;

public class RadixSort {

  public static void radixSort(int[] arr) {
    int max = getMax(arr);
    for (int exp = 1; max / exp > 0; exp *= 10) {
      countSort(arr, exp);
    }
  }

  private static void countSort(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int i = 0; i < n; i++) {
      count[(arr[i] / exp) % 10]++;
    }

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

    for (int i = n - 1; i >= 0; i--) {
      output[count[(arr[i] / exp) % 10] - 1] = arr[i];
      count[(arr[i] / exp) % 10]--;
    }

    System.arraycopy(output, 0, arr, 0, n);
  }

  private static int getMax(int[] arr) {
    int max = arr[0];
    for (int val : arr) {
      if (val > max) {
        max = val;
      }
    }
    return max;
  }
}

function getMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

function countSort(arr, exp) {
  const n = arr.length;
  const output = new Array(n).fill(0);
  const count = new Array(10).fill(0);

  for (let i = 0; i < n; i++) {
    count[Math.floor(arr[i] / exp) % 10]++;
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  for (let i = n - 1; i >= 0; i--) {
    output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
    count[Math.floor(arr[i] / exp) % 10]--;
  }

  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

function radixSort(arr) {
  const max = getMax(arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countSort(arr, exp);
  }
}

fun getMax(arr: IntArray): Int {
    var max = arr[0]
    for (i in 1 until arr.size) {
        if (arr[i] > max) {
            max = arr[i]
        }
    }
    return max
}

fun countSort(arr: IntArray, exp: Int) {
    val n = arr.size
    val output = IntArray(n)
    val count = IntArray(10)

    for (i in 0 until n) {
        count[arr[i] / exp % 10]++
    }

    for (i in 1 until 10) {
        count[i] += count[i - 1]
    }

    for (i in n - 1 downTo 0) {
        output[count[arr[i] / exp % 10] - 1] = arr[i]
        count[arr[i] / exp % 10]--
    }

    output.copyInto(arr)
}

fun radixSort(arr: IntArray) {
    val max = getMax(arr)
    var exp = 1
    while (max / exp > 0) {
        countSort(arr, exp)
        exp *= 10
    }
}

def getMax(arr):
    max_val = arr[0]
    for val in arr:
        if val > max_val:
            max_val = val
    return max_val

def countSort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        count[arr[i] // exp % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        output[count[arr[i] // exp % 10] - 1] = arr[i]
        count[arr[i] // exp % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radixSort(arr):
    max_val = getMax(arr)
    exp = 1
    while max_val // exp > 0:
        countSort(arr, exp)
        exp *= 10

fn get_max(arr: &Vec<u32>) -> u32 {
    let mut max = arr[0];
    for &val in arr.iter() {
        if val > max {
            max = val;
        }
    }
    max
}

fn count_sort(arr: &mut Vec<u32>, exp: u32) {
    let n = arr.len();
    let mut output = vec![0; n];
    let mut count = vec![0; 10];

    for &val in arr.iter() {
        count[((val / exp) % 10) as usize] += 1;
    }

    for i in 1..10 {
        count[i] += count[i - 1];
    }

    for &val in arr.iter().rev() {
        let index = ((val / exp) % 10) as usize;
        output[count[index] as usize - 1] = val;
        count[index] -= 1;
    }

    arr.copy_from_slice(&output);
}

fn radix_sort(arr: &mut Vec<u32>) {
    let max = get_max(arr);
    let mut exp = 1;
    while max / exp > 0 {
        count_sort(arr, exp);
        exp *= 10;
    }
}

function getMax(arr: number[]): number {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

function countSort(arr: number[], exp: number): void {
  const n = arr.length;
  const output: number[] = new Array(n).fill(0);
  const count: number[] = new Array(10).fill(0);

  for (let i = 0; i < n; i++) {
    count[Math.floor(arr[i] / exp) % 10]++;
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  for (let i = n - 1; i >= 0; i--) {
    output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
    count[Math.floor(arr[i] / exp) % 10]--;
  }

  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

function radixSort(arr: number[]): void {
  const max = getMax(arr);
  let exp = 1;
  while (Math.floor(max / exp) > 0) {
    countSort(arr, exp);
    exp *= 10;
  }
}