Question

Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n log n)-time algorithm in class and, also, proved a lower bound of Ω(n log n) for any comparison-based algorithm.

2. Give an efficient sorting algorithm for an array C[1, ..., n] whose elements are taken from the set {1, 2, 3, 4, 5}.

Answer 1

As the number of distinct elements are re-decided, We can take an array of 6 elements (assuming index start from 0, and we will only use from index 1 to index 5).

int counts[6] = {0};

Then one by one check each element, and increment the count on the index equal to element.. So if element i is observed, then do:
counts[i] += 1

After going through the entire array, we have the couns of each element.. So, we can reconstruct the sorted array in below way:

int i = 0;
int j = 1;
while(j <= 5) {
        
        for(int x=0; x<counts[j]; x++) {
                arr[i++] = j;
        }
        j++;
}

On doing this, the array will becomes sorted, keeping all the 1s first, then 2s.. and so on.. As we do two complete traversals on the array (one for counting, another for re-constructing), So algorithm complexity is O(2n) or O(n).
Hence it is a linear algorithm.

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.