How to sort an int array in linear time?

Question

I had been given a homework to do a program to sort an array in ascending order.I did this:

#include <stdio.h>
int main()
 {
    int a[100],i,n,j,temp;
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    for(i=0;i<n;++i)
      {
       printf("%d. Enter element: ",i+1);
       scanf("%d",&a[i]);
     }
    for(j=0;j<n;++j)
    for(i=j+1;i<n;++i)
     {
         if(a[j]>a[i])
          {
             temp=a[j];
             a[j]=a[i];
             a[i]=temp;
         }
    }
    printf("Ascending order: ");
    for(i=0;i<n;++i)
        printf("%d  ",a[i]);
    return 0;
}

The input will not be more than 10 numbers. Can this be done in less amount of code than i did here? I want the code to be as shortest as possible.Any help will be appreciated.Thanks!

Answer 1

You have 10 lines doing the sorting. If you're allowed to use someone else's work (subsequent notes indicate that you can't do this), you can reduce that by writing a comparator function and calling the standard C library qsort() function:

static int compare_int(void const *v1, void const *v2)
{
    int i1 = *(int *)v1;
    int i2 = *(int *)v2;
    if (i1 < i2)
        return -1;
    else if (i1 > i2)
        return +1;
    else
        return 0;
}

And then the call is:

qsort(a, n, sizeof(a[0]), compare_int);

Now, I wrote the function the way I did for a reason. In particular, it avoids arithmetic overflow which writing this does not:

static int compare_int(void const *v1, void const *v2)
{
    return *(int *)v1 - *(int *)v2;
}

Also, the original pattern generalizes to comparing structures, etc. You compare the first field for inequality returning the appropriate result; if the first fields are unequal, then you compare the second fields; then the third, then the N^th, only returning 0 if every comparison shows the values are equal.

Obviously, if you're supposed to write the sort algorithm, then you'll have to do a little more work than calling qsort(). Your algorithm is a Bubble Sort. It is one of the most inefficient sorting techniques — it is O(N²). You can look up Insertion Sort (also O(N²)) but more efficient than Bubble Sort), or Selection Sort (also quadratic), or Shell Sort (very roughly O(N^3/2)), or Heap Sort (O(NlgN)), or Quick Sort (O(NlgN) on average, but O(N²) in the worst case), or Intro Sort. The only ones that might be shorter than what you wrote are Insertion and Selection sorts; the others will be longer but faster for large amounts of data. For small sets like 10 or 100 numbers, efficiency is immaterial — all sorts will do. But as you get towards 1,000 or 1,000,000 entries, then the sorting algorithms really matter. You can find a lot of questions on Stack Overflow about different sorting algorithms. You can easily find information in Wikipedia for any and all of the algorithms mentioned.

Incidentally, if the input won't be more than 10 numbers, you don't need an array of size 100.

Answer 2

If you know the range of the array elements, one way is to use another array to store the frequency of each of the array elements ( all elements should be int :) ) and print the sorted array. I am posting it for large number of elements (106). You can reduce it according to your need:

#include <stdio.h>
#include <malloc.h>

int main(void){
    int t, num, *freq = malloc(sizeof(int)*1000001);

    memset(freq, 0, sizeof(int)*1000001);   // Set all elements of freq to 0
    scanf("%d",&t);                         // Ask for the number of elements to be scanned (upper limit is 1000000)

    for(int i = 0; i < t; i++){
        scanf("%d", &num);
        freq[num]++;
    }

    for(int i = 0; i < 1000001; i++){
        if(freq[i]){
            while(freq[i]--){
                printf("%d\n", i);
            }
        }
    }
}  

This algorithm can be modified further. The modified version is known as Counting sort and it sorts the array in Θ(n) time.

Counting sort:¹

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k = O(n), the sort runs in Θ(n) time. Counting sort determines, for each input element x, the number of elements less than x. It uses this information to place element x directly into its position in the output array. For example, if 17 elements are less than x, then x belongs in output position 18. We must modify this scheme slightly to handle the situation in which several elements have the same value, since we do not want to put them all in the same position.

In the code for counting sort, we assume that the input is an array A[1...n] and thus A.length = n. We require two other arrays: the array B[1....n] holds the sorted output, and the array C[0....k] provides temporary working storage.

The pseudo code for this algo:

for i ← 1 to k do
c[i] ← 0
for j ← 1 to n do
    c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i
for i ← 2 to k do
    c[i] ← c[i] + c[i-1]
// c[i] now contains the number of elements ≤ i
for j ← n downto 1 do
    B[c[A[i]]] ← A[j]
    c[A[i]] ← c[A[j]] - 1  

---

_{1. Content has been taken from Introduction to Algorithms by Thomas H. Cormen and others.}