Motivation
Wikipedia explains it very nicely: sorting is ubiquitous in Computer Sciences. It is a simple problem (“How can I sort the following values the most efficiently?”) that has many solutions, but still offers open problems.
We only consider correct algorithms, i.e., one where their output is such that
- each element is larger than or equal to the previous one, according to the order picked,
- all the elements that were in the input are present in the output (with the same cardinality, if repetition is allowed).
There are many ways of “comparing” sorting algorithms. A sorting algorithm…
- has a best, worst and average case time complexity (measured in general in number of comparisons required),
- has a best, worst and average case space complexity (i.e., “how much additional memory is required?”),
- can be “stable” (i.e., equal values are not permutted),
- uses insertion, exchange, selection, merging method,
- is serial or parallel,
among other properties.
Insertion Sort Algorithm
This algorithm is nicely explained and illustrated on wikipedia, and can be implemented as follows:
public static void InsertionSort(List<T> listP)
{
int swapOperations = 0;
// Can be ignored, is simply here
// to count number of time we
// swap values.
Console.WriteLine("----------- Insertion Sort -------");
Displaying<T>.DisplayHeader(listP, 0, listP.Count);
T current;
int slot;
for (int bar = 1; bar < listP.Count; bar++)
{
current = listP[bar];
for (slot = bar; slot > 0 && current.CompareTo(listP[slot - 1]) < 0; slot--)
{
swapOperations++;
listP[slot] = listP[slot - 1];
}
listP[slot] = current;
}
Displaying<T>.Display(listP);
Console.WriteLine("Count = {0}", swapOperations);
}Heapsort Algorithm
We first define some helper methods:
private static void Swap(List<T> listP, int lhs, int rhs)
{
T temp = listP[lhs];
listP[lhs] = listP[rhs];
listP[rhs] = temp;
}
private static int LeftChild(int i)
{
return 2 * i + 1;
}and then leverage the heap structure to sort:
public static void Heapsort(List<T> listP)
{
Console.WriteLine(" --- Starting HeapSort ----");
Heapsort(listP, listP.Count);
}
private static void Heapsort(List<T> listP, int N)
{
Displaying<T>.DisplayHeader(listP, 0, listP.Count);
Displaying<T>.Display(listP);
for (int i = N / 2; i >= 0; i--) /* BuildHeap */
PercDown(listP, i, N);
Console.WriteLine("-- Max Heap is built --");
Displaying<T>.Display(listP);
for (int i = N - 1; i > 0; i--)
{
Swap(listP, 0, i); /* DeleteMax */
PercDown(listP, 0, i);
Displaying<T>.Display(listP);
}
}
private static void PercDown(List<T> listP, int i, int N)
{
int Child;
T current;
for (current = listP[i]; LeftChild(i) < N; i = Child)
{
Child = LeftChild(i);
if (Child != N - 1 && listP[Child].CompareTo(listP[Child + 1]) < 0)
Child++;
if (current.CompareTo(listP[Child]) < 0) // current < listP[child]
listP[i] = listP[Child];
else
// if current >= listP[child] we *do not*
// swap: we are constructing a *max* heap!
break;
}
listP[i] = current;
}Note that PercDown builds a max heap: once the values are
“pre-sorted greater value first”, removing the first one to move it
to the end of the list makes the list sorted from smallest to greatest
value once we are done.