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)

 

[LudusRex]

The function of these two algorithms is to count and sort a given array of elements. The first algorithm, countSort, uses a counting technique to determine the number of occurrences of each element in the array and then rearranges the elements in the output array based on their count. This allows for a more efficient sorting process.

The second algorithm, sort, utilizes the countSort algorithm twice, first to sort the elements based on their least significant digit and then again based on their most significant digit. This is known as radix sorting and it allows for a more efficient sorting process for arrays with large numbers.

Overall, the function of these algorithms is to efficiently sort a given array of elements by counting their occurrences and rearranging them in ascending order. This can be useful in various applications, such as organizing data or finding the most frequent elements in a dataset.