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

今回はシェーカーソートを紹介します。

シェーカーソートは前回紹介したバブルソートを改善したものです。 バブルソートで隣接する要素を比較していくときにすで順番に並んでいる部分を検出した場合にはその部分をソート済みにすることで性能を上げています。 またバブルソードでは一方向からのみ走査していましたがシェーカーソートでは走査を毎回反転することで反対側からもソート済み部分を検出することができます。

以下はJavaによる実装例です。

sort/ShakerSort.java

package sort;

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

public class ShakerSort {

    public static void swap(List list, int index1, int index2) {
        E t = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, t);
    }

    public static void sort(List list) {
        int start = 0, end = list.size() - 1;
        int lastSwap = start;
        int inc = 1;
        while (true) {
            for (int i = lastSwap; i < end; i++) {
                if (list.get(i).compareTo(list.get(i + 1)) > 0) {
                    swap(list, i, i + 1);
                    lastSwap = i;
                }
            }
            end = lastSwap;
            if (start >= end) break;
            System.out.println(list);

            for (int i = lastSwap; i > start; i--) {
                if (list.get(i).compareTo(list.get(i - 1)) < 0) {
                    swap(list, i, i - 1);
                    lastSwap = i;
                }
            }
            start = lastSwap;
            if (start >= end) break;
            System.out.println(list);
        }
    }

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

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