Sortowanie LinkedList
class List
{
public int item;
public List rest;
public List(int item, List rest)
{
this.item = item;
this.rest = rest;
}
// helper methods for quicksort
public static List Append(List xs, List ys)
{
if (xs == null) return ys;
else return new List(xs.item, Append(xs.rest, ys));
}
public static List Filter(Func<int,bool> p, List xs)
{
if (xs == null) return null;
else if (p(xs.item)) return new List(xs.item, Filter(p, xs.rest));
else return Filter(p, xs.rest);
}
public static List QSort(List xs)
{
if (xs == null) return null;
else
{
int pivot = xs.item;
List less = QSort(Filter(x => x <= pivot, xs.rest));
List more = QSort(Filter(x => x > pivot, xs.rest));
return Append(less, new List(pivot, more));
}
}
// Helper methods for mergesort
public static int Length(List xs)
{
if (xs == null) return 0;
else return 1 + Length(xs.rest);
}
public static List Take(int n, List xs)
{
if (n == 0) return null;
else return new List(xs.item, Take(n - 1, xs.rest));
}
public static List Drop(int n, List xs)
{
if (n == 0) return xs;
else return Drop(n - 1, xs.rest);
}
public static List Merge(List xs, List ys)
{
if (xs == null) return ys;
else if (ys == null) return xs;
else if (xs.item <= ys.item) return new List(xs.item, Merge(xs.rest, ys));
else return new List(ys.item, Merge(xs, ys.rest));
}
public static List MSort(List xs)
{
if (Length(xs) <= 1) return xs;
else
{
int len = Length(xs) / 2;
List left = MSort(Take(len, xs));
List right = MSort(Drop(len, xs));
return Merge(left, right);
}
}
public static string Show(List xs)
{
if(xs == null) return "";
else return xs.item.ToString() + " " + Show(xs.rest);
}
}
Gifted Gnat