Kquick 정렬

Jan 05, 2018 조회수 298

Kquick정렬_해설.pdf [178.98 KB]

2학년 2학기, 알고리즘 강의중 권영미 교수님이 제시해준 도전 과제이다.

자랑을 하자면 본 문제를 푼 학생은, 수강생중 본인 혼자였다.

**(도전문제) 퀵 정렬에서 앞의 k개의 수들을 pivot으로 하여 퀵 정렬을 시행하는 함수를 완성하시오. 예를 들어 k=2일 때 두 수중 작은 수를 a, 큰 수를 b라 하면 전체 리스트를 a보다 작은 수, a, a와 b 사이의 수, b, b보다 큰 수들로 리스트를 정렬하는 partition을 하고 다시 각 부분에 대해 같은 일은 수행한다. **

void kquick_sort(int list[], int left, int right, int k)

Kmerge 정렬 다음으로, 시간을 많이 걸린 문제였다.

비교적 아이디어는 쉽게 얻어 빨리 해답을 찾을 수 있었다.

코드는 다음과 같다. 해설파일은 첨부하였다.

#include <stdio.h>
#include <stdlib.h>

#define swap(x,y,t) (t=x,x=y,y=t)
#define max 10

typedef int element;

void printList(element list[], int left, int right){
	for (int i = left; i < right; i++)
		printf(" %d - ", list[i]);
	printf("\n");
}

void kquick_sort(element list[], int left, int right, int k);

element* SetPivot(element list[], int left, int k){ //pivot값 정렬
	element* p = (element*)malloc(sizeof(element)*k);
	int l = 0;

	for (int i = left; i < left + k; i++)//왼쪽부터 k개만큼 *p에 입력
		p[l++] = list[i];

	kquick_sort(p, 0, k - 1, 1); // 입력된값을 퀵정렬을 통해 정렬

	return p;

}

int* kpartition(element list[], int left, int right, int k){
	element temp;
	element *pivot = SetPivot(list, left, k); //pivot값을 할당함
	int *highpoint = (int*)malloc(sizeof(int)*k); //k개의 highpoint
	int low, high;
	int i = 0, j;

	while (i < k){//k번만큼 수행

		for (j = left; j <= right; j++) //list에서 피봇의 index를 찾아냄
			if (pivot[i] == list[j])break;
		swap(list[left], list[j], temp);//왼쪽과 pivot의 위치를 바꿈

		low = left;
		high = right + 1;

		do{//pivot[i]를 기준으로 작은값 큰값 정렬
			do
				low++;
			while (low < right &amp;&amp; list[low] < pivot[i]);

			do
				high--;
			while (left < high &amp;&amp; list[high] >= pivot[i]);

			if (low < high)
				swap(list[low], list[high], temp);

		} while (low< high);
		swap(list[left], list[high], temp);

		highpoint[i] = high;//high값 저장
		left = high + 1;//left를 high값의 바로 오른쪽값으로 해줌
		i++;
	}

	free(pivot);
	return highpoint;
}

void kquick_sort(element list[], int left, int right, int k){
	int *q;
	int *startpoint, *endpoint;
	int gap = right - left;
	if (gap >= k){
		q = kpartition(list, left, right, k);

		startpoint = (int*)malloc(sizeof(int)*(k + 1));//startpoint 할당
		endpoint = (int*)malloc(sizeof(int)*(k + 1));//endpoint 할당
		startpoint[0] = left;
		for (int i = 1; i < k + 1; i++)
			startpoint[i] = q[i - 1] + 1;

		endpoint[k] = right;
		for (int i = 0; i < k; i++)
			endpoint[i] = q[i] - 1;

		for (int i = 0; i < k + 1; i++)
			kquick_sort(list, startpoint[i], endpoint[i], k);

		free(startpoint);
		free(endpoint);
		free(q);
	}
	else if (0 < gap &amp;&amp; gap < k)kquick_sort(list, left, right, 1);
	else;
}

int main() {
	int list[max];
	int k;
	while (true){
		for (int i = 0; i < max; i++){
			list[i] = rand() % 100;
		}
		printf("----------------k갯수 Pivot 퀵정렬------------ \n");
		printList(list, 0, max);
		printf("\n");
		printf("k값을 입력해주십시오.\n");
		scanf_s("%d", &amp;k);
		printf("\n");


		if (k>max || k == 0)printf("error\n");
		else{
			printf(".....%d갯수 Pivot 퀵정렬 완료 \n", k);
			kquick_sort(list, 0, max - 1, k);
		}
		printList(list, 0, max);
		printf("\n");
		printf("=========================================================================\n\n");


	}
}

'Kquick 정렬' 관련된 다른글

이전 댓글 보기

알림

등록

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.