MergeSort(합병정렬), C, C++

데이터를 각각 낱개로 나눈 후 합치면서 정렬하는 알고리즘으로 속도면에서 빠르다.

 

주석은 내가 이해한대로, 해석한대로 달아보았고 추후에 이미지 설명이나 등등을 추가해볼 계획이다.

#include 
#define MAX 6

void mergesort_divide(int*, int, int);
void mergesort_conquer(int*, int, int, int);


void mergesort_conqure(int a[], int start, int end, int mid_index){
	//any array
	int b[1000];
	
	//first index of left array
	int i = start;
	
	//first index of right array
	int j = mid_index + 1;
	
	//sorted array index
	int k = 0;
	
	//compare left array and right array untill one of left and right index will be a last index
	while(i <= mid_index && j <= end){
		if(a[i] > a[j]){
			b[k] = a[j];
			j++;
			k++;
		} else{
			b[k] = a[i];
			i++;
			k++;
		}
	}
	
	//if left array value is bigger than right array
	while(i <= mid_index){
		b[k] = a[i];
		i++;
		k++;
	}
	
	//if right array value is bigger than left array
	while(j <= end){
		b[k] = a[j];
		j++;
		k++;
	}
	
	//if k size is bigger than array size
	k--;
	
	//write data on real array
	while(k >= 0 ){
		a[start+k] = b[k];
		k--;	
	}
		
}


void mergesort_divide(int a[], int start, int end){
	
	//exit condition (condition : when the value same start and end -> both start and end are 0.
	if(start < end){
		//value of middle
		int mid_index = (start+end) / 2;
		
		//seperate left array
		mergesort_divide(a, start, mid_index);
		
		//seperate right array
		mergesort_divide(a, mid_index+1, end);
		
		//conqure array
		mergesort_conqure(a, start, end, mid_index);
	}
	//not exit condition
	else{
		return ; 
	}
	
}

int main(){
	int a[MAX] = {20, 10, 70, 80, 40, 90};
	
	printf("before sort : " );
	for(int i = 0; i < 6; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
	
	mergesort_divide(a, 0, MAX-1);
	
	printf("after sort : " );
	for(int i = 0; i < 6; i++){
		printf("%d ", a[i]);
	}
}