Radix Sort with a mix of positive and negative integers without added time complexity.

#radix_sort

One of the beautiful things about Radix Sort is that of the basic sorting algorithms it sits on the low end of Big O. Generally speaking, its time complexity in both the best and worst case scenarios is O(nk), where n is the size of the array and k is the amount of digits in the array’s largest integer. It keeps the time complexity low because the algorithm avoids any direct comparison between any of the components of the array and therefore removes the need for any nested loops. The most basic description I can give of radix sort is that it continually groups the contents of the array into 10 “buckets” according to the integer’s last digit according to the loop that it is currently in. There are plenty of resources on the web that can give a more complete description both verbally and graphically. My purpose here, however, is to try to solve the issue of attempting to use radix sort on an array that contains a mix of positive and negative integers.

I probably wouldn’t have felt the need to address this issue except that much of the material I read on the internet while attempting to learn how to create and implement radix sort would specifically state, “can be used with both positive and negative integers.” They would then leave a formula that would only sort arrays with positive OR negative integers, but would produce a faulty result when trying to mix the integers. I wasted a lot of time thinking that there was something wrong with my code, my computer, even myself before I realized that I was being misled. I decided to redress this with my own code that would also not spoil the great O(nk) time complexity that makes radix sort so desirable in the first place. I did this in both JavaScript and Ruby. Since I don’t see algorithms of this sort printed in Ruby much, I go through the Ruby version here.

In order to get radix sort to function correctly, it is general practice to create a few helper methods first, and that’s what we’ll do here. Since this algorithm relies on looping x amount of times through the array, and x = the amount of digits in the largest integer of the array, we need a method that returns the amount of digits in the largest integer. However, we need to accomplish this without relying on direct comparisons of the contents of the array or else with destroy the time complexity benefit of radix sort. Therefore, the way we are going to do this is to break the method into two smaller methods, one that just uses a math formula to return to us the amount of digits that are in an integer passed to it, and one to run that method through each integer in the array once and only once, which will return the answer as to how many times we need to loop through the array.

The mathematical formula to return the amount of digits contained in an integer (in the common base 10 system) is log10(n)+1.

def digit_count(n)   if n == 0      return 1   end return (Math.log10(n.abs)).floor()+1end

We can now loop through out array once, storing a maximum value of the return of digit_count, and then comparing each number in the unsorted array to the stored maximum value and return the maximum value at the end.

def most_digits(arr)   max = 0   arr.each do |value|     if (digit_count(value) > max)       max = digit_count(value)     end   end return maxend

Next, we need a helper method to return the value of the digit to the Nth place of the integer. There is also a mathematical formula for this, so we can avoid having to convert the integer to a string. The remainder (modulo) of an integer when the integer is divided by 10 will return the last digit of a number. For instance, the remainder of 123456 divided by ten is 6. But we’re going to need every digit in the integer at some point. No problem, we’ll just loop through the integer the amount of times for the place to the left of the last digit and continually divide the integer by 10 until we’re at the place we need, then take that number and get the remainder once divided again by 10.

def get_digit(num, place)   num = num.abs()   i = place   while i>1 do     num = num / 10     i -= 1   end return num % 10end

We are now ready to run our generic radix sort. Notice that we use Array.new(10).map {|e| []} to create an empty array [] of ten empty arrays [ [], [], [], … [] ]. This is our “bucket” of arrays. Also, the return of each loop uses Ruby’s “splat” operator, which functions like JavaScript’s spread […] operator.

def radix_sort(arr)
loop = most_digits(arr)
i = 0
while i<loop do
bucket = Array.new(10).map{ |e| [] }
j = 0
while j<arr.length do
final_number = get_digit(arr[j], i)
bucket[final_number].push(arr[j])
j += 1
end
arr = [].concat(*bucket)
i += 1
end
return arr
end

Run this an you’ll see it works. However, run this with an array like [1,8,44, -3, 11] and you’ll see that the -3 in not in the correct spot. What can be done about this without increasing the time complexity logarithmically or exponentially? We’re going to create a couple of more helper methods and conditionals that will at most only run through the array once or less.

Logically, the first one we should create is to check whether the array passed into the radix sort function has a mix of both positive and negative numbers. And to reduce the time it takes to do this, return true once it encounters a mix.

def contains_mixed(arr)
positive = 0
negative = 0
for a in arr do
if a>=0
positive += 1
else
negative += 1
end
if positive>0 && negative >0
return true
break
end
end
return false
end

If we do encounter a mixed array, the best thing to do is to split the array into two separate arrays and deal with them individually.

def split(arr)
positive = []
negative = []
for a in arr do
if a>=0
positive.push(a)
else
negative.push(a)
end
end
return [positive, negative]
end

But how should we deal with this in our code if there is a mix without creating additional logic, conditionals, and redundant code? We’ll just call #radix_sort recursively.

def radix_sort(arr)
if contains_mixed(arr)
mixed_array = split(arr)
positive = radix_sort(mixed_array[0])
negative = radix_sort(mixed_array[1])
return negative.concat(positive)

However, another issue arises here: You’ll see that the negative numbers are not in the order that we’d like. The return would be something like: [-4, -66, -999, 1, 16, 44, 987]. This is not technicality correct. So, once again, how do we order the negative integers here before combining it with the positive integers without greatly increasing the time complexity? We can just use a common swap algorithm which swaps the first and last item of an array n/2 times. And with that, we finally have our radix sort algorithm in Ruby which returns a correctly sorted algorithm of integers whether it contains negative integers, positive integers, or a mix of the two, and without increasing Big O logarithmically nor exponentially.

def radix_sort(arr)
if contains_mixed(arr)
mixed_array = split(arr)
positive = radix_sort(mixed_array[0])
negative = radix_sort(mixed_array[1])
left = 0
right = negative.length-1
while left<right do
temp = negative[left]
negative[left] = negative[right]
negative[right] = temp
left += 1
right -= 1
end
return negative.concat(positive)
end
loop = most_digits(arr)
i = 0
while i<loop do
bucket = Array.new(10).map{ |e| [] }
j = 0
while j<arr.length do
final_number = get_digit(arr[j], i)
bucket[final_number].push(arr[j])
j += 1
end
arr = [].concat(*bucket)
i += 1
end
return arr
end

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store