07. C언어_퀵 정렬 (Quick sort)

퀵 정렬(Quick sort)이란?

- 퀵 정렬은 기준값(pivot)을 중심으로 연속적으로 분할하며 정렬하는 기법
- pivot 값을 중심으로 pivot보다 작은 값을 왼쪽으로, pivot보다 큰 값을 오른쪽으로 배열시키는 방식
- sort가 완료될 때까지 (left>=right) 반복
 

퀵정렬 알고리즘 구현

1. sort값의 가장 우측 값을 pivot으로 설정

 
2. 한 구간 안에서 다음을 반복적으로 수행한다.
 - 구간 좌측부터 pivot보다 큰 값을 j를 증가시키면서 검사
 - 구간 우측부터 pivot보다 작은 값을 k를 감소시키면서 검사
 - j<k이면 j의 자리에 있는 값과 k의 자리에 있는 값을 교환

3. j == k이거나 j>k이면 한 구간에 대한 교환이 완료된 것이므로 j의 자리에 있는 값과 pivot의 값을 교환
 (이때 pivot값을 중심으로 좌측에는 pivot보다 작은 값이, 우측에는 pivot보다 큰 값들이 위치)
 * pivot이 j원소보다 클 때에는 교환을 하지 않고 pivot값만 고정

4. 이러한 분할 과정을 pivot값을 중심으로 나누어 좌측과 우측 두 구간에 대하여 똑같이 반복
 (구간의 크기가 1이 될 때까지 재귀 호출)

퀵 정렬 구현 코드 예제

#include <stdio.h>

/*----------------------------------------------------------------
Function 	: quickSort() - 퀵 정렬 함수
parameter	: ary - 정렬할 데이터 배열의 시작주소
			  left - 배열의 시작 index 값 (하한 index값)
			  right - 배열의 끝 index 값 (상한 index값)
return value: 없음
----------------------------------------------------------------*/
void quickSort(int ary[], int left, int right) {
	int pivot;//정렬의 기준값
	int temp;//swap을 위한 임시 변수
	int j; //
	int k;
	j = left-1;
	k = right;

	if (left >= right) {
		return;
	}//구간의 크기가 1이 될 때까지 반복

	pivot = ary[right]; //sort 구간의 가장 우측의 값을 pivot으로 설정
	do {
		while (ary[++j] < pivot); //구간 좌측부터 pivot보다 큰 값을 j를 증가시키면서 검사
		while ((--k >= 0) && ary[k] > pivot); //구간 우측부터 pivot보다 작은 값을 k를 감소시키면서 검사
		if (j < k) { //j<k이면 j의 자리에 있는 값과 k의 자리에 있는 값을 교환
            temp = ary[j];
			ary[j] = ary[k];
			ary[k] = temp;
		}
	} while (j < k); //j는 큰값을 찾으러 가고, k는 작은값을 찾으러 다시 올라가
    //j==k, j>k 이면 한 구간에 대한 교환이 완료된 것이므로 j의 자리에 있는 값과 pivot 값을 교환한다
    //이때 pivot 값을 중심으로 좌측에는 pivot보다 작은 값이, 우측에는 pivot보다 큰 값들이 위치한다.
	temp = ary[j];
	ary[j] = ary[right];
	ary[right] = temp;
    //이러한 분할 과정을 pivot값을 중심으로 나누어 좌측과 우측 두 구간에 대해 똑같이 반복한다, 구간의 크기가 1이 될때 까지 반복
	quickSort(ary, left, j - 1);
	quickSort(ary, j + 1, right);
}


/*----------------------------------------------------------------
Function	: output() - 배열의 모든 원소 출력하기
Parameters  : ary - 정렬할 데이터 배열의 시작주소
	  		  size - 정렬할 데이터의 개수
Returns	    : 없음
----------------------------------------------------------------*/
void output(int arr[], int size) {
	int i;
	for(i=0; i<size; i++) {
		printf(" %d ", arr[i]);
	}
	printf("\n");
}

int main(){
    int arr[] = {8,3,6,1,4,2,7,6,5};
    int size = sizeof(arr)/sizeof(int); //배열 내 원소의 개수 구하기 (sizeof(arr) = 5*4(int의 메모리 크기))
    quickSort(arr, 0, size-1); //left 배열의 시작 index, right 배열의 끝 index
    output(arr, size);
}

 
퀵 정렬 qsort(general 함수) 사용 정렬 예제

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
#define ARRAY_ITEM_SIZE(a) (sizeof(a[0]))
void printArray(int* ary, int n);
void printDoubleArray(double* ary, int n);
void printStrArray(char(*ary)[10], int n);
int compare(const int* one, const int* two);
int doubleCompare(const double* one, const double* two);
int strCompare(const char* one, const char* two);
int main() {
	int a[] = { 20,50,30,70,40,60 };
	double b[] = { 5.5, 7.5, 3.5, 4.5 };
	char str[][10] = { "pear", "banana", "kiwi", "apple" };
	int i;
	qsort(a, ARRAY_SIZE(a), ARRAY_ITEM_SIZE(a), (int(*)(const void*, const void*))(compare));
	printArray(a, ARRAY_SIZE(a));
	qsort(b, ARRAY_SIZE(b), ARRAY_ITEM_SIZE(b), (int(*)(const void*, const void*))(doubleCompare));
	printDoubleArray(b, ARRAY_SIZE(b));
	qsort(str, ARRAY_SIZE(str), ARRAY_ITEM_SIZE(str), (int(*)(const void*, const void*))(strCompare));
	printStrArray(str, ARRAY_SIZE(str));
	return 0;
}
int compare(const int* one, const int* two) { //비교정책을 가지고 있는 보조함수의 시작주소
	return (*one < *two) ? -1 : 1; 
}
int doubleCompare(const double* one, const double* two) { //비교정책을 가지고 있는 보조함수의 시작주소
	return (*one < *two) ? -1 : 1;
}
int strCompare(const char* one, const char* two) { //비교정책을 가지고 있는 보조함수의 시작주소
	if (strcmp(one, two) < 0) {return -1;}
	else { return 1; }
}

void printArray(int* ary, int n) {
	int i;
	for (i = 0; i < n; i++) {
		printf(" %d ", ary[i]);
	}
	printf("\n");
}

void printDoubleArray(double* ary, int n) {
	int i;
	for (i = 0; i < n; i++) {
		printf(" %lf ", ary[i]);
	}
	printf("\n");
}

void printStrArray(char(*ary)[10], int n) {
	int i;
	for (i = 0; i < n; ++i) {
		printf(" %s ", ary[i]);
	}
	printf("\n");
}