Tag: counting-sort

Counting Sort

Imagine having a box of mixed socks. Instead of painstakingly comparing each pair, Counting Sort counts the number of socks of each color, allowing you to instantly identify the most frequent (or least frequent) colors, creating order from chaos.

Process

Imagine a messy room overflowing with toys. While other sorting algorithms might meticulously compare each toy, Counting Sort takes a different approach: it counts! Yes, that’s right, it leverages the power of counting to bring order to chaos. Let’s delve into the steps:

1. Counting the Crew: First, Counting Sort creates a temporary array, one slot for each unique value (color, size, type) your toys might have. Then, it iterates through your room (data), patiently counting how many toys belong to each category (value). So, all the red cars get a tally in the “red car” slot, and so on.

2. Calculating Positions: With the popularity (count) of each value known, Counting Sort does some clever math. It calculates the starting position in the final sorted array for each value based on its count and the counts of previous values. Think of it as figuring out how much space each toy category deserves in the organized closet (final array).

3. Placing the Toys (Data): Finally, it’s time to put things away! Counting Sort goes back to your messy room (data) and visits each toy (element) one by one. Based on the toy’s value, it uses the calculated position from step 2 to place it in the correct spot in the final sorted array. It’s like having a map that tells you exactly where each toy belongs!

Pseudo Code

Code
function countingSort(array):
  # Find the maximum element in the array
  max_value = findMax(array)

  # Create a count array to store the frequency of each element
  count_array = [0] * (max_value + 1)

  # Count the occurrences of each element
  for i in range(len(array)):
    count_array[array[i]] += 1

  # Calculate the cumulative sum of the count array
  for i in range(1, len(count_array)):
    count_array[i] += count_array[i - 1]

  # Create the output array
  output_array = [0] * len(array)

  # Place elements in the output array based on their counts
  for i in range(len(array) - 1, -1, -1):
    output_array[count_array[array[i]] - 1] = array[i]
    count_array[array[i]] -= 1

  # Return the sorted array
  return output_array

# Function to find the maximum element
function findMax(array):
  max_value = array[0]
  for i in range(1, len(array)):
    if array[i] > max_value:
      max_value = array[i]
  return max_value
Explanation
  1. findMax: This function finds the maximum element in the array, which determines the size of the count_array.
  2. count_array: This array stores the count of each element. Each index represents a possible value, and the value at that index represents how many times that value appears in the original array.
  3. Counting occurrences: The loop iterates through the original array, incrementing the corresponding element in the count_array for each occurrence.
  4. Cumulative sum: This loop calculates the cumulative sum of the count_array. This means that each element at index i in the count_array now represents the starting position for elements with that value in the final sorted array.
  5. output_array: This is where the sorted elements will be placed.
  6. Placing elements: The loop iterates through the original array in reverse order. For each element, it uses its value to find its corresponding count in the count_array. This count indicates the correct position in the output_array, and the element is placed there. After placing, the count for that element is decremented to ensure correct placement of subsequent occurrences.
  7. Return: The sorted array is returned.

Implementation

Kotlin

Golang