C언어 병합정렬 구현

1 개요[ | ]

C 병합정렬 구현

#include <stdio.h>
void merge_sort(int a[], int left, int right) {
    if( left>=right ) return;
    int middle = (left+right-1)/2;
    merge_sort(a, left, middle);
    merge_sort(a, middle+1, right);
    int n1 = middle + 1 - left;
    int n2 = right - middle;
    int i, j, k, L[n1], R[n2];
    for(i=0; i<n1; i++) L[i]=a[left+i];
    for(i=0; i<n2; i++) R[i]=a[middle+1+i];
    i=j=0; k=left;
    while( i<n1 && j<n2 ) {
        if( L[i]<=R[j] ) { a[k]=L[i]; i++; k++; }
        else { a[k]=R[j]; j++; k++; }
    }
    while( i<n1 ) { a[k]=L[i]; i++; k++; }
    while( j<n2 ) { a[k]=R[j]; j++; k++; }
}
int main() {
    int arr[] = {9,1,22,4,0,-1,1,22,100,100};
    int size = sizeof(arr)/sizeof(int);
    merge_sort(arr, 0, size-1);
    for(int i=0; i<size; i++) printf("%d ", arr[i]);
    // -1 0 1 1 4 9 22 22 100 100 
}

#include <stdio.h>
void merge_merge(int a[], int left, int middle, int right) {
    int temp[right-1], i, j, k;
	for(i=left, j=left, k=middle+1; j<=middle && k<=right; i++) {
		if(a[j]<=a[k]) temp[i]=a[j++];
		else temp[i]=a[k++];
	}
	while( j<=middle ) temp[i++]=a[j++];
	while( k<=right ) temp[i++]=a[k++];
	for(i=left; i<=right; i++) a[i]=temp[i]; 
}
void merge_sort(int a[], int left, int right) {
	if(left >= right) return;
	int middle = (left+right)/2;
	merge_sort(a, left, middle);
	merge_sort(a, middle+1, right);
	merge_merge(a, left, middle, right);
}
int main() {
    int arr[] = {9,1,22,4,0,-1,1,22,100,100};
    int size = sizeof(arr)/sizeof(int);
	merge_sort(arr, 0, size-1);
	for(int i=0; i<size; i++) printf("%d ", arr[i]);
	// -1 0 1 1 4 9 22 22 100 100 
}

#include<stdio.h>
void merge(int arr[], int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;
    int L[n1], R[n2], i, j, k = left;
    for(i=0; i<n1; i++) L[i] = arr[left+i];
    for(j=0; j<n2; j++) R[j] = arr[middle+j+1];
    i = j = 0;
    while( i<n1 && j<n2 ) {
        if( L[i] <= R[j] ) { arr[k] = L[i]; i++; }
        else { arr[k] = R[j]; j++; }
        k++;
    }
    while(i < n1) { arr[k] = L[i]; i++; k++; }
    while(j < n2) { arr[k] = R[j]; j++; k++; }
}
void merge_sort(int arr[], int left, int right) {
    if(left >= right) return; 
    int middle = left+(right-left)/2;
    merge_sort(arr, left, middle);
    merge_sort(arr, middle+1, right);
    merge(arr, left, middle, right);
}
int main() {
    int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
    int size = sizeof(arr)/sizeof(int);
    merge_sort(arr, 0, size-1);
    for(int i=0; i<size; i++) printf("%d ", arr[i]);
    // 0 1 2 3 4 5 6 7 8 9 10 100
}

2 같이 보기[ | ]