Kmerge 정렬

기존의 합력정렬은 2등분 하여, 병합 과정을 통해 merge 한다.

2학년 2학기, 알고리즘 강의에 권영미 교수님께서 다음과 같은 도전 문제를 제시해 주었다.

<br/>

<br/>

<span style="background-color:#ffffff"><span style="background-color:#ffffff">(도전문제<span style="background-color:#ffffff">) <span style="background-color:#ffffff">합병정렬에서 <span style="background-color:#ffffff">2<span style="background-color:#ffffff">등분을 하는 경우를 포함하여 <span style="background-color:#ffffff">k<span style="background-color:#ffffff">등분하는 경우 합병정렬을 완성하시오<span style="background-color:#ffffff">.

<span style="background-color:#ffffff"><span style="background-color:#ffffff">함수의 형태는

<span style="background-color:#ffffff"><span style="background-color:#ffffff">void kmerge_sort(int list[], int left, int right, int k)

<br/>

<br/>

해당 문제를 푸는데 일주일을 고민한 것 같다.

지나온 과제중 가장 재밌었고, 가장 기억에 남는 과제이다.

코드는 다음과 같다. 해설파일을 첨부한다.

<br/>

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

typedef int element;

#define max 10
element sorted[max];

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

bool index_confirm(int startpoint[], int endpoint[], int n){
	bool result = false;
	for (int i = 0; i < n; i++){
		if (startpoint[i] <= endpoint[i])result = true;
		else return false;
	}
	return result;
}

int MinData(element list[], int midpoint[], int n){
	int minindex = 0;
	int i = 0;
	int mindata = list[midpoint[0]];
	for (i = 1; i <n; i++){
		if (list[midpoint[i]] < mindata){
			mindata = list[midpoint[i]];
			minindex = i;
		}
	}
	return minindex;
}

void kmerge(element list[], int startpoint[], int endpoint[], int n){
	int left = startpoint[0];
	int right = endpoint[n - 1];
	int q = left;
	int minpointindex = 0;

	while (n != 1){//startpoint가 1개가 남지안을경우
		bool result = index_confirm(startpoint, endpoint, n); // 각 startpoint값중 다음 endpoint를 넘어간 list가 있는지 확인
		while (result == true){
			minpointindex = MinData(list, startpoint, n); //최소값을 가진 startpoint index값을구함
			sorted[q++] = list[startpoint[minpointindex]];
			startpoint[minpointindex]++;
			result = index_confirm(startpoint, endpoint, n);
		}
		for (int i = minpointindex; i < n; i++){ // endpoint값이 넘어간 부분을 제외시킴
			startpoint[i] = startpoint[i + 1];
			endpoint[i] = endpoint[i + 1];
		}
		n--; //제외시키므로 point 범위를 한칸 줄임
	}

	while (startpoint[0] <= endpoint[0]){ //point가 1개가남앗을경우 모두 sort에 넣어버림
		sorted[q++] = list[startpoint[0]];
		startpoint[0]++;
	}

	for (int i = left; i <= right; i++)
		list[i] = sorted[i];
}

void kmerge_sort(element list[], int left, int right, int k){				
	int amount = right - left + 1;
	if (amount == 1);
	else if (amount <k)
			kmerge_sort(list, left, right, 2);
	else {
		int *startpoint, *endpoint;
		int lastStartpoint = 1;
		int gap = 1;
		int i = k;

		while (i < amount){ // 차이값을 구하는 프로그램 *규칙에따라서
			lastStartpoint = (k - 1)*gap;
			if (k == 2 &amp;&amp; i == 2 * lastStartpoint)gap++;
			else if (k != 2 &amp;&amp; i - lastStartpoint == (k - 1))gap++;
			i++;

		}

		int n = k;

		startpoint = (int*)malloc(sizeof(int)*n);//startpoint할당
		for (i = 0; i < k; i++)
			startpoint[i] = left + gap*i;

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

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

		kmerge(list, startpoint, endpoint, n);

		free(startpoint);
		free(endpoint);
	}	
}


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


		if (k>max || k == 1)printf("error\n");
		else{
			printf(".....%d등분 정렬 완료 \n", k);
			kmerge_sort(list, 0, max - 1, k);
		}
		printList(list, max);
		printf("\n");
		printf("=========================================================================\n\n");


	}
}
<br/>

<br/>

<br/>