07/04/01 14:37:24
チラシの裏 クイックソート (C# 3.0 without LINQ)
using System;
using System.Collections.Generic;
public static class QSort {
public static IEnumerable<T> Sort<T>(IEnumerable<T> seq) where T : IComparable<T> {
return IsEmpty(seq) ? seq : Sort(Head(seq), Tail(seq));
}
static IEnumerable<T> Sort<T>(T head, IEnumerable<T> tail) where T : IComparable<T> {
return Concat(
Sort(tail.Filter(e => e.CompareTo(head) < 0)),
Lift(head),
Sort(tail.Filter(e => e.CompareTo(head) >= 0))
);
}
static bool IsEmpty<T>(IEnumerable<T> seq) {
foreach (var e in seq) {
return false;
}
return true;
}
static T Head<T>(IEnumerable<T> seq) {
foreach (var e in seq) {
return e;
}
throw new InvalidOperationException("empty sequence");
}