Non-Comparison Sorts (Radix, Counting - conceptual)

Non-Comparison Sorting Algorithms

So far, we've seen sorts that rely on comparing elements. But what if we could sort without comparisons? Non-comparison sorts like Counting Sort and Radix Sort do just that. They leverage the internal structure of the data (e.g., integer values) to sort in linear time, which is faster than the O(N log N) limit of comparison-based sorts.

---

1. Counting Sort

Counting Sort is an efficient algorithm for sorting a collection of items that have keys in a specific, small range (e.g., integers from 0 to k).

• The Core Idea: It works by counting the number of occurrences of each distinct element in the input array. This count information is then used to place the elements directly into their correct sorted positions.

• The Algorithm Step-by-Step:

  1. Find the maximum element k in the input array.
  2. Create a count array of size k+1 and initialize it with zeros.
  3. Iterate through the input array and for each element, increment its corresponding count in the count array.
  4. Modify the count array to store the cumulative sum of counts. This now represents the correct position for each element in the output array.
  5. Build the output array by iterating through the input array in reverse (to maintain stability) and placing each element in its sorted position using the count array.

• Implementation:

  function countingSort(arr, max) {
    const count = Array(max + 1).fill(0);
    const output = Array(arr.length);
  
    // Count occurrences of each element
    for (let i = 0; i < arr.length; i++) {
      count[arr[i]]++;
    }
  
    // Calculate cumulative counts
    for (let i = 1; i <= max; i++) {
      count[i] += count[i - 1];
    }
  
    // Build the output array
    for (let i = arr.length - 1; i >= 0; i--) {
      output[count[arr[i]] - 1] = arr[i];
      count[arr[i]]--;
    }
  
    return output;
  }
  

• Complexity:

  • Time: O(N + K), where N is the number of elements and K is the range of the input.
  • Space: O(N + K).

---

2. Radix Sort

Radix Sort is a non-comparison sorting algorithm that sorts integers by processing individual digits. It can process digits from the least significant digit (LSD) to the most significant digit (MSD), or vice-versa.

• The Core Idea: It sorts the list of numbers digit by digit. For each digit, it uses a stable sorting algorithm (like Counting Sort) to sort the numbers based on that digit.

• The Algorithm Step-by-Step (LSD Radix Sort):

  1. Find the maximum number in the array to determine the number of digits.
  2. For each digit, from the least significant to the most significant:
     • Sort the entire array using a stable sorting algorithm (like Counting Sort) based on the current digit.

• Implementation:

  // This implementation uses Counting Sort as a subroutine
  function radixSort(arr) {
    const max = Math.max(...arr);
  
    // Do counting sort for every digit. Note that instead of passing digit number,
    // exp is passed. exp is 10^i where i is current digit number.
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
      arr = countingSortByDigit(arr, exp);
    }
    return arr;
  }
  
  function countingSortByDigit(arr, exp) {
    const output = Array(arr.length);
    const count = Array(10).fill(0);
  
    for (let i = 0; i < arr.length; i++) {
      const digit = Math.floor(arr[i] / exp) % 10;
      count[digit]++;
    }
  
    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }
  
    for (let i = arr.length - 1; i >= 0; i--) {
      const digit = Math.floor(arr[i] / exp) % 10;
      output[count[digit] - 1] = arr[i];
      count[digit]--;
    }
  
    return output;
  }
  

• Complexity:

  • Time: O(d * (N + K)), where d is the number of digits in the maximum number, N is the number of elements, and K is the base of the number system (e.g., 10 for decimal).
  • Space: O(N + K).

---

Key Takeaway: Non-comparison sorts can break the O(N log N) barrier by making assumptions about the data. Counting Sort is extremely fast for small integer ranges, and Radix Sort extends this capability to handle larger integers by sorting them digit by digit.