퀵정렬(Quick Sort)

 

 

 

 

 

 

 

 

 

 

 

 

Name	Best	Avg	Worst	Run-time (int 60,000) sec
버블정렬	n^2	n^2	n^2	22.89
선택정렬	n^2	n^2	n^2	10.84
삽입정렬	n	n^2	n^2	7.43
셀정렬	n	n^1.5	n^2	0.05
퀵정렬	nlog₂n	nlog₂n	n^2	0.01
힙정렬	nlog₂n	nlog₂n	nlog₂n	0.03
병합정렬	nlog₂n	nlog₂n	nlog₂n	0.02

 

 

 

#include<stdio.h>
#define MAX_SIZE 9
#define SWAP(x,y, temp)((temp)=(x),(x)=(y),(y)=(temp))


int partition(int list[], int left, int right)
{
	int pivot, temp;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];

	do 
	{
		do
		{
			low++;
		} while (low <= right && list[low] < pivot);

		do
		{
			high--;
		} while (high >= left && list[high] > pivot);

		if (low < high)
		{
			SWAP(list[low], list[high], temp);
		}

	} while (low < high);

	SWAP(list[left], list[high], temp);

	return high;
}

void quick_sort(int list[], int left, int right)
{
	if (left < right)
	{
		int q = partition(list, left, right);

		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}

int main()
{
	int i;
	int n = MAX_SIZE;
	int list[] = { 5, 3, 8, 4, 9, 1, 6, 2, 7};

	quick_sort(list, 0, n - 1);

	for (i = 0; i < n; i++)
	{
		printf("%d", list[i]);
	}
}