クイックソートとは : JavaA2Z

クイックソート

日本語	早並び替え
英語	quick sort、quicksort
ふりがな	くいっくそーと
フリガナ	クイックソート

最速のソート。
ソートのアルゴリズムのひとつ。
「中間の値」を決めて、左右から入れ替えていき、分割、を繰り返すアルゴリズム。
最速だが、「すでにある程度並べられている」場合にあまり効果がないこと、安定ソートではないこと、といったデメリットもある。
　
クイックソートは、まず「中間の値」を決める。
「中間の値」は、実際に配列の中央にある値を取ることもあれば、全要素の中央値を使用する場合もある。
次に、左から値を見ていき、「中間の値」より大きな値があったら止まる。
同じく、右から値を見ていき、「中間の値」より小さな値があったら止まる。
そして、この2つの値を入れ替える。と、この時点で左に小さい値、右に大きな値が来る。
これを、左右が交差するまで続ける。すると、交差した位置の左には「中間の値より小さい値」、右には「中間の値より大きい値」が来る。
この位置で左右を分割し、それぞれで再び同じ処理を行う。
これを全て行うとソートが完了する。
　
Arrays クラスのsort()メソッドでプリミティブ型の配列をソートする場合、このアルゴリズムが用いられる。
　
アルゴリズムのテキストではもったいぶって最後に登場し、「最速」をうたっておきながら、状況によって処理速度にむらがあり、安定ソートではないといったデメリットがあるため、実用度という点ではあまり高くない。

参考サイト

J2SE Array#sort()

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

// 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,

        // クイックソートします。
        quickSort( 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 quickSort( int[] array )
    {
        // 配列の先頭と最後を渡します。
        quickSortImpl( array, 0, array.length - 1 );
    }

    /**
    *   クイックソートの実装。
    *   再帰呼び出しされます。
    */
    private static void quickSortImpl( int[] array, int firstPos, int lastPos )
    {
        // セパレータとなる値を取得。
        int iSeparator = array[firstPos + ( ( lastPos - firstPos ) / 2 )];
        // インデックス取得。
        int iLeft = firstPos;
        int iRight = lastPos;

        // 無限ループ。
        while( true )
        {
            // 左から見て、セパレータ以上の値まで移動。
            while( array[iLeft] < iSeparator )
            {
                ++iLeft;
            }

            // 右から見て、セパレータ以下の値まで移動。
            while( iSeparator < array[iRight] )
            {
                --iRight;
            }

            if( iRight <= iLeft )
            {
                // 交差していたので抜けます。
                break;
            }

            // 入れ替え。
            int iTemp = array[iLeft];
            array[iLeft] = array[iRight];
            array[iRight] = iTemp;

            // 入れ替え箇所を飛ばすため、ひとつ進めます。
            ++iLeft;
            --iRight;
        }

        if( firstPos < iLeft - 1 )
        {
            // 左側の要素数が 1 よりも多ければ、
            // 左側を再ソートします。
            quickSortImpl( array, firstPos, iLeft - 1 );
        }

        if( iRight + 1 < lastPos )
        {
            // 右側の要素数が 1 よりも多ければ、
            // 右側を再ソートします。
            quickSortImpl( array, iRight + 1, lastPos );
        }
    }
}

// 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, 

        // クイックソートします。
        quickSort( 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 quickSort( int[] array )
    {
        // 配列の先頭と最後を渡します。
        quickSortImpl( array, 0, array.length - 1 );
    }

    /**
    *   クイックソートの実装。
    *   再帰呼び出しされます。
    */
    private static void quickSortImpl( int[] array, int firstPos, int lastPos )
    {
        // セパレータとなる値を取得。
        int iSeparator = array[firstPos + ( ( lastPos - firstPos ) / 2 )];
        // インデックス取得。
        int iLeft = firstPos;
        int iRight = lastPos;

        // 無限ループ。
        while( true )
        {
            // 左から見て、セパレータ以上の値まで移動。
            while( array[iLeft] < iSeparator )
            {
                ++iLeft;
            }

            // 右から見て、セパレータ以下の値まで移動。
            while( iSeparator < array[iRight] )
            {
                --iRight;
            }

            if( iRight <= iLeft )
            {
                // 交差していたので抜けます。
                break;
            }

            // 入れ替え。
            int iTemp = array[iLeft];
            array[iLeft] = array[iRight];
            array[iRight] = iTemp;

            // 入れ替え箇所を飛ばすため、ひとつ進めます。
            ++iLeft;
            --iRight;
        }

        if( firstPos < iLeft - 1 )
        {
            // 左側の要素数が 1 よりも多ければ、
            // 左側を再ソートします。
            quickSortImpl( array, firstPos, iLeft - 1 );
        }

        if( iRight + 1 < lastPos )
        {
            // 右側の要素数が 1 よりも多ければ、
            // 右側を再ソートします。
            quickSortImpl( array, iRight + 1, lastPos );
        }
    }
}