[C언어]퀵 정렬 프로그램 구현하기

실행 예시

퀵 정렬은 정렬에서 정말 중요한 방법이므로 필시 숙지해야하는 방법입니다.

 

 

피봇 개념이 어려울수있는데 코드를 실행시키면서 정확히 개념을 집으면 정말 쉽고 간단한 정렬입니다

---

<구현 예시>

#include <stdio.h>
typedef int element;
int size, i = 0;

//피봇 위치를 확정하고 분할 위치를 정하는 함수
int partition(element a[], int begin, int end) {
	int pivot, L, R, t;
	element temp;
	L = begin;
	R = end;
	pivot = (int)((begin + end) / 2.0); //피봇은 중심값으로 설정

	printf("\n [%d단계: pivot= %d ] \n", ++i, a[pivot]);
	while (L < R) { //L은 R보다 클수 없음
		while ((a[L] < a[pivot]) && (L < R)) L++; //L이 피봇보다 작고 L<R을 동시에 만족하면 L++을 실행한다.
		while ((a[R] >= a[pivot]) && (L < R))R--;
		if (L < R) {
			temp = a[L];
			a[L] = a[R];
			a[R] = temp;

			if (L == pivot) {
				pivot = R;
			}
		}

		//L=R이 된 경우 더 이상 진행 할수 없으므로 교체를 실시하여야한다
		temp = a[pivot];
		a[pivot] = a[R];
		a[R] = temp;

		for (t = 0; t < size; t++) {
			printf("%3d", a[t]);
		}
		printf("\n");
		return R;
	}
}

void quickSort(element a[], int begin, int end) {
	int p;
	if (begin < end) {
		p = partition(a, begin, end); //분할 위치 결정
		quickSort(a, begin, p - 1); //왼쪽 부분집합
		quickSort(a, p + 1, end);//오른쪽 부분집합(왼쪽 부분집합 전부 처리후 실행)
	}
}

void main() {
	element list[8] = { 69,10,30,2,16,8,31,22 };
	size = 8;
	printf("\n[초기 상태]:");
	for (int i = 0; i <= size - 1; i++) {
		printf("%3d", list[i]);
	}

	quickSort(list, 0, size - 1);
}