[알고리즘] 퀵 정렬

퀵 정렬

• 분할정복방법론
• 다른 완소와의 비교만으로 정렬을 수행하는 비교 정렬에 속함
• 최악 시간복잡도 - O(n^2), 평균 시간복잡도 - O(nlogn)
• 일반적으로 다른 O(nlogn)알고리즘에 비해 훨씬 빠르게 동작

 

 

 

 

 

피봇은 제일 오른쪽에 있는 값으로 설정

#include <stdio.h>

void quickSort(int *A, int p, int r) {
	int q;
	if (p < r) {
		q = partition(A, p, r);	// 분할
		quickSort(A, p, q - 1);	// 왼쪽 부분 배열 정렬
		quickSort(A, q + 1, r);	// 오른쪽 부분 배열 정렬
	}
}

int partition(int *A, int p, int r) {
	int i = p;
	int j = p;
	int tmp = 0;
	while (j != r) {
		if (A[j] > A[r]) {
			j++;
		}
		else {
			tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
			i++;
			j++;
		}
	}
	tmp = A[i];
	A[i] = A[r];
	A[r] = tmp;
	return i;
}

int main(void) {
	int arr[10] = { 31,8,48,73,11,3,20,29,65,15 };
	quickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	return 0;
}

 

 

맨 처음 피봇 선택

#include <stdio.h>
void quickSort(int* A, int p, int r) {
	if (p < r) {
		int q = partition(A, p, r);
		quickSort(A, p, q - 1);
		quickSort(A, q + 1, r);
	}
}

int partition(int* A, int p, int r) {
	int pivot = A[p];
	int low = p + 1;
	int high = r;
	int temp;
	do {
		while (A[low] < pivot)low++;
		while (A[high] > pivot)high--;
		if (low < high) {
			temp = A[low];
			A[low] = A[high];
			A[high] = temp;
		}
	}while (low <= high);

	temp = pivot;
	A[p] = A[high];
	A[high] = temp;
	return high;
}

int main(void) {
	int arr[10] = { 31,8,48,73,11,3,20,29,65,15 };
	quickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	return 0;
}