How to Implement Counting Sort in Ruby

There are various ways to sort data in computer programming: bubble sort, quick sort, merge sort. Another method, which I recently learned about, is counting sort. This method is useful when the data you’re sorting has a relatively small range of values between the minimum and maximum – for instance, if you’re sorting individual letters or individual digits. There are only 26 digits – not a very large range. For large data sets of this type, counting sort can be faster than merge sort.

Here’s a visualization of counting sort. Here are the steps, which are kind of hard to understand without the visualization:

(1) Create an empty array of n elements, where n is the range of possible values. If we’re sorting letters, we create an empty array with a length of 26 (lowest index is 0, highest index is 25).

(2) Into each space in the empty array, put the total number of that element that exists in the original unsorted list. For instance, suppose the original unsorted list contains 3 g‘s. Since g is the 7th letter of the alphabet, the seventh index of the array – array[6] – should be assigned the value 3.

(3) Take this newly-populated array. Starting from the beginning, add the value of each index to the value of the index after it. If you do this correctly, the last index of the array will contain the number of all elements in the unsorted list. (This is easier to understand if you look at the visualization linked above.)

(4) Finally, create another empty array the same length as the number of elements in the original unsorted list. Then, for each value in the original unsorted list, find the element in the array that has that index value. Confusing? In other words, if a value in the original unsorted list is the letter g, go to array[6].

Then reduce that value by 1. Next, whatever value array[6] holds, go to the new array at new_array[that_value]. For instance, if array[6] contains 4, reduce it to 3, then go to new_array[3].

Now, assign new_array[3] the value 6.

Do that for every element in the original unsorted list, and you will now have an array containing all the elements, sorted.

Here’s how I implemented counting sort in Ruby, where init_string is the original unsorted data. I created a key array to use to convert letters to their numerical equivalents.

key = "abcdefghijklmnopqrstuvwxyz".split("")

init_string = "zyxwvutdcba"

init_array = init_string.split("")

mid_array = Array.new(26, 0)   #[0,0,0,0,0,0...]
final_array = Array.new(init_array.length, 0)   #[0,0,0,0,0,0...]

# put each character in the array at its proper index
init_array.each do |letter|
  i = key.index(letter)
  mid_array[i] += 1
end

# increment each value in the array by the sum of the number before it
mid_array.each_with_index do |value, index|
  mid_array[index] = mid_array[index-1] + mid_array[index] if index > 0
end

# for each value in init_array:
init_array.each do |value|
  # take the value (init_array[i])
  i = key.index(value)
  # find the value in mid_array that has the index of that first value; decrement that value in mid_array by 1
  mid_array[i] -= 1
  final_index = mid_array[i]
  # go to final_array with the index of that new decremented value; put the initial value there
  final_array[final_index] = value
end

final_array = final_array.join

print final_array

Leave a Reply

Your email address will not be published. Required fields are marked *