MHB Function of Algorithms: Count & Sort

[evinda]

Hello! (Wave)

Could you explain me the function of the following two algorithms? (Thinking)

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);
}

 

[PvsNP]

Hello! (Wave)

Could you explain me the function of the following two algorithms? (Thinking)

What happens if you compile and run it? (Wasntme) Add output statements in between to keep track of what the algorithm is doing.

Given that the name of the function is "countSort", my guess is that it's probably related to: Counting sort - Wikipedia, the free encyclopedia

 

[evinda]

What happens if you compile and run it? (Wasntme) Add output statements in between to keep track of what the algorithm is doing.

Given that the name of the function is "countSort", my guess is that it's probably related to: Counting sort - Wikipedia, the free encyclopedia

I wanted to apply the algorithm at this array:

View attachment 3716

After calling the function [m] countSort(arr, n, 1) [/m], we get this:

View attachment 3717

When I call then the function [m] countSort(arr, n, n) [/m], at this for loop:

[m]for (i = n - 1; i >= 0; i--)
{
output[count[ (arr/exp)%n] - 1] = arr;
count[(arr/exp)%n]--;
}
[/m]I get [m] output[-1]=arr[4] [/m].

But the array doesn't have such a position... (Worried)

Have I done something wrong? (Sweating)

 

[evinda]

At the code, we count the number of occurences of each value and then the counts are accumulated..
How do we use the latter, in order to sort the array we are looking at?
I haven't understood the general idea...
Could you explain it to me? (Worried)