今回はストランドソートを解説します。

ストランドソートは前回解説したマージソートと同じマージ系と呼ばれるソートアルゴリズムです。

マージソートではソートされていないリストを2分割してマージソートを再帰呼び出しして、ソートされたサブリストをマージするアルゴリズムでした。

ストランドソートでは、リストからソートされたサブリストを抽出し、結果リストにマージしていくことでソートします。

sort/StrandSort.java

package sort;

import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Collections;

public class StrandSort {

private static <E extends Comparable<E>> List<E> merge(List<E> list1,
    List<E> list2) 
    ListIterator<E> iter1 = list1.listIterator();
    ListIterator<E> iter2 = list2.listIterator();
    List<E> result = new LinkedList<E>();
    if (!iter1.hasNext()) {
      return list2;
    }
    if (!iter2.hasNext()) {
      return list1;
    }
    E item1 = iter1.next();
    E item2 = iter2.next();
    for (;;) {
      if (item1.compareTo(item2) < 0) {
         result.add(item1);
         if (iter1.hasNext()) {
           item1 = iter1.next();
         } else {
           result.add(item2);
           while (iter2.hasNext()) {
             result.add(iter2.next());
           }
           break;
         }
      } else {
        result.add(item2);
        if (iter2.hasNext()) {
        item2 = iter2.next();
        } else {
          result.add(item1);
          while (iter1.hasNext()) {
            result.add(iter1.next());
          }
          break;
        }
      }
    }
    return result;
  }

  private static <E extends Comparable <E>> List<E> subList(List<E> list) {
    ListIterator<E> iter = list.listIterator();
    if (!iter.hasNext()) {
      return Collections.<E>emptyList();
    }

    List<E> result = new LinkedList<E>();
    E max = iter.next();
    iter.remove();
    result.add(max);
    while (iter.hasNext()) {
      E tmp = iter.next();
      if (tmp.compareTo(max) > 0) {
        iter.remove();
        result.add(max = tmp);
      }
    }
    return result;
  }

  public static <E extends Comparable<E>>  List<E> sort(List<E> list) {
    List<E> result = new LinkedList<E>();
    while (!list.isEmpty()) {
      result = merge(result, subList(list));
    }
    return result;
  }

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