ソートアルゴリズム(1)

ソートアルゴリズムを紹介していきます。

整数を整列するソートアルゴリズムには様々なものがあり、それぞれのアルゴリズムには利点と欠点があります。

今回はバブルソートを紹介します。

バブルソートは隣接する要素を比較し入れ替えることでソートを行うアルゴリズムです。計算量はO(n^2)であり効率はよくありませんがアルゴリズムはシンプルで実装は容易です。

以下はJavaによる整数のリストを昇順に並べ替えるバブルソートアルゴリズムの実装例です。

sort/BubbleSort.java

package sort;

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class BubbleSort {

  private static void swap(List list, int idx1, int idx2) {
    Integer t = list.get(idx1);
    list.set(idx1, list.get(idx2));
    list.set(idx2, t);
  }

  public static void sort(List list) {
    for (int i = list.size() - 1; i > 0; i--) {
      for (int j = 0; j < i; j++) {
	if (list.get(j) > list.get(j + 1)) {
	  swap(list, j, j + 1);
	}
      }
    }
  }

  public static void main(String[] args) {
    List  list = new ArrayList();
    for (int i = 0; i < 10; i++) {
      list.add(i);
    }
    Collections.shuffle(list);
    System.out.println(list);
    sort(list);
    System.out.println(list);
  }
}

1番目の要素と2番目の要素を比較し、順番が逆であれば要素を入れ替えます。
次に、2番目の要素と3番目の要素を比較し、順番が逆であれば要素を入れ替えます。
これを最後まで繰り返していくと一番最後の要素には整数リストの中で最も大きい数値が格納されます。
さらに、最後の要素を除いた範囲で上記の処理を繰り返していくことで整数リストの末尾の方から整列されていきます。

2009年9月1日 | カテゴリー：アルゴリズム