최신판 |
당신의 편집 |
1번째 줄: |
1번째 줄: |
| [[분류: 병합정렬]] | | [[분류: 정렬]] |
| ==C== | | ==C== |
| [[분류: C]] | | [[분류: C]] |
| {{참고|C 병합정렬 구현}} | | {{참고|C 병합정렬 구현}} |
| <syntaxhighlight lang='c'> | | <source lang='c'> |
| #include <stdio.h> | | #include <stdio.h> |
| void merge_sort(int a[], int left, int right) { | | void merge(int arr[], int left, int middle, int right) { |
| if( left>=right ) return;
| | int temp[right-1], i, j, k; |
| int middle = (left+right-1)/2; | | for(i=left, j=left, k=middle+1; j<=middle && k<=right; i++) { |
| merge_sort(a, left, middle);
| | if(arr[j]<=arr[k]) temp[i]=arr[j++]; |
| merge_sort(a, middle+1, right);
| | else temp[i]=arr[k++]; |
| int n1 = middle + 1 - left;
| | } |
| int n2 = right - middle;
| | while(j <= middle) temp[i++]=arr[j++]; |
| int i, j, k, L[n1], R[n2];
| | while(k <= right) temp[i++]=arr[k++]; |
| for(i=0; i<n1; i++) L[i]=a[left+i];
| | for(i=left; i<=right; i++) arr[i]=temp[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() {
| | void merge_sort(int arr[], int left, int right) { |
| int arr[] = {9,1,22,4,0,-1,1,22,100,100};
| | if(left >= right) return; |
| int size = sizeof(arr)/sizeof(int);
| | int middle = (left+right)/2; |
| merge_sort(arr, 0, size-1);
| | merge_sort(arr, left, middle); |
| for(int i=0; i<size; i++) printf("%d ", arr[i]);
| | merge_sort(arr, middle+1, right); |
| // -1 0 1 1 4 9 22 22 100 100
| | merge(arr, left, middle, right); |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==C++==
| |
| [[분류: C++]]
| |
| {{참고|C++ 병합정렬 구현}}
| |
| <syntaxhighlight 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 main() { |
| int arr[] = {9,1,22,4,0,-1,1,22,100,10}; | | int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10}; |
| int size = sizeof(arr)/sizeof(int); | | int size = sizeof(arr)/sizeof(int); |
| merge_sort(arr, 0, size-1);
| | merge_sort(arr, 0, size-1); |
| for(int x: arr) std::cout << x << " ";
| | for(int i=0; i<size; i++) printf("%d ", arr[i]); |
| // -1 0 1 1 4 9 10 22 22 100
| | // 0 1 2 3 4 5 6 7 8 9 10 100 |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==C#==
| |
| [[분류: csharp]]
| |
| {{참고|C샵 병합정렬 구현}}
| |
| <syntaxhighlight 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
| |
| }
| |
| } | | } |
| </syntaxhighlight> | | </source> |
|
| |
|
| ==Java== | | ==Java== |
| [[분류: Java]] | | [[분류: Java]] |
| {{참고|Java 병합정렬 구현}} | | {{참고|Java 병합정렬 구현}} |
| <syntaxhighlight lang='Java'> | | <source lang='Java'> |
| public class MyClass {
| | </source> |
| 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
| |
| }
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==Perl==
| |
| [[분류:Perl]]
| |
| {{참고|Perl 병합정렬 구현}}
| |
| <syntaxhighlight 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
| |
| </syntaxhighlight>
| |
| | |
| ==PHP==
| |
| [[분류: PHP]]
| |
| {{참고|PHP 병합정렬 구현}}
| |
| <syntaxhighlight 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
| |
| </syntaxhighlight> | |
|
| |
|
| ==Python== | | ==Python== |
| [[분류: Python]] | | [[분류: Python]] |
| {{참고|Python 병합정렬 구현}} | | {{참고|Python 병합정렬 구현}} |
| <syntaxhighlight lang='Python'> | | <source lang='Python'> |
| def merge_sort(a, left=0, right=-1):
| | </source> |
| 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]
| |
| </syntaxhighlight>
| |
| | |
| ==Ruby==
| |
| [[분류: Ruby]]
| |
| {{참고|Ruby 병합정렬 구현}}
| |
| <syntaxhighlight 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]
| |
| </syntaxhighlight> | |
|
| |
|
| ==같이 보기== | | ==같이 보기== |
| | * [[정렬 구현]] |
| * [[병합정렬]] | | * [[병합정렬]] |
| * [[정렬 구현]]
| |
|
| |
| ==참고==
| |
| * https://www.geeksforgeeks.org/merge-sort/
| |
| * https://www.interviewbit.com/tutorial/merge-sort-algorithm/
| |