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

(새 문서: 분류: 정렬 ==C== 분류: C <source lang='c'> #include <stdio.h> #define SIZE 10 int a[SIZE] = {3,4,2,1,7,5,8,9,0,6}; int size = SIZE; int b[SIZE-1]; void merge(int low, in...)
 
 
(사용자 3명의 중간 판 39개는 보이지 않습니다)
1번째 줄: 1번째 줄:
[[분류: 정렬]]
+
[[분류: 병합정렬]]
 
==C==
 
==C==
 
[[분류: C]]
 
[[분류: C]]
 +
{{참고|C 병합정렬 구현}}
 
<source lang='c'>
 
<source lang='c'>
 
#include <stdio.h>
 
#include <stdio.h>
#define SIZE 10
+
void merge_sort(int a[], int left, int right) {
int a[SIZE] = {3,4,2,1,7,5,8,9,0,6};
+
    if( left>=right ) return;
int size = SIZE;
+
    int middle = (left+right-1)/2;
int b[SIZE-1];
+
    merge_sort(a, left, middle);
void merge(int low, int mid, int high) {
+
    merge_sort(a, middle+1, right);
int l1, l2, i;
+
    int n1 = middle + 1 - left;
for(l1=low, l2=mid+1, i=low; l1<=mid && l2<=high; i++) {
+
    int n2 = right - middle;
if(a[l1]<=a[l2]) b[i]=a[l1++];
+
    int i, j, k, L[n1], R[n2];
else b[i]=a[l2++];
+
    for(i=0; i<n1; i++) L[i]=a[left+i];
}
+
    for(i=0; i<n2; i++) R[i]=a[middle+1+i];
while(l1 <= mid) b[i++]=a[l1++];
+
    i=j=0; k=left;
while(l2 <= high) b[i++]=a[l2++];
+
    while( i<n1 && j<n2 ) {
for(i=low; i<=high; i++) a[i]=b[i];
+
        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++; }
 
}
 
}
void merge_sort(int low, int high) {
+
int main() {
if(low >= high) return;
+
    int arr[] = {9,1,22,4,0,-1,1,22,100,100};
int mid = (low+high)/2;
+
    int size = sizeof(arr)/sizeof(int);
merge_sort(low, mid);
+
    merge_sort(arr, 0, size-1);
merge_sort(mid+1, high);
+
    for(int i=0; i<size; i++) printf("%d ", arr[i]);
merge(low, mid, high);
+
    // -1 0 1 1 4 9 22 22 100 100
 
}
 
}
int main() {  
+
</source>
merge_sort(0, SIZE-1);
+
 
for(int i=0; i<SIZE; i++) printf("%d ", a[i]);
+
==C++==
// 0 1 2 3 4 5 6 7 8 9
+
[[분류: 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>
 +
 
 +
==C#==
 +
[[분류: csharp]]
 +
{{참고|C샵 병합정렬 구현}}
 +
<source lang='csharp'>
 +
using System;
 +
class Program {
 +
    static void merge_sort(int[] a) {
 +
        merge_sort(a,0,a.Length-1);
 +
    }
 +
    static 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[] L=new int[n1], R=new int[n2];
 +
        int i, j, k;
 +
        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++; }
 +
    }
 +
    static void Main() {
 +
        int[] arr = {9,1,22,4,0,-1,1,22,100,10};
 +
        merge_sort(arr);
 +
        Console.Write(string.Join(",",arr));
 +
        // -1,0,1,1,4,9,10,22,22,100
 +
    }
 +
}
 +
</source>
 +
 
 +
==Java==
 +
[[분류: Java]]
 +
{{참고|Java 병합정렬 구현}}
 +
<source lang='Java'>
 +
public class MyClass {
 +
    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++; }
 +
    }
 +
    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 = {9,1,22,4,0,-1,1,22,100,10};
 +
        merge_sort(arr, 0, arr.length-1);
 +
        for(int x: arr) System.out.format("%d ",x);
 +
        // -1 0 1 1 4 9 10 22 22 100
 +
    }
 +
}
 +
</source>
 +
 
 +
==Perl==
 +
[[분류:Perl]]
 +
{{참고|Perl 병합정렬 구현}}
 +
<source lang='perl'>
 +
sub merge_sort {
 +
    my ($a) = @_;
 +
    $size = @$a;
 +
    return if $size < 2;
 +
    $bound = int $size/2;
 +
    my @L = @$a[0 .. $bound-1];
 +
    my @R = @$a[$bound .. $size-1];
 +
    merge_sort( \@L );
 +
    merge_sort( \@R );
 +
    for $i (@$a) {
 +
        $i = !@R ? shift @L : !@L ? shift @R
 +
            : @R[0]<@L[0] ? shift @R : shift @L;
 +
    }
 +
}
 +
@arr = (9,1,22,4,0,-1,1,22,100,10);
 +
merge_sort( \@arr );
 +
print join(',',@arr);
 +
# -1,0,1,1,4,9,10,22,22,100
 +
</source>
 +
 
 +
==PHP==
 +
[[분류: PHP]]
 +
{{참고|PHP 병합정렬 구현}}
 +
<source lang='php'>
 +
<?php
 +
function merge_sort(&$a) {
 +
    $size = count($a);
 +
    if( $size<2 ) return;
 +
    $bound = intdiv($size,2);
 +
    $L = array_slice($a, 0, $bound);
 +
    $R = array_slice($a, $bound, $size);
 +
    merge_sort( $L );
 +
    merge_sort( $R );
 +
    foreach( $a as &$x ) {
 +
        if(empty($R)) { $x=array_shift($L); continue; }
 +
        if(empty($L)) { $x=array_shift($R); continue; }
 +
        $x = ($R[0]<$L[0])? array_shift($R): array_shift($L);
 +
    }
 
}
 
}
 +
$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
 +
</source>
 +
 +
==Python==
 +
[[분류: Python]]
 +
{{참고|Python 병합정렬 구현}}
 +
<source lang='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 = (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]
 +
</source>
 +
 +
==Ruby==
 +
[[분류: Ruby]]
 +
{{참고|Ruby 병합정렬 구현}}
 +
<source lang='ruby'>
 +
def merge_sort(a, left=0, right=-1)
 +
    def merge(a, left, middle, right)
 +
        n1 = middle+1-left
 +
        n2 = right-middle
 +
        l = Array.new(n1,0)
 +
        r = Array.new(n2,0)
 +
        for i in (0...n1); l[i]=a[left+i]; end
 +
        for i in (0...n2); r[i]=a[middle+1+i]; end
 +
        i=j=0; k=left
 +
        while i<n1 and j<n2
 +
            if l[i]<=r[j] then a[k]=l[i]; i+=1; k+=1
 +
            else a[k]=r[j]; j+=1; k+=1 end
 +
        end
 +
        while i<n1; a[k]=l[i]; i+=1; k+=1; end
 +
        while j<n2; a[k]=r[j]; j+=1; k+=1; end
 +
    end
 +
    right=a.size-1 if right==-1
 +
    return if left>=right
 +
    middle = (left+right-1)/2
 +
    merge_sort(a, left, middle)
 +
    merge_sort(a, middle+1, right)
 +
    merge(a, left, middle, right)
 +
end
 +
arr = [9,1,22,4,0,-1,1,22,100,10]
 +
merge_sort(arr)
 +
print arr
 +
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]
 
</source>
 
</source>
  
 
==같이 보기==
 
==같이 보기==
 
* [[병합정렬]]
 
* [[병합정렬]]
 +
* [[정렬 구현]]
 +
 +
==참고==
 +
* https://www.geeksforgeeks.org/merge-sort/
 +
* https://www.interviewbit.com/tutorial/merge-sort-algorithm/

2019년 4월 8일 (월) 23:29 기준 최신판

1 C[편집]

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

2 C++[편집]

16px-Crystal_Clear_app_xmag.svg.png 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 C#[편집]

16px-Crystal_Clear_app_xmag.svg.png C샵 병합정렬 구현 문서를 참고하십시오.
using System;
class Program {
    static void merge_sort(int[] a) {
        merge_sort(a,0,a.Length-1);
    }
    static 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[] L=new int[n1], R=new int[n2];
        int i, j, k;
        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++; }
    }
    static void Main() {
        int[] arr = {9,1,22,4,0,-1,1,22,100,10};
        merge_sort(arr);
        Console.Write(string.Join(",",arr));
        // -1,0,1,1,4,9,10,22,22,100
    }
}

4 Java[편집]

16px-Crystal_Clear_app_xmag.svg.png Java 병합정렬 구현 문서를 참고하십시오.
public class MyClass {
    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++; }
    }
    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 = {9,1,22,4,0,-1,1,22,100,10};
        merge_sort(arr, 0, arr.length-1);
        for(int x: arr) System.out.format("%d ",x);
        // -1 0 1 1 4 9 10 22 22 100 
    }
}

5 Perl[편집]

16px-Crystal_Clear_app_xmag.svg.png Perl 병합정렬 구현 문서를 참고하십시오.
sub merge_sort {
    my ($a) = @_;
    $size = @$a;
    return if $size < 2;
    $bound = int $size/2;
    my @L = @$a[0 .. $bound-1];
    my @R = @$a[$bound .. $size-1];
    merge_sort( \@L );
    merge_sort( \@R );
    for $i (@$a) {
        $i = !@R ? shift @L : !@L ? shift @R
            : @R[0]<@L[0] ? shift @R : shift @L;
    }
}
@arr = (9,1,22,4,0,-1,1,22,100,10);
merge_sort( \@arr );
print join(',',@arr);
# -1,0,1,1,4,9,10,22,22,100

6 PHP[편집]

16px-Crystal_Clear_app_xmag.svg.png PHP 병합정렬 구현 문서를 참고하십시오.
<?php
function merge_sort(&$a) {
    $size = count($a);
    if( $size<2 ) return;
    $bound = intdiv($size,2);
    $L = array_slice($a, 0, $bound);
    $R = array_slice($a, $bound, $size);
    merge_sort( $L );
    merge_sort( $R );
    foreach( $a as &$x ) {
        if(empty($R)) { $x=array_shift($L); continue; }
        if(empty($L)) { $x=array_shift($R); continue; }
        $x = ($R[0]<$L[0])? array_shift($R): array_shift($L);
    }
}
$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

7 Python[편집]

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

8 Ruby[편집]

16px-Crystal_Clear_app_xmag.svg.png Ruby 병합정렬 구현 문서를 참고하십시오.
def merge_sort(a, left=0, right=-1)
    def merge(a, left, middle, right)
        n1 = middle+1-left
        n2 = right-middle
        l = Array.new(n1,0)
        r = Array.new(n2,0)
        for i in (0...n1); l[i]=a[left+i]; end
        for i in (0...n2); r[i]=a[middle+1+i]; end
        i=j=0; k=left
        while i<n1 and j<n2
            if l[i]<=r[j] then a[k]=l[i]; i+=1; k+=1
            else a[k]=r[j]; j+=1; k+=1 end
        end
        while i<n1; a[k]=l[i]; i+=1; k+=1; end
        while j<n2; a[k]=r[j]; j+=1; k+=1; end
    end
    right=a.size-1 if right==-1
    return if left>=right
    middle = (left+right-1)/2
    merge_sort(a, left, middle)
    merge_sort(a, middle+1, right)
    merge(a, left, middle, right)
end
arr = [9,1,22,4,0,-1,1,22,100,10]
merge_sort(arr)
print arr
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

9 같이 보기[편집]

10 참고[편집]

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