편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
| 최신판 | 당신의 편집 | ||
| 3번째 줄: | 3번째 줄: | ||
[[분류: C]] | [[분류: C]] | ||
{{참고|C 병합정렬 구현}} | {{참고|C 병합정렬 구현}} | ||
< | <source lang='c'> | ||
#include <stdio.h> | #include <stdio.h> | ||
void merge_sort(int a[], int left, int right) { | void merge_sort(int a[], int left, int right) { | ||
| 30번째 줄: | 30번째 줄: | ||
// -1 0 1 1 4 9 22 22 100 100 | // -1 0 1 1 4 9 22 22 100 100 | ||
} | } | ||
</ | </source> | ||
==C++== | ==C++== | ||
[[분류: C++]] | [[분류: C++]] | ||
{{참고|C++ 병합정렬 구현}} | {{참고|C++ 병합정렬 구현}} | ||
< | <source lang='cpp'> | ||
#include <iostream> | #include <iostream> | ||
void merge_sort(int a[], int left, int right) { | void merge_sort(int a[], int left, int right) { | ||
| 62번째 줄: | 62번째 줄: | ||
// -1 0 1 1 4 9 10 22 22 100 | // -1 0 1 1 4 9 10 22 22 100 | ||
} | } | ||
</ | </source> | ||
==Java== | ==Java== | ||
[[분류: Java]] | [[분류: Java]] | ||
{{참고|Java 병합정렬 구현}} | {{참고|Java 병합정렬 구현}} | ||
< | <source lang='Java'> | ||
import java.util.Arrays; | |||
public class MyClass { | public class MyClass { | ||
static void merge(int[] | private static void merge(int arr[], int left, int middle, int right) { | ||
int n1 = middle - left + 1; | int n1 = middle - left + 1; | ||
int n2 = right - middle; | int n2 = right - middle; | ||
| 123번째 줄: | 87번째 줄: | ||
while( j < n2 ) { arr[k] = R[j]; j++; k++; } | while( j < n2 ) { arr[k] = R[j]; j++; k++; } | ||
} | } | ||
static void merge_sort(int arr[], int left, int right) { | private static void merge_sort(int arr[], int left, int right) { | ||
if(left >= right) return; | if(left >= right) return; | ||
int middle = (left+right)/2; | int middle = (left+right)/2; | ||
| 131번째 줄: | 95번째 줄: | ||
} | } | ||
public static void main(String args[]) { | public static void main(String args[]) { | ||
int[] | int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10}; | ||
merge_sort(arr, 0, arr.length-1); | 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] | ||
} | } | ||
} | } | ||
</ | </source> | ||
==PHP== | ==PHP== | ||
[[분류: PHP]] | [[분류: PHP]] | ||
{{참고|PHP 병합정렬 구현}} | {{참고|PHP 병합정렬 구현}} | ||
< | <source lang='php'> | ||
<?php | <?php | ||
function merge_sort(&$a) { | function merge_sort(&$a, $left=0, $right=null) { | ||
$ | if( is_null($right) ) $right=count($a)-1; | ||
if( $ | 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); | |||
if | 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]; | $arr = [9,1,22,4,0,-1,1,22,100,10]; | ||
merge_sort( $arr ); | merge_sort( $arr ); | ||
echo implode(' | echo implode(' ',$arr); | ||
# -1 | # -1 0 1 1 4 9 10 22 22 100 | ||
</ | </source> | ||
==Python== | ==Python== | ||
[[분류: Python]] | [[분류: Python]] | ||
{{참고|Python 병합정렬 구현}} | {{참고|Python 병합정렬 구현}} | ||
< | <source lang='Python'> | ||
def merge_sort(a, left=0, right=-1): | def merge_sort(a, left=0, right=-1): | ||
def merge(a, left, middle, right): | def merge(a, left, middle, right): | ||
| 202번째 줄: | 149번째 줄: | ||
i = j = 0 | i = j = 0 | ||
k = left | k = left | ||
while i<n1 and j<n2: | while i<n1 and j<n2 : | ||
if L[i]<=R[j]: a[k]=L[i]; i+=1; k+=1 | if L[i]<=R[j]: | ||
else: a[k]=R[j]; j+=1; k+=1 | 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 i<n1: a[k]=L[i]; i+=1; k+=1 | ||
while j<n2: a[k]=R[j]; j+=1; k+=1 | while j<n2: a[k]=R[j]; j+=1; k+=1 | ||
if right==-1: right=len(a)-1 | if right == -1: right = len(a)-1 | ||
if left>=right: return | if left >= right: return | ||
middle = (left+right-1) | middle = int((left+(right-1))/2) | ||
merge_sort(a, left, middle) | merge_sort(a, left, middle) | ||
merge_sort(a, middle+1, right) | merge_sort(a, middle+1, right) | ||
| 217번째 줄: | 166번째 줄: | ||
print( arr ) | print( arr ) | ||
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100] | # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100] | ||
</ | </source> | ||
==같이 보기== | ==같이 보기== | ||
* [[정렬 구현]] | |||
* [[병합정렬]] | * [[병합정렬]] | ||
==참고== | ==참고== | ||
* https://www.geeksforgeeks.org/merge-sort/ | * https://www.geeksforgeeks.org/merge-sort/ | ||