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

28번째 줄: 28번째 줄:
for(int i=0; i<size; i++) printf("%d ", arr[i]);
for(int i=0; i<size; i++) printf("%d ", arr[i]);
// -1 0 1 1 4 9 22 22 100 100  
// -1 0 1 1 4 9 22 22 100 100  
}
</source>
==C++==
[[분류: C++]]
{{참고|C++ 병합정렬 구현}}
<source lang='cpp'>
#include <iostream>
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,10};
    int size = sizeof(arr)/sizeof(int);
    merge_sort(arr, 0, size-1);
    for(int x: arr) std::cout << x << " ";
    // -1 0 1 1 4 9 10 22 22 100
}
}
</source>
</source>

2018년 8월 27일 (월) 19:24 판

1 C

#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 
}

2 C++

#include <iostream>
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,10};
    int size = sizeof(arr)/sizeof(int);
    merge_sort(arr, 0, size-1);
    for(int x: arr) std::cout << x << " ";
    // -1 0 1 1 4 9 10 22 22 100 
}

3 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]
    }
}

4 PHP

<?php
function merge_sort(&$a, $left=0, $right=null) {
    if( is_null($right) ) $right=count($a)-1;
    if( $left>=$right ) return;
    $middle = intdiv($left+$right-1, 2);
    merge_sort($a, $left, $middle);
    merge_sort($a, $middle+1, $right);
    $n1 = $middle + 1 - $left;
    $n2 = $right - $middle;
    $L = array_fill(0, $n1, 0);
    $R = array_fill(0, $n2, 0);
    for($i=0; $i<$n1; $i++) $L[$i] = $a[$left+$i];
    for($i=0; $i<$n2; $i++) $R[$i] = $a[$middle+1+$i];
    $k = $left;
    $i = $j = 0;
    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++; }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
merge_sort( $arr );
echo implode(' ',$arr);
# -1 0 1 1 4 9 10 22 22 100

5 Python

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

6 같이 보기

7 참고

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