#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int KeyType;
typedef int InfoType;

typedef struct {
	KeyType key;
	InfoType otherinfo;
}RedType;
typedef struct {
	RedType r[MAXSIZE+1];
	int length;
}SqList;

Status ListInsert(SqList *L)
{
	int i, n;

	printf("Input number of key: ");
	scanf("%d", &n);
	if(n>MAXSIZE)
		exit(-1);

	L->r[0].key = 0;
	L->length = 0;
	for(i=1; i<=n; i++)
	{
		printf("Input key: ");
		scanf("%d", &L->r[i]);
		L->length++;
	}

	return OK;
}

void ListTraverse(SqList L)
{
	int i;
	for(i=1; i<=L.length; i++)
		printf("%d ", L.r[i].key);
	printf("\n");
}

Status LT(KeyType a, KeyType b)
{
	if(a<b)
		return TRUE;
	else
		return FALSE;
}

int Partition(SqList *L, int low, int high, _Bool change[])
{
	int pivotkey;
	int l, m, h;
	RedType tmp;

	l = L->r[low].key;
	m = L->r[(low+high)/2].key;
	h = L->r[high].key;

	if((m<l && m<h && h<l) || (m>l && m>h && h>l))
	{
		tmp = L->r[high];
		L->r[high] = L->r[low];
		L->r[low] = tmp;
	}
	else
	{
		tmp = L->r[(low+high)/2];
		L->r[(low+high)/2] = L->r[low];
		L->r[low] = tmp;
	}

	L->r[0] = L->r[low];
	pivotkey = L->r[low].key;
	while(low<high)
	{
		while(low<high && L->r[high].key>=pivotkey)
		{
			if(high<L->length && L->r[high].key>L->r[high+1].key)
			{
				tmp = L->r[high];
				L->r[high] = L->r[high+1];
				L->r[high+1] = tmp;
				change[1] = TRUE;
			}
			high--;
		}
		L->r[low] = L->r[high];
		while(low<high && L->r[low].key<=pivotkey)
		{
			if(low>1 && L->r[low].key<L->r[low-1].key)
			{
				tmp = L->r[low];
				L->r[low] = L->r[low-1];
				L->r[low-1] = tmp;
				change[0] = TRUE;
			}
			low++;
		}
		L->r[high] = L->r[low];
	}
	L->r[low] = L->r[0];
	return low;
}

void QSort(SqList *L, int low, int high)
{
	int pivotloc;
	_Bool change[2];
	int mid;

	if(low<high)
	{
		change[0] = change[1] = FALSE;
		pivotloc = Partition(L, low, high, change);
		if(change[0] && change[1])
			if(pivotloc <= (low+high)/2)
			{
				QSort(L, low, pivotloc-1);
				QSort(L, pivotloc+1, high);
			}
			else
			{
				QSort(L, pivotloc+1, high);
				QSort(L, low, pivotloc-1);
			}
		else if(change[0])
			QSort(L, low, pivotloc-1);
		else if(change[1])
			QSort(L, pivotloc+1, high);
	}
}

void QuickSort(SqList *L)
{
	QSort(L, 1, L->length);
}

void main()
{
	SqList L;

	ListInsert(&L);
	QuickSort(&L);
	ListTraverse(L);
}