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

今回紹介するソートアルゴリズムは奇遇転置ソートです。このソートはバブルソートを改良したアルゴリズムで、ソートではスキャンを順番に行っていましたが、奇遇転置ソートでは2つずつペアで比較を行います。

リストの奇数番目の要素とその次の偶数番目の要素を比較し、順番に並んでいなければ入れ替える。
(リストのすべてのペアでこれを行う。)
リストの偶数番目の要素とその次の奇数番目の要素を比較し、順番に並んでいなければ入れ替える。
(リストのすべてのペアでこれを行う。)
リストが整列されるまで1. 2. を繰り返す。

OddEvenTranspositionSort.java

package sort;

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

public class OddEvenTranspositionSort {
  private static <E extends Comparable<E>> boolean scanPair(List<E> list, int start) {
  boolean swapped = false;
    for (int i = start; i < list.size() - 1; i += 2) {
      if (list.get(i).compareTo(list.get(i + 1)) > 0) {

      }
    }
    return swapped;
  }

  public static<E extends Comparable<E>> void sort(List<E> list) {
    for (int start = 0; scanPair(list, start); start ^= 1);
  }

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

EeBlog(テクニカルブログ)

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