1
$\begingroup$

So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm.

Now i find that solutions for that question given by my professors are wrong because they do gave this as answer:( pseudocode)

Sorting(A,k) //where k is a value inserted by the user(?)
{ 
max=a[0];
for i=1 to n // n=dim
{
    if( a[i] > max) update max with a[i]
}
if( max <= k*n) then countingsort(A)

else heapsort(A);

return A;

Now that being said, if k is really a value inserted by the user, this makes that solution not really case sensitive or a proper valuation of counting sort time complexity. It seems to me that it isnt a general algorithm, which should be instead the purpose of that exercise i guess. my solution is:

Sort(A){
    int max, i;
    int min;
    if( arr[0] > arr[1]){
        max=a[0];
        min=a[1];
    }

    for(i= 2 ; i < n ; i++){
        if(a[i] > max) max=arr[i];

        else if( a[i]< min) min=arr[i];
    }
    range= max-min; // range for counting sort
    if(range/n < log n) counting sort(A,range);

    else mergesort/heapsort(A......);

    return A;
    }

If (range/n) < logn , it means that range < nlogn, which implies it ""should"" be better than other optimal sorting algorithms. It might be not the most accurate way but it seems like it should be something like that, shouldnt it?

$\endgroup$
0

2 Answers 2

0
$\begingroup$

I wouldn’t be too happy with your professor’s solution. You noticed that it will refuse to do a very fast counting sort if all item are either nk+1 or nk+2. That’s bad. What is fatal is that it will always do a counting sort if the array elements are all negative. (Please don’t tell me that a sorting algorithm which can only handle positive numbers would ever be considered).

PS It seems there was an attempt to fix the code since I wrote my answer. As a result it became a lot worse since in half the cases min and max start out as being undefined. Plus memory used can be up to n log n.

$\endgroup$
3
  • 2
    $\begingroup$ since they are just learning, the point is to build the principal algorithm rather than to address all corner cases $\endgroup$
    – Bulat
    Commented Jul 9, 2019 at 16:11
  • 1
    $\begingroup$ Negative numbers are not a “corner case”. And good algorithms don’t have “corner cases”. $\endgroup$
    – gnasher729
    Commented Jul 10, 2019 at 3:32
  • $\begingroup$ by changing int to unsigned we can easily avoid working with negatives. But this cosmetical change will result only in more paper-writing. $\endgroup$
    – Bulat
    Commented Jul 10, 2019 at 8:39
0
$\begingroup$

The professor's solution differs from yours in an important way: it limits the memory size to $kn$, where $k$ is chosen by the user. Your solution does not offer this control and might lead to memory overflow.

$\endgroup$
2
  • $\begingroup$ On aother hand, using the range rather than the maximum is an unimportant detail. $\endgroup$
    – user16034
    Commented Apr 21, 2023 at 9:44
  • $\begingroup$ Birth years of living people are usually from 1910 to 1924, so the range is about one 18th of the maximum. $\endgroup$
    – gnasher729
    Commented May 15 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.