COUNTING SORT

/* Program for Counting sort on numbers whose values are in certain boundary */

#include<stdio.h>
#include<stdlib.h>
#define N 100
#define LOWER_BOUND 30
#define UPPER_BOUND 99
void counting_sort(int *list,int size);

main()
{
int i=0,list[N];
int key,size;

    printf("Enter numbers with-in range %d-%d and stop with -9999\n",LOWER_BOUND,UPPER_BOUND);
    do
    {
        scanf("%d",&key);
        if(key == -9999)
        {
            break;
        }
        else if((key < LOWER_BOUND) || (key > UPPER_BOUND))
        {
            printf("Enter a value in the range %d-%d\n", LOWER_BOUND, UPPER_BOUND);
        }
        else
        {
            list[i++] = key;
        }
    }while(1);
    size = i;
    printf("original \n");

    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }

    printf("\nSorted  \n");
    counting_sort(list,size);
    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }
    getchar();
    getchar();
    return 0;
}

/* This function does the counting sort */
void counting_sort(int *list, int size)
{
int i,j,k,count[UPPER_BOUND-LOWER_BOUND+1] = {0};

    /* Count the number of repetetions for each number entered */
    for(i=0;i<size;i++)
    {
        count[list[i]-LOWER_BOUND]++;
    }
    k=0;
    /* Fill the array according to the count */
    for(i=0;i<(UPPER_BOUND-LOWER_BOUND+1);i++)
    {
        if(count[i] !=0)
        {
            for(j=0;j<count[i];j++)
            {
                list[k++] = i+LOWER_BOUND;
            }
        }
    }
    return;
}

QUICK SORT

/* QUICK sort is the fastest algorithm on random data of O(n log n) */

#include<stdio.h>
#include<stdlib.h>
#define N 100
void quick_sort(int *list,int start, int end);

main()
{
int i=0,list[N];
int key,size=1;

    do
    {
        scanf("%d",&key);
        if(key == -9999)
        {
            break;
        }
        else
        {
            list[i++] = key;
        }
    }while(1);
    size = i;
    printf("original \n");

    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }

    printf("\nSorted  \n");
    quick_sort(list,0,size-1);
    for(i=0;i<size;i++)
    {
        printf("%d ",list[i]);
    }
    getchar();
    getchar();
    return 0;
}

/* This function does the quick sort recursively */
void quick_sort(int *list, int start,int end)
{
int i,j, pivot,temp;
/* Algo should end if start > = end*/
    if(start<end)
    {
        /* store pivot and indexes*/
        pivot = list[end];
        i=start;
        j=end-1;
        while(i<j)
        {
            /* move i until list[i] < pivot*/
            while(list[i] < pivot)
            {
                i++;
            }
            /* move j until list[j] > pivot */
            while( (i < j) &&(list[j] > pivot))
            {
                j--;
            }

            /* interchange if required*/
            if(i<j)
            {
                temp    = list[i];
                list[i] = list[j];
                list[j] = temp;
                i++;
                j--;
            }
        }
        /* partition is done at i. move the pivot to i*/
        if(i<end)
        {
            list[end] = list[i];
            list[i]   = pivot;
        }
        /*Call recursive*/
        quick_sort(list,start,i-1);
        quick_sort(list,i+1,end);
    }
    return;
}