Wednesday, April 17, 2013

Sort n values using quick sort method

Suppose n different values are stored in numeric array a from the location 0 to n-1.Consider a dummy value which is largest among all input values. Place this dummy value at the n+1 location i.e. logical position a[n].In short place this dummy value after the last input value.The dummy value is used for sorting as follows -
1. a[n]=dummy value
2. Consider two indices l(low) and h(high).Initialize l to 0 and h to n-1.
3. If the lower limit is less than the higher limit then do the following -
    a. Consider temporary variable k.Copy the content of the position l i.e. a[l] into k.Here k acts as a reference value for creating two partitions.
    b. Consider two indices i and j.Initialize i to lower limit l and j to higher limit h+1.
    c. While i < j do the following
        i. While value of a[i] is less than or equal to k and i is less than h,increment i.
        ii. While value of a[j] is greater than or equal to k and j is greater than l ,decrement j.
        iii. If i is less than j ,then swap the values of a[i] and a[j].
    d. If j is not equal to l ,then swap the values of a[j] and a[l].
    e. After swapping a[l] and a[j],two partitions are created.First partition is from l to j-1 and second partition is from j+1 to h.
4. Use the steps from 2 to 3 for each partition till no more partition is possible.
5. After creating all the partitions , the input values are sorted automatically.

#include < stdio.h >
#include < conio.h >

void main()
{
    int a[50];
    int n;
    clrscr();
    printf("\nEnter n: ");
    scanf("%d",&n);
    read_data(a,n);
    a[n]=9999;
    printf("\nBefore sort :");
    print_data(a,n);
    qsort(a,0,n-1,n);
    printf("\nAfter sort :");
    print_data(a,n);
}

int read_data(int a[],int max)
{
    int i;
    printf("\nEnter %d values \n",max);
    for(i=0; i < max; i++)
    {
        scanf("%d",&a[i]);
    }
    return;
}

int print_data(int a[],int max)
{
    int i;
    for(i=0; i < max; i++)
    {
        printf("%4d",a[i]);
    }
    return;
}

int quick_sort(int a[],int l,int h,int n)
{
    int i,j,k,t;
    if(l < h)
    {
        k=a[l];
        i=l;
        j=h+1;
        while( i < j)
        {
            while( i < h && a[i] <= k)
                i++;

            while( j > l && a[j] > =k)
                j--;

            if( i < j)
            {
                  t=a[i];
                  a[i]=a[j];
                  a[j]=t;
            }
        }
        if( l != j)
        {
            t=a[l];
            a[l]=a[j];
            a[j]=t;
        }
        printf("\nOutput :");
        print_data(a,n);
        qsort(a,l,j-1,n);
        qsort(a,j+1,h,n);
    }
    //print_data(a,n);
    return;
}

No comments:

Post a Comment