#include <stdio.h>

#include <stdlib.h>



void bubbleSort(int seq[], int n)

{

	int i;

	int j;

	int tmp;

	int exchange;

	for (i=0; i<n; i++) {

		exchange = 0;

		for (j=n; j>i; j--) {

			if (seq[j] < seq[j-1]) {

				/* swap j and j-1 */

				tmp = seq[j];

				seq[j] = seq[j-1];

				seq[j-1] = tmp;



				exchange = 1;

			}	

		}

		if (exchange == 0) {

			return;

		}

	}		

}



int partition(int seq[], int n, int low, int high) {

	int i;

	int pivot = seq[low];

	int tmp;

	int k=low;

	for (i=low+1; i<=high; i++) {

		if (seq[i] < pivot) {

			k++;



			/* swap k and i */		

			tmp = seq[k];

			seq[k] = seq[i];

			seq[i] = tmp;

		}

	}

	

	/* swap k and low */

	seq[low] = seq[k];

	seq[k] = pivot;

	return k;

}



void quickSort(int seq[], int n, int low, int high) {

	int pivotPos;

	if (low < high) {

		pivotPos = partition(seq, n, low, high);

		quickSort(seq, n, low, pivotPos-1);	

		quickSort(seq, n, pivotPos+1, high);

	}

}



void main()

{

	int ancient[] = {1,9,1,2,3,4,4,5,5,7,8,9,10};

	int seq[] = {1,9,1,2,3,4,4,5,5,7,8,9,10};

	int n = sizeof(seq)/sizeof(int);

	int i;



	printf("Bubble sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	bubbleSort(seq, n);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");



	printf("Quick sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}

	printf("\n");

	quickSort(seq, n, 0, n-1);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");

}