/***********************************
* Section : 15
* Machine No. : N
* Roll No. : 18CS100XY
* Name : Soumyajit Dey, Aritra Hazra
* Assignment No : 6a
* Description : MinMax Sort
************************************/

#include <stdio.h>
#define MAX 100000

int main()
{
    int A[MAX], t, n, i, j, maxIndex, minIndex, start;

    /* taking n-element integer array input from user */
    printf("Enter Number of Elements: ");
    scanf("%d", &n);
    if(n==0) /* no element in array case */
    {
        printf("Array has NO element!\n");
        return;
    }
    printf("Enter %d Integer Elements: ", n);
    for(i=0; i<n; ++i)
    {
        scanf("%d", &A[i]);
    }

    /* MinMax sorting procedure */
    for(i=n-1;i>=(n+1)/2; --i)
    { /* iterate from end to middle of the array */
        maxIndex = i;
        minIndex = i;
        start = (n-1) - i;
        for(j=start; j<i; ++j)
        {
            if(A[j] > A[maxIndex]) /* finding max element */
                maxIndex = j;
            if(A[j] < A[minIndex]) /* finding min element */
                minIndex = j;
        }
        if(i != maxIndex)
        { /* putting max element at the end */
            t = A[i];
            A[i] = A[maxIndex];
            A[maxIndex] = t;
            /* update min element location in case min element gets swapped */
            if(i == minIndex)
                minIndex = maxIndex;
        }
        if(start != minIndex)
        { /* putting min element at the beginning */
            t = A[start];
            A[start] = A[minIndex];
            A[minIndex] = t;
         }
    }

    /* displaying the sorted (in ascending order) array */
    printf("The Sorted Array:");
    for(i=0; i<n; ++i)
    {
        printf(" %d,", A[i]);
    }
    printf("\n");

    return 0;
}