安定ソートとは : JavaA2Z

安定ソート

日本語	安定並べ替え
英語	stable sort
ふりがな	あんていそーと
フリガナ	アンテイソート

元の順序を維持したままソートすること。
ソートの方法のひとつ。
　
たとえば「名前」と「日付」を持つクラスがあるとする。このクラスの配列を「名前」でソートした場合、同じ名前のデータが複数ある場合には「元々の配列上での順序」で並べるソートが「安定ソート」である。
これは、複数の項目を順にソートする場合に重要となる。まず「日付」でソートし、次に「名前」でソートした場合、安定ソートであれば「日付」でのソート結果がそのまま残るが、安定ソートでない場合には「日付」でのソートが無視され順番が入れ替わる可能性がある。
　
このような場合、安定ソートではなく「項目に優先順位を設けて、全ての項目を比較する」方法もある。この場合では「名前でまず比較し、名前が一致したら日付でも比較する」というものである。
ところがこの方法では項目が増えることによって比較方法が膨大に増えてしまうという問題がある。
そのため、項目ごとにソートを可能にし、安定ソートでソートすることで複数項目のソートを可能にすることが多い。
　
安定ソートであるソートのひとつに「修正マージソート」がある。Arrays クラスのsort()メソッドで、クラスの配列をソートする場合にはこのアルゴリズムが使用される。
安定ソートではないソートのひとつに「クイックソート」がある。Arrays クラスのsort()メソッドで、プリミティブ型の配列をソートする場合にはこのアルゴリズムが使用されるが、プリミティブ型は「項目がひとつ」であり、安定ソートにする必要がないため問題ない。

参考サイト

J2SE Arrays

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

// Sample.java
import java.util.Arrays;
import java.util.Comparator;

public class Sample
{
    public static void main( String[] args )
    {
        // ソート対象の配列を作ります。
        // (A)同士が同じ名前、(B)同士が同じ名前。
        Data[] datas = new Data[]
            { new Data( "かきくけこ", 200 )    // (A)
            , new Data( "あいうえお", 300 )    // (B)
            , new Data( "さしすせそ", 400 )
            , new Data( "あいうえお", 100 )    // (B)
            , new Data( "かきくけこ", 500 )    // (A)
            };

        // 修正マージソートでソートします。
        Arrays.sort( datas, new DataNameComparator() );

        for( int iF1 = 0; iF1 < datas.length; ++iF1 )
        {
            System.out.println( datas[iF1] );
        }
        // さしすせそ:400
        // かきくけこ:200
        // かきくけこ:500
        // あいうえお:300
        // あいうえお:100

        // このように、nameが同じ要素は、numがソート前の順番を
        // そのまま維持しています。
    }
}

/**
*   ソート対象のクラス。
*/
class Data
{
    // 注：ここではpublicフィールドにしますが、
    // 皆さんはお行儀よくprivateフィールドにしてsetter/getterを
    // 作りましょう。

    public String name = "";
    public int num = 0;

    /**
    *   コンストラクタ。
    */
    public Data( String name, int num )
    {
        this.name = name;
        this.num = num;
    }

    /**
    *   toString()のオーバーライド。
    */
    public String toString()
    {
        return name + ":" + num;
    }
}

/**
*   Dataクラスを名前でソートするためのComparator。
*/
class DataNameComparator implements Comparator
{
    public int compare( Object lh, Object rh )
    {
        Data iL = (Data)lh;
        Data iR = (Data)rh;
        // Dataとして取得してそのnameフィールドのcompareTo()の結果を
        // そのまま使用します。
        return -( iL.name.compareTo( iR.name ) );
    }
}

// Sample.java
import java.util.Arrays;
import java.util.Comparator;

public class Sample
{
    public static void main( String[] args )
    {
        // ソート対象の配列を作ります。
        // (A)同士が同じ名前、(B)同士が同じ名前。
        Data[] datas = new Data[]
            { new Data( "かきくけこ", 200 )    // (A)
            , new Data( "あいうえお", 300 )    // (B)
            , new Data( "さしすせそ", 400 )
            , new Data( "あいうえお", 100 )    // (B)
            , new Data( "かきくけこ", 500 )    // (A)
            };

        // 修正マージソートでソートします。
        Arrays.sort( datas, new DataNameComparator() );

        for( int iF1 = 0; iF1 < datas.length; ++iF1 )
        {
            System.out.println( datas[iF1] );
        }
        // さしすせそ:400
        // かきくけこ:200
        // かきくけこ:500
        // あいうえお:300
        // あいうえお:100

        // このように、nameが同じ要素は、numがソート前の順番を
        // そのまま維持しています。
    }
}

/**
*   ソート対象のクラス。
*/
class Data
{
    // 注：ここではpublicフィールドにしますが、
    // 皆さんはお行儀よくprivateフィールドにしてsetter/getterを
    // 作りましょう。

    public String name = "";
    public int num = 0;

    /**
    *   コンストラクタ。
    */
    public Data( String name, int num )
    {
        this.name = name;
        this.num = num;
    }

    /**
    *   toString()のオーバーライド。
    */
    public String toString()
    {
        return name + ":" + num;
    }
}

/**
*   Dataクラスを名前でソートするためのComparator。
*/
class DataNameComparator implements Comparator
{
    public int compare( Object lh, Object rh )
    {
        Data iL = (Data)lh;
        Data iR = (Data)rh;
        // Dataとして取得してそのnameフィールドのcompareTo()の結果を
        // そのまま使用します。
        return -( iL.name.compareTo( iR.name ) );
    }
}