スポンサーサイト
- -------- -- --:--:--
- スポンサー広告
- Comments (Close): -
- TrackBack (Close): -
選択ソート
- 2011-10-02 Sun 22:00:48
- アルゴリズム
選択ソートは、データの最小値(最大値)を選択して探索範囲の先頭(末尾)に置き、その探索範囲をだんだん狭めていくことでデータを整列する並べ替え方法です。
具体的にいうと、まず、先頭の値を最小値と仮定します。これと2番目の値を比較し、2番目の値のほうが小さければ先頭の値と交換します。このようにして先頭の値との比較を最後の要素まで繰り返していくと、先頭の値が真の最小値になります。
最小値が求まったら、2番目に小さい値を探します。2番目に格納されている要素を2番目に小さい値と仮定し、これと3番目の値を比較し、3番目の値のほうが小さければ2番目の値と交換します。このようにして2番目の値との比較を最後の要素まで繰り返していくと、2番目の値が真の2番目に小さい値になります。
以上の手続きを繰り返していくと、データが昇順に並べ替えられているはずです。
package kihon;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Sample
{
public static void main(String args[])
{
ArrayListlist=new ArrayList ();
for(int i=0; i<10; i++){
list.add(i);
}
System.out.println(list);
Collections.shuffle(list);
System.out.println(list);
selectionSort(list);
System.out.println(list);
}
staticvoid swap(List list,int index1,int index2){
T tmp=list.get(index1);
list.set(index1,list.get(index2));
list.set(index2, tmp);
}
static void selectionSort(Listlist){
for(int i=0;iint min=i;
for(int j=i+1; jif(list.get(j) swap(list,j,min);
}
}
}
}
}
最小値を設定する外ループの i の探索終了が i
なぜなら・・・
タグ :
- Comments (Close): -
- TrackBack (Close): -