Counting Sort Visualization in JavaScript

Sorting algorithms are the backbone of computer science, helping us organize data efficiently. Counting Sort is a non-comparison-based algorithm with linear time complexity in certain cases. While its implementation might seem complex, visualizing it can make the concept much clearer. In this post, we’ll explore how to implement and visualize Counting Sort using JavaScript.

What is Counting Sort?

Counting Sort is an integer sorting algorithm that sorts by counting the frequency of each element. Instead of comparing elements directly, it uses a counting array to store the frequency of each unique value.

Algorithm Steps:

1. Count the occurrences of each element in the array and store them in a counting array.
2. Modify the counting array to store cumulative sums.
3. Use the counting array to place elements in their correct positions in the sorted array.

Code Walkthrough

Below is an interactive Counting Sort implementation in JavaScript, designed to visualize the sorting process.

Features of the Visualization

1. Interactive UI:
   • The array visualization updates dynamically as elements are sorted.
   • A slider adjusts the speed of the sorting process.
2. Custom Visualization:
   • Elements are represented as colored bars or blocks.
   • Counting and placement are visualized step-by-step.
3. Asynchronous Execution: The use of await and async allows the sorting process to pause for visualization.

Core Functions

1. countSortSwap This function increments the count of an element in the visualization and shifts its position temporarily.

const countSortSwap = (arrayCount, divContainer, numArray2, j, l, k) => {
  divContainer[l].style.transform = `translate(${numArray2[k][2]}px, 145px)`;
  let count = Number(arrayCount[k].innerHTML) + 1;
  arrayCount[k].innerHTML = count;
};

2. countSortAns This function places sorted elements in their final positions and adjusts the count accordingly.

const countSortAns = (arrayCount, divContainer, numArray2, j, l) => {
  divContainer[l].style.order = numArray2[incrementar][1];
  divContainer[l].style.transform = `translate(${numArray2[incrementar++][2]}px, 0px)`;
  let count = Number(arrayCount[j].innerHTML) - 1;
  arrayCount[j].innerHTML = count;
  setColor(divContainer[l], "#9eff9e");
};

3. countingSort The main function orchestrates the sorting and visualization process.

Visualization Process

1. Initial Setup Elements are represented as div blocks with specific order and transform styles, which simulate their positions on the screen.

if (numArray.length % 2 === 0) {
  gapLenth = -(j * 100 + 50);
} else {
  gapLenth = -(j * 100 + 100);
}

2. Counting Elements Each element is compared and its count is incremented, with the visualization updated in real-time.

for (let j = 0; j < numArray.length; j++) {
  l = 0;
  k = 0;
  while (divContainer.childNodes[l].style.order != numArray[j][1]) l++;
  while (numArray[j][0] != numArray2[k][0]) k++;
  countSortSwap(array_visualization_count.childNodes, divContainer.childNodes, numArray2, j, l, k);
}

3. Placing Sorted Elements Once counting is complete, elements are placed in their sorted positions based on the counting array.

for (let j = 0; j < numArray.length; j++) {
  let subLength = Number(array_visualization_count.childNodes[j].innerHTML);
  l = -1;
  while (subLength--) {
    l++;
    while (numArray[u][0] != numArray2[j][0]) u++;
    countSortAns(array_visualization_count.childNodes, divContainer.childNodes, numArray2, j, l);
  }
}

Highlights

1. Real-Time Updates: The visualization updates dynamically with each comparison and placement.
2. Customizable Speed: The sorting speed is adjustable via a slider, making it easy to observe the process at different paces.
3. Interactive Design: Bars or blocks represent elements, making it intuitive for users to follow the algorithm’s steps.

Conclusion

Counting Sort’s unique approach to sorting makes it an exciting algorithm to visualize. By combining JavaScript, asynchronous programming, and dynamic styling, we’ve created an interactive and educational visualization tool. This implementation not only demonstrates the algorithm but also makes it accessible for learners.

Try It Yourself!

Copy the code and integrate it into your project to see Counting Sort in action. Experiment with different array sizes and visualization styles to deepen your understanding.