Counting Sort

Definition

Definition

Counting Sort is a non-comparative sorting algorithm that sorts elements by counting the number of occurrences of each unique element in the input array. It operates on integer arrays with a defined range of values

Explanation

The algorithm begins by tallying the occurrences of each distinct element within the input array. These counts are then utilized to ascertain the respective positions of the elements within the sorted output array. Finally, the sorted array is assembled using the counts and positions obtained in the previous step

Guidance

• Initialize an auxiliary array, to store the count of each unique element
• Traverse the input array, and increment the corresponding count in count array for each element encountered
• Modify the count array to contain the actual position of each element in the sorted array
• Iterate through the count array to construct the sorted array, by placing each element from the input array into its correct position based on the counts

Tips

• counting Sort is most efficient when the range of input elements is not significantly greater than the number of elements to be sorted
• ensure the input array contains only non-negative integers or modify the algorithm accordingly if negative integers are present

Practice

Practice

counting_sort(arr[], size, max_val):
  // Initialize count array with zeros
  for i = 0 to max_val:
    count[i] = 0

  // Count occurrences of each element
  for i = 0 to size:
    count[arr[i]]++

  // Modify count array to contain actual position
  for i = 1 to max_val:
    count[i] += count[i - 1]

  // Build the sorted array
  for i = size - 1 downto 0:
    sorted[count[arr[i]] - 1] = arr[i]
    count[arr[i]]--

  // Copy sorted array to original array
  for i = 0 to size:
    arr[i] = sorted[i]

Solution

func countingSort(arr []int, max int) []int {
    count := make([]int, max+1)
    sorted := make([]int, len(arr))

    for _, num := range arr {
        count[num]++
    }

    index := 0
    for i := 0; i <= max; i++ {
        for count[i] > 0 {
            sorted[index] = i
            index++
            count[i]--
        }
    }

    return sorted
}

public class CountingSort {

  public static int[] countingSort(int[] arr, int max) {
    int[] count = new int[max + 1];
    int[] sorted = new int[arr.length];

    for (int num : arr) {
      count[num]++;
    }

    int index = 0;
    for (int i = 0; i <= max; i++) {
      while (count[i] > 0) {
        sorted[index] = i;
        index++;
        count[i]--;
      }
    }

    return sorted;
  }
}

function countingSort(arr, max) {
  const count = new Array(max + 1).fill(0);
  const sorted = [];

  arr.forEach((num) => count[num]++);

  let index = 0;
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      sorted[index++] = i;
      count[i]--;
    }
  }

  return sorted;
}

fun countingSort(arr: IntArray, max: Int): IntArray {
    val count = IntArray(max + 1)
    val sorted = IntArray(arr.size)

    arr.forEach { num -> count[num]++ }

    var index = 0
    for (i in 0..max) {
        while (count[i] > 0) {
            sorted[index++] = i
            count[i]--
        }
    }

    return sorted
}

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    sorted_arr = []

    for num in arr:
        count[num] += 1

    for i in range(max_val + 1):
        sorted_arr.extend([i] * count[i])

    return sorted_arr

fn counting_sort(arr: &[usize], max: usize) -> Vec<usize> {
    let mut count = vec![0; max + 1];
    let mut sorted = vec![0; arr.len()];

    for &num in arr {
        count[num] += 1;
    }

    let mut index = 0;
    for i in 0..=max {
        while count[i] > 0 {
            sorted[index] = i;
            index += 1;
            count[i] -= 1;
        }
    }

    sorted
}

function countingSort(arr: number[], max: number): number[] {
  const count: number[] = new Array(max + 1).fill(0);
  const sorted: number[] = [];

  arr.forEach((num) => count[num]++);

  let index = 0;
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      sorted[index++] = i;
      count[i]--;
    }
  }

  return sorted;
}