병합정렬 구현

Jmnote (토론 | 기여)님의 2018년 7월 15일 (일) 22:13 판 (→‎Java)

1 C

#include <stdio.h>
void merge(int arr[], 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(arr[j]<=arr[k]) temp[i]=arr[j++];
		else temp[i]=arr[k++];
	}
	while(j <= middle) temp[i++]=arr[j++];
	while(k <= right) temp[i++]=arr[k++];
	for(i=left; i<=right; i++) arr[i]=temp[i]; 
}
void merge_sort(int arr[], int left, int right) {
	if(left >= right) return;
	int middle = (left+right)/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 Java

import java.util.Arrays;
public class MyClass {
    private static void merge(int arr[], int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;
        int L[] = new int[n1];
        int R[] = new int[n2];
        int i, j, k;
        for(i=0; i<n1; ++i) L[i]=arr[left+i];
        for(j=0; j<n2; ++j) R[j]=arr[middle+j+1];
        i=0; j=0; k=left;
        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++; }
    }
    private static void merge_sort(int arr[], int left, int right) {
        if(left >= right) return;
        int middle = (left+right)/2;
        merge_sort(arr, left, middle);
        merge_sort(arr , middle+1, right);
        merge(arr, left, middle, right);
    }
    public static void main(String args[]) {
        int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
        merge_sort(arr, 0, arr.length-1);
        System.out.println( Arrays.toString(arr) );
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
    }
}

3 Python

def merge(arr, left, middle, right):
	n1 = middle - left + 1
	n2 = right - middle
	L = [0] * (n1)
	R = [0] * (n2)
	for i in range(0 , n1):
		L[i] = arr[left + i]
	for j in range(0 , n2):
		R[j] = arr[middle + 1 + j]
	i = j = 0
	k = left
	while i < n1 and j < n2 :
		if L[i] <= R[j]:
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1
def merge_sort(arr, left, right):
	if left < right:
		middle = int((left+(right-1))/2)
		merge_sort(arr, left, middle)
		merge_sort(arr, middle+1, right)
		merge(arr, left, middle, right)
arr = [3,4,2,1,7,5,8,9,0,6,100,10]
merge_sort(arr, 0, len(arr)-1)
print( arr )
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]

4 같이 보기

5 참고

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}