[C언어] 퀵정렬 빠른정렬을 작성하고 출력하는 프로그램을 작성하시오 quickSort(element a[], int begin, int end)

공부하시는대에 도움이 됐으면 좋겠습니다.

답안코드 확인해주세요!

 

#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) {
		while ((a[L]<a[pivot]) && (L<R)) L++;
		while ((a[R] >= a[pivot]) && (L<R)) R--;
		if (L<R) {					// L과 R 원소의 자리 교환
			temp = a[L];
			a[L] = a[R];
			a[R] = temp;

			if (L == pivot)			// L이 피봇인 경우,             
				pivot = R;			// 변경된 피봇의 위치(R)를 저장! 
		} // if(L<R)
	} // while(L<R)

	  // (L=R)이 된 경우, 
	  // 더 이상 진행할 수 없으므로 R 원소와 피봇 원소의 자리를 교환하여 마무리
	temp = a[pivot];
	a[pivot] = a[R];
	a[R] = temp;
	for (t = 0; t<size; t++) printf(" %d", 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;	// list 배열의 원소 개수
	printf("\n [ 초기 상태 ] \n");
	for (int i = 0; i <= size - 1; i++) printf(" %d", list[i]);
	printf("\n");

	quickSort(list, 0, size - 1);

	getchar();
}

 

더 많은 C코드가 보고 싶다면?

https://chuinggun.tistory.com/category/C%EC%96%B8%EC%96%B4