"병합정렬 구현"의 두 판 사이의 차이

(Python)
41번째 줄: 41번째 줄:
 
{{참고|Python 병합정렬 구현}}
 
{{참고|Python 병합정렬 구현}}
 
<source lang='Python'>
 
<source lang='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]
 
</source>
 
</source>
  

2018년 7월 15일 (일) 21:55 판

1 C

16px-Crystal_Clear_app_xmag.svg.png 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

16px-Crystal_Clear_app_xmag.svg.png Java 병합정렬 구현 문서를 참고하십시오.

3 Python

16px-Crystal_Clear_app_xmag.svg.png 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 같이 보기

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