JavaA2Z

KAB-studio > プログラミング > JavaA2Z > マージソートとは

マージソート

日本語 併合並び替え
英語 merge sort、mergesort
ふりがな まーじそーと
フリガナ マージソート

解説

分割した要素マージしていくソート
ソートアルゴリズムのひとつ。
最速レベルのソートであり、安定ソートでもある、とソートアルゴリズムの優等生。
 
配列を一度バラバラに分解し、バラバラになった要素を隣同士くっつけていく際に「小さい方を左に、大きい方を右に」するようくっつけていくと、最終的にはソートされている、というアルゴリズム
この「くっつける」という作業を「マージ」と呼ぶため「マージソート」と呼ぶ。
マージされた塊は「すでにソートされている」ため、これを小さい順にマージする処理は「要素の比較」の回数が少なくて済み、ソートアルゴリズムの中でもトップクラスの速さを誇る。
 
最速レベルであり、安定ソートであり、様々なソートに利用できる事もあり、よく使われるアルゴリズムである。
 
Arraysクラスのsort()メソッドクラスソートする場合にはこのアルゴリズムを改良した「修正マージソート」を使用しているため、Arraysクラスのsort()メソッドを用いたソートはかなり優秀なソートということができる。

参考サイト


(KAB-studioからのおしらせです)

サンプルプログラム(とか)サンプルを別ウィンドウで表示サンプルをクリップボードへコピー(WindowsでIEの場合のみ)

// Sample.java
public class Sample
{
    public static void main( String[] args )
    {
        // 出力する配列を用意します。
        int[] ints = new int[]{ 4, 9, 3, 5, 8 };

        forint iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 4, 9, 3, 5, 8, 

        // マージソートします。
        mergeSort( ints );

        forint iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 3, 4, 5, 8, 9, 
    }

    /**
    *   マージソートします。
    */
    private static void mergeSort( int[] array )
    {
        if( array.length <= 1 )
        {
            // 要素数が1以下なら何もしません。
            return;
        }

        // 中央から左側のサイズを取得します。
        int leftSize = array.length / 2;
        // 中央から右側のサイズを取得します。
        int rightSize = array.length - leftSize;
        // 中央から左側のサイズの配列を作成します。
        int[] leftArray = new int[leftSize];
        // 中央から右側のサイズの配列を作成します。
        int[] rightArray = new int[rightSize];
        // それぞれコピーします。
        int iF1;
        for( iF1 = 0; iF1 < leftSize; ++iF1 )
        {
            leftArray[iF1] = array[iF1];
        }
        
        for( iF1 = 0; iF1 < rightSize; ++iF1 )
        {
            rightArray[iF1] = array[leftSize + iF1];
        }

        // それぞれ再帰呼び出しします。
        mergeSort( leftArray );
        mergeSort( rightArray );

        // マージします。
        int leftPos = 0;
        int rightPos = 0;
        while(
            ( leftPos  < leftSize  ) || 
            ( rightPos < rightSize )
            )
        {
            // 左右両方とも配列の中にいる間、ループします。

            if( rightSize <= rightPos )
            {
                // 右側が配列の最後まで来ている場合。
                // 左側を追加します。
                array[leftPos + rightPos] = leftArray[leftPos];
                ++leftPos;
            }
            else if( leftSize <= leftPos )
            {
                // 左側が配列の最後まで来ている場合。
                // 右側を追加します。
                array[leftPos + rightPos] = rightArray[rightPos];
                ++rightPos;
            }
            else if( leftArray[leftPos] > rightArray[rightPos] )
              {
                // 左側の方が右側より大きい場合。
                // 右側を追加します。
                array[leftPos + rightPos] = rightArray[rightPos];
                ++rightPos;
              }
              else
            {
                // それ以外の場合(左側の方が右側より小さい場合)。
                // 左側を追加します。
                array[leftPos + rightPos] = leftArray[leftPos];
                ++leftPos;
            }
        }
    }
}
// Sample.java
public class Sample
{
    public static void main( String[] args )
    {
        // 出力する配列を用意します。
        int[] ints = new int[]{ 4, 9, 3, 5, 8 };

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 4, 9, 3, 5, 8, 

        // マージソートします。
        mergeSort( ints );

        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 3, 4, 5, 8, 9, 
    }

    /**
    *   マージソートします。
    */
    private static void mergeSort( int[] array )
    {
        if( array.length <= 1 )
        {
            // 要素数が1以下なら何もしません。
            return;
        }

        // 中央から左側のサイズを取得します。
        int leftSize = array.length / 2;
        // 中央から右側のサイズを取得します。
        int rightSize = array.length - leftSize;
        // 中央から左側のサイズの配列を作成します。
        int[] leftArray = new int[leftSize];
        // 中央から右側のサイズの配列を作成します。
        int[] rightArray = new int[rightSize];
        // それぞれコピーします。
        int iF1;
        for( iF1 = 0; iF1 < leftSize; ++iF1 )
        {
            leftArray[iF1] = array[iF1];
        }
        
        for( iF1 = 0; iF1 < rightSize; ++iF1 )
        {
            rightArray[iF1] = array[leftSize + iF1];
        }

        // それぞれ再帰呼び出しします。
        mergeSort( leftArray );
        mergeSort( rightArray );

        // マージします。
        int leftPos = 0;
        int rightPos = 0;
        while(
            ( leftPos  < leftSize  ) || 
            ( rightPos < rightSize )
            )
        {
            // 左右両方とも配列の中にいる間、ループします。

            if( rightSize <= rightPos )
            {
                // 右側が配列の最後まで来ている場合。
                // 左側を追加します。
                array[leftPos + rightPos] = leftArray[leftPos];
                ++leftPos;
            }
            else if( leftSize <= leftPos )
            {
                // 左側が配列の最後まで来ている場合。
                // 右側を追加します。
                array[leftPos + rightPos] = rightArray[rightPos];
                ++rightPos;
            }
            else if( leftArray[leftPos] > rightArray[rightPos] )
              {
                // 左側の方が右側より大きい場合。
                // 右側を追加します。
                array[leftPos + rightPos] = rightArray[rightPos];
                ++rightPos;
              }
              else
            {
                // それ以外の場合(左側の方が右側より小さい場合)。
                // 左側を追加します。
                array[leftPos + rightPos] = leftArray[leftPos];
                ++leftPos;
            }
        }
    }
}

この単語を含むページ

「みだし」に含まれているページ

「サンプルプログラムとか」に含まれているページ

はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
Yahoo!ブックマーク 詳細を表示 users
del.icio.us 登録する RSSに登録
サンプルを別ウィンドウで表示
サンプルをクリップボードへコピー(WindowsでIEの場合のみ)
update:2005/07/18
このページは、Javaプログラミング言語についての用語を網羅した辞書「JavaA2Z」の一ページです。
詳しくは「JavaA2Z」表紙の説明をご覧ください。