Could you explain me how the following two algorithms work?
int countSort(int arr[], int n, int exp)
{
int output[n];
int i, count[n] ;
for (int i=0; i < n; i++)
count[i] = 0;
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%n ]++;
for (i = 1; i < n; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%n] - 1] = arr[i];
count[(arr[i]/exp)%n]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void sort(int arr[], int n)
{
countSort(arr, n, 1);
countSort(arr, n, n);
}
I wanted to apply the algorithm at this array:
After calling the function countSort(arr, n, 1) , we get this:
When I call then the function countSort(arr, n, n) , at this for loop:
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%n] - 1] = arr[i];
count[(arr[i]/exp)%n]--;
}
I get output[-1]=arr[4].
But the array doesn't have such a position...
Have I done something wrong?
EDIT:Considering the array arr[] = { 10, 6, 8, 2, 3 }, the array count will contain the following elements:
what do these numbers represent? How do we use them?
It took a bit of time to pick though your
countSort
routine and attempt to determine just what it was you were doing compared to a normalradix
sort. There are some versions that split the iteration and the actual sort routine which appears to be what you attempted using bothcountSort
andsort
functions. However, after going though that exercise, it was clear you had just missed including necessary parts of the sort routine. After fixing various compile/declaration issues in your original code, the following adds the pieces you overlooked.In your
countSort
function, the size of yourcount
array was wrong. It must be the size of thebase
, in this case10
. (you had5
) You confused the use ofexp
andbase
throughout the function. Theexp
variable steps through the powers of10
allowing you to get the value and position of each element in the array when combined with amodulo base
operation. You hadmodulo n
instead. This problem also permeated you loop ranges, where you had a number of your loop indexes iterating over0 < n
where the correct range was0 < base
.You missed finding the maximum value in the original array which is then used to limit the number of passes through the array to perform the sort. In fact all of your existing loops in
countSort
must fall within the outer-loop iteratingwhile (m / exp > 0)
. Lastly, you omitted a increment ofexp
within the outer-loop necessary to applying the sort to each element within the array. I guess you just got confused, but I commend your effort in attempting to rewrite the sort routine and not just copy/pasting from somewhere else. (you may have copied/pasted, but if that's the case, you have additional problems...)With each of those issues addressed, the sort works. Look though the changes and understand what it is doing. The
radix sort/count sort
aredistribution sorts
relying on where numbers occur and manipulating indexes rather than comparing values against one another which makes this type of sort awkward to understand at first. Let me know if you have any questions. I made attempts to preserve your naming convention throughout the function, with the addition of a couple that were omitted and to prevent hardcoding10
as the base.output: