JavaA2Z

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

安定ソート

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

解説

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

参考サイト


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

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

// 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() );

        forint 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 ) );
    }
}

この単語を含むページ

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

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

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