티스토리 뷰

[Algorithm]

MergeSort

별을쫓다 2011. 9. 18. 18:20
import java.util.*;

public class MergeSort
{
    public static void main( String[] args )
    {
        int[] arrays = new int[32];
        for( int i = 0; i < 32; i++ )
        {
            arrays[ i ] = ( 32 - i ) * 2;
        }
        
        for( int i = 0; i < 32; i++ )
        {
            System.out.println( i + "th : " + arrays[i] );
        }
        
        mergeSort( 32, arrays );
        
        
        for( int i = 0; i < 32; i++ )
        {
            System.out.println( i + "th : " + arrays[i] );
        }
        
    }

    public static void mergeSort( int n, int[] array )
    {
        if ( n > 1 )
        {
            int mid;
            int leftSize = 0, rightSize = 0;
            int[] U = null;
            int[] V = null;
            leftSize = (int) Math.floor( n / 2 );
            rightSize = n - leftSize;

            U = new int[ leftSize ];
            U = Arrays.copyOfRange( array, 0, leftSize );
            V = new int[ rightSize ];
            V = Arrays.copyOfRange( array, leftSize, n );
            mergeSort( leftSize, U );
            mergeSort( rightSize, V );
            merge( leftSize, rightSize, U, V, array );
        }
    }

    private static void merge( int h, int m, int[] U, int[] V, int[] array )
    {
        int i = 0, j = 0, k = 0;

        while (i < h && j < m)
        {
            if ( U[ i ] < V[ j ] )
            {
                array[ k ] = U[ i++ ];
            } else
            {
                array[ k ] = V[ j++ ];
            }
            ++k;
        }
        if( i > h )
        {
            for( int a = k; a < array.length; a++ )
            {
                array[ a ] = V[ j++ ];
            }
        }
        else
        {
            for( int a = k; a < array.length; a++ )
            {
                array[ a ] = U[ i++ ];
            }
        }
    }
}

'[Algorithm]' 카테고리의 다른 글

Binary Search  (0) 2011.09.02
Linear Search  (0) 2011.09.02
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함