ソートとは : JavaA2Z

ソート

日本語	並べ替え
英語	sort
ふりがな	そーと
フリガナ	ソート

配列やコレクションを特定の順番で並べ替えること。
配列やコレクションの各要素を、特定のルールを元に並び替えることを「ソートする」という。
　
基本的には、要素と要素を比較し、「小さい方」と「大きい方」に分け、それを全ての要素に対して行うことで並び替える。
一般的に、小さい方から大きい方へと並べることを「昇順」、大きい方から小さい方へと並べることを「降順」と呼ぶ。
また、比較時に「一致」した場合に、ソート前の並び順をそのまま維持するソート方法を「安定ソート」と呼ぶ。
　
要素と要素の比較を行う際に、全ての要素をベタに比較するとそれだけ時間が掛かる。
だが、実際には総当たり的に比較を行う必要はなく、様々な方法が編み出されている。これらはソートのアルゴリズムとしてプログラムに組むことができる。
　
Javaでは、ソートは基本的にArrays クラスのsort()メソッドを使用する。
sort()メソッドは、プリミティブ型の場合はクイックソートで、クラスの場合には修正マージソートを使用する。どちらも最速レベルのアルゴリズムであり、修正マージソートは「安定ソート」のため、よほどの理由がない限りsort()メソッドを使用してソートした方が良い。自分で新たにソートを行うプログラムを作るのはやめた方がいいだろう。
クラスの場合、Comparable インターフェイスの実装クラスでないとそのままsort()メソッドに使用することはできない。Comparable インターフェイスの実装クラスでない場合には、sort()メソッドの第2引数にComparator インターフェイス実装クラスの実装クラスを渡す必要がある。

参考サイト

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

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

public class Sample
{
    public static void main( String[] args )
    {
        // int型の配列を用意します。
        int[] ints = new int[] { 300, 100, 200 };
        // ソート機能を使ってみます。
        Arrays.sort( ints );
        // ソートされたので出力してみます。
        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 100, 200, 300,

        // クラスでも、Comparableインターフェイスの実装クラスは
        // 同じようにArrays.sort()メソッドでソートできます。
        // Integerで試します。IntegerはComparableインターフェイスから
        // implementsしています。
        Integer[] intgerss = new Integer[] { new Integer( 3000 ), new Integer( 1000 ), new Integer( 2000 ) };
        // ソート機能を使ってみます。
        Arrays.sort( intgerss );
        // ソートされたので出力してみます。
        for( int iF1 = 0; iF1 < intgerss.length; ++iF1 )
        {
            System.out.print( intgerss[iF1] + ", " );
        }
        System.out.println();
        // 1000, 2000, 3000,

        // Comparableインターフェイスの実装クラスでない場合
        // そのままではソートできません。
        StringBuffer[] strbufs = new StringBuffer[] { new StringBuffer( "CCC" ), new StringBuffer( "AAA" ), new StringBuffer( "BBB" ) };
        try
        {
            Arrays.sort( strbufs );
        }
        catch( ClassCastException e )
        {
            e.printStackTrace();
            // java.lang.ClassCastException
            //     at java.util.Arrays.mergeSort(Arrays.java:1122)
            //     at java.util.Arrays.sort(Arrays.java:1073)
            //     at Sample.main(Sample.java:41)
        }

        // 専用のComparatorインターフェイス実装クラスを作れば
        // ソートできます。
        Arrays.sort( strbufs, new StringBufferComparator() );
        for( int iF1 = 0; iF1 < strbufs.length; ++iF1 )
        {
            System.out.print( strbufs[iF1].toString() + ", " );
        }
        System.out.println();
        // AAA, BBB, CCC,
    }
}

/**
*   StringBuffer用Comparator。
*/
class StringBufferComparator implements Comparator
{
    public int compare( Object lh, Object rh )
    {
        StringBuffer strbufL = (StringBuffer)lh;
        StringBuffer strbufR = (StringBuffer)rh;
        // Stringとして取得してそのcompareTo()の結果を
        // そのまま使用します。
        return strbufL.toString().compareTo( strbufR.toString() );
    }
}

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

public class Sample
{
    public static void main( String[] args )
    {
        // int型の配列を用意します。
        int[] ints = new int[] { 300, 100, 200 };
        // ソート機能を使ってみます。
        Arrays.sort( ints );
        // ソートされたので出力してみます。
        for( int iF1 = 0; iF1 < ints.length; ++iF1 )
        {
            System.out.print( ints[iF1] + ", " );
        }
        System.out.println();
        // 100, 200, 300, 

        // クラスでも、Comparableインターフェイスの実装クラスは
        // 同じようにArrays.sort()メソッドでソートできます。
        // Integerで試します。IntegerはComparableインターフェイスから
        // implementsしています。
        Integer[] intgerss = new Integer[] { new Integer( 3000 ), new Integer( 1000 ), new Integer( 2000 ) };
        // ソート機能を使ってみます。
        Arrays.sort( intgerss );
        // ソートされたので出力してみます。
        for( int iF1 = 0; iF1 < intgerss.length; ++iF1 )
        {
            System.out.print( intgerss[iF1] + ", " );
        }
        System.out.println();
        // 1000, 2000, 3000, 

        // Comparableインターフェイスの実装クラスでない場合
        // そのままではソートできません。
        StringBuffer[] strbufs = new StringBuffer[] { new StringBuffer( "CCC" ), new StringBuffer( "AAA" ), new StringBuffer( "BBB" ) };
        try
        {
            Arrays.sort( strbufs );
        }
        catch( ClassCastException e )
        {
            e.printStackTrace();
            // java.lang.ClassCastException
            //     at java.util.Arrays.mergeSort(Arrays.java:1122)
            //     at java.util.Arrays.sort(Arrays.java:1073)
            //     at Sample.main(Sample.java:41)
        }

        // 専用のComparatorインターフェイス実装クラスを作れば
        // ソートできます。
        Arrays.sort( strbufs, new StringBufferComparator() );
        for( int iF1 = 0; iF1 < strbufs.length; ++iF1 )
        {
            System.out.print( strbufs[iF1].toString() + ", " );
        }
        System.out.println();
        // AAA, BBB, CCC, 
    }
}

/**
*   StringBuffer用Comparator。
*/
class StringBufferComparator implements Comparator
{
    public int compare( Object lh, Object rh )
    {
        StringBuffer strbufL = (StringBuffer)lh;
        StringBuffer strbufR = (StringBuffer)rh;
        // Stringとして取得してそのcompareTo()の結果を
        // そのまま使用します。
        return strbufL.toString().compareTo( strbufR.toString() );
    }
}

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

「解説」に含まれているページ

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

users

update:2005/04/05

このページは、Javaプログラミング言語についての用語を網羅した辞書「JavaA2Z」の一ページです。
詳しくは「JavaA2Z」表紙の説明をご覧ください。