/* 9(a). W.A.P. to sort the elements of a list of size 'n' using selection
sort that uses partition method of Hoare. */

#include<stdio.h>
#include<conio.h>
int a[20];
int Partition(int low,int high)
{
    int temp,key,i,j;
    if (low < high)
    {
        key = a[low];
        i = low+1;
        j = high;
        while (1)
        {
            while (a[i] <= key) i++;
            while (a[j] > key) j--;
                if (i < j)
                {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }    
                else
                    break; /* Partition is over */
        }
        a[low] = a[j];
        a[j] = key;
    }
    return j;
}
int SelSort(int low,int high,int k)
{
    int key,q,t;
    if (low == high)
    return a[low];
    q = Partition(low,high);
    t = q - low + 1;
    if (k <= t)
        return SelSort(low,q,k);
    else    
        return SelSort(q+1,high,k-t);
 }
void main()
{
    int i,k,n;
    clrscr();
    printf("Enter the number of elements : ");
    scanf("%d",&n);
    printf("\nEnter %d distinct elements only : ",n);
    for (i = 0; i < n; i++)
        scanf("%d",&a[i]);
    for (k = 1; k <= n; k++)
        a[k-1] = SelSort(0,n-1,k); /* Find the kth smallest element */
        printf("\n\nSorted list is as follows :\n");
    for (i=0; i < n; i++)
        printf("%d\n",a[i]);
        getch();
}
/* OUTPUT
Enter the number of elements : 5
Enter 5 distinct elements only : 4 234 654 26 989

Sorted list is as follows :
4
26
234
654
989
*/