Dowemo


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!


Best Answer:


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()


{


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


        for(int i = 0; i < 1000001; i++)


            freq[i] = 0;


    scanf("%d",&t);



    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("%dn", 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:1

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.




Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs