Counting Sort array values aren't changing

Question

I am trying to implement the counting sort algorithm. Based on the pseudocode from Introduction to Algorithms (and if you don't know it it's just a book), I came up with this code:

var countingSort = function(array, array2, k){
    var a = [];
    a.length = k;
    for(var i in a){
        a[i] = 0;
    }
    for(var j in array){
        a[array[j]] += 1;
    }
    for(var i in a){
        a[i] += a[i - 1];
    }
    for(var j = array.length; j >= 0; j--){
        array2[a[array[j]]] = array[j];
        a[array[j]] -= 1;
    }
};

When I use the function, however, my array stays the same (I put in all the arguments!) How to fix this? Can someone please explain what is going on?

Answer 1

First of all, you shouldn't use a for in loop in short because it doesn't only iterate over the elements in the array but also over all the properties on the of Array object. Here's more info

In you case, a simple for loop would suffice.

Further, you should use descriptive names so that you (now or when you are looking at the code later on) or somebody else can understand the code more clearly.

I assume the variables in your program mean the following:

1. array stores the initial data to be sorted.
2. array2 stores the final, sorted list.
3. k is the max value in the array (all values are in the range 0..k)
4. a is the array used to count unique occurrences of values in array

These can be renamed into something like:

1. This one is fine as array
2. array2 can be renamed to sorted
3. k can be renamed to max
4. a can be renamed to count

Another thing you are doing wrong is in the last for loop. You are starting the loop at array.length but arrays are 0-indexed in javascript so your first value is out-of-bounds. You should start from array.length - 1.

And as far as setting a.length = k, this is not necessary in javascript because arrays are objects and objects have no direct concept of length. You can view arrays in javascript as dynamic lists.

Adding all the stated changes, here is how your code could look like:

function countingSort(array, sorted, max){
    var i, j;

    var count = [];

    // initialize counting array
    for(i = 0; i <= max; i++){
        count[i] = 0;
    }

    // count unique occurrences
    for(i = 0; i <= max; i++){
        count[array[i]] += 1;
    }

    // compute proper indices
    for(i = 1; i <= max; i++){
        count[i] += count[i - 1];
    }

    // sort
    for(i = array.length - 1; i >= 0; i--){
        sorted[count[array[i]] - 1] = array[i];
        count[array[i]] -= 1;
    }
}

Running example:

var countingSort = function(array, sorted, max) {
  var i, j;

  var count = [];

  // initialize counting array
  for (i = 0; i <= max; i++) {
    count[i] = 0;
  }

  // count unique occurrences
  for (i = 0; i <= max; i++) {
    count[array[i]] += 1;
  }

  // compute proper indices
  for (i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // sort
  for (i = array.length - 1; i >= 0; i--) {
    sorted[count[array[i]] - 1] = array[i];
    count[array[i]] -= 1;
  }
}

document.getElementById("button").onclick = function() {
  var i, array, max, sorted = [];

  array = document.getElementById("input").value.split(',');
  // convert strings to numbers
  for (i = 0; i < array.length; i++) {
    array[i] = +array[i];
  }
  // find max
  var max = Number.MIN_VALUE;
  for (i = 0; i < array.length; i++) {
    if (max < array[i]) {
      max = array[i];
    }
  }
  countingSort(array, sorted, max);
  document.getElementById("result").value = sorted;
}

input {
  width: 100%;  
  margin: 10px 0;
  padding: 10px;
  border: 1px solid #018bbc;
  border-radius: 5px;  
}

<input type="text" id="input" placeholder="Enter comma separated list of integers">
<button type="button" id="button">Sort</button>
<input type="text" id="result" disabled placeholder="Sorted array is displayed here...">

---

Additionally, here is a version of counting sort which IMHO seems more intuitive and less complicated than the general approach above:

var countingSort = function(array, sorted, max) {
  var i, j, count = [];

  // initialize counting array
  for (i = 0; i <= max; i++) {
    count[i] = 0;
  }

  // count unique occurences
  for (i = 0; i < array.length; i++) {
    count[array[i]] ++;
  }

  // sort
  for (i = 0, j = 0; i <= max; i++) {
    while (count[i] > 0) {
      sorted[j++] = i;
      count[i] --;
    }
  }
};