Functional Quicksort and Mergesort
Here's a linked list with quicksort and mergesort methods written in a functional style:
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);
}
}
Functional heapsort using a Pairing Heap
Bonus: heapsort (using functional pairing heap).
class List
{
// ...
public static Heap List2Heap(List xs)
{
if (xs == null) return null;
else return Heap.Merge(new Heap(null, xs.item, null), List2Heap(xs.rest));
}
public static List HSort(List xs)
{
return Heap.Heap2List(List2Heap(xs));
}
}
class Heap
{
Heap left;
int min;
Heap right;
public Heap(Heap left, int min, Heap right)
{
this.left = left;
this.min = min;
this.right = right;
}
public static Heap Merge(Heap a, Heap b)
{
if (a == null) return b;
if (b == null) return a;
Heap smaller = a.min <= b.min ? a : b;
Heap larger = a.min <= b.min ? b : a;
return new Heap(smaller.left, smaller.min, Merge(smaller.right, larger));
}
public static Heap DeleteMin(Heap a)
{
return Merge(a.left, a.right);
}
public static List Heap2List(Heap a)
{
if (a == null) return null;
else return new List(a.min, Heap2List(DeleteMin(a)));
}
}
For actual use you want to rewrite the helper methods without using recursion, and maybe use a mutable list like the built-in one.
How to use:
List xs = new List(4, new List(2, new List(3, new List(1, null))));
Console.WriteLine(List.Show(List.QSort(xs)));
Console.WriteLine(List.Show(List.MSort(xs)));
Console.WriteLine(List.Show(List.HSort(xs)));
Imperative In-place Quicksort for linked lists
An in-place version was requested. Here's a very quick implementation. I wrote this code top to bottom without looking for opportunities to make the code better, i.e. every line is the first line that came to mind. It's extremely ugly because I used null as the empty list :) The indentation is inconsistent, etc.
Additionally I tested this code on only one example:
MList ys = new MList(4, new MList(2, new MList(3, new MList(1, null))));
MList.QSortInPlace(ref ys);
Console.WriteLine(MList.Show(ys));
Magically it worked the first time! I'm pretty sure that this code contains bugs though. Don't hold me accountable.
class MList
{
public int item;
public MList rest;
public MList(int item, MList rest)
{
this.item = item;
this.rest = rest;
}
public static void QSortInPlace(ref MList xs)
{
if (xs == null) return;
int pivot = xs.item;
MList pivotNode = xs;
xs = xs.rest;
pivotNode.rest = null;
// partition the list into two parts
MList smaller = null; // items smaller than pivot
MList larger = null; // items larger than pivot
while (xs != null)
{
var rest = xs.rest;
if (xs.item < pivot) {
xs.rest = smaller;
smaller = xs;
} else {
xs.rest = larger;
larger = xs;
}
xs = rest;
}
// sort the smaller and larger lists
QSortInPlace(ref smaller);
QSortInPlace(ref larger);
// append smaller + [pivot] + larger
AppendInPlace(ref pivotNode, larger);
AppendInPlace(ref smaller, pivotNode);
xs = smaller;
}
public static void AppendInPlace(ref MList xs, MList ys)
{
if(xs == null){
xs = ys;
return;
}
// find the last node in xs
MList last = xs;
while (last.rest != null)
{
last = last.rest;
}
last.rest = ys;
}
public static string Show(MList xs)
{
if (xs == null) return "";
else return xs.item.ToString() + " " + Show(xs.rest);
}
}
