# A Collection of Sorts

The past few days I've posted some sorting routines customized to the tasks they were required to solve. Since I have a bunch of different sorting routines already coded, I decided to post them.

Please note that some of these sorts are fast, but not a single one is as fast as the built in Array.Sort due to these using managed code while I suspect Array.Sort uses pointers and unmanaged code.

The snippet above is the base class I use for all the sort routines to ensure that they are interchangeable. All the routines are generic sorts and will sort any array of types as long as the type implements IComparable.

Just to give some idea on how fast the various sorts are, here are some timings on sorting 20,000 integers. Times given in milliseconds:

``````Selection... -       3961
Insertion... -       2308
Quick....... -         20
Odd-Even.... -       4388
Gnome....... -       4527
Comb........ -         35
Cocktail.... -       3504
Bubble...... -       4892
Heap........ -         30
Shell....... -         26
Array.Sort.. -          5``````
jonsca commented: Great job! (beyond that, I haven't tested them yet) +7
ddanbe commented: Great stuff! +8
``````using System;

namespace Whittle.Sorting {
abstract class Sorts<T> where T : IComparable {
abstract public String Name { get; }
abstract public void Sort(T[] array);
public void Swap(T[] array, int a, int b) {
T temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
}``````
Momerath 1,327

Selection sort:

``````using System;

namespace Whittle.Sorting.Selection {
class Selection<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Selection"; }
}

override public void Sort(T[] items) {
int n = items.Length;
int iMin;

for (int i = 0; i < n; i++) {
iMin = i;
for (int j = i+1; j < n; j++) {
if (items[j].CompareTo(items[iMin]) < 0) {
iMin = j;
}
}
if (iMin != i) {
Swap(items, iMin, i);
}
}
}
}
}``````
Momerath 1,327

Insertion sort

``````using System;

namespace Whittle.Sorting.Insertion {
class Insertion<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Insertion"; }
}

override public void Sort(T[] items) {
int n = items.Length;
for (int i = 1; i < n; i++) {
T value = items[i];
int j = i - 1;
Boolean done = false;
do {
if (items[j].CompareTo(value) > 0) {
items[j + 1] = items[j];
j--;
if (j < 0) {
done = true;
}
} else {
done = true;
}
} while (done == false);
items[j + 1] = value;
}
}
}
}``````
Momerath 1,327

Quick sort

``````using System;

namespace Whittle.Sorting.Exchange {
class Quick<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Quick"; }
}

override public void Sort(T[] items) {
Quicksort(items, 0, items.Length - 1);
}

private void Quicksort(T[] array, int left, int right) {
if (right > left) {
int pivotIndex = left + (right - left) / 2;
pivotIndex = Partition(array, left, right, pivotIndex);
Quicksort(array, left, pivotIndex - 1);
Quicksort(array, pivotIndex + 1, right);
}
}

private int Partition(T[] array, int left, int right, int pivotIndex) {
T pivotValue = array[pivotIndex];
int storeIndex = left;

Swap(array, pivotIndex, right);

for (int i = left; i < right; i++) {
if (array[i].CompareTo(pivotValue) <= 0) {
Swap(array, i, storeIndex);
storeIndex++;
}
}

Swap(array, storeIndex, right);

return storeIndex;
}

}
}``````
Momerath 1,327

OddEven sort

``````using System;

namespace Whittle.Sorting.Exchange {
class OddEven<T>: Sorts<T> where T : IComparable {
override public string Name {
get { return "Odd-Even"; }
}

override public void Sort(T[] items) {
int n = items.Length;
Boolean sorted = false;
while (sorted == false) {
sorted = true;
for (int i = 1; i < n - 1; i += 2) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
sorted = false;
}
}

for (int i = 0; i < n - 1; i += 2) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
sorted = false;
}
}
}
}
}
}``````
Momerath 1,327

Gnome sort

``````using System;

namespace Whittle.Sorting.Exchange {
class Gnome<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Gnome"; }
}

override public void Sort(T[] items) {
int n = items.Length;
int pos = 1;
while (pos < n) {
if (items[pos].CompareTo(items[pos - 1]) > 0) {
pos++;
} else {
Swap(items, pos, pos - 1);
if (pos > 1) {
pos--;
} else {
pos++;
}
}
}
}
}
}``````
Momerath 1,327

Comb sort

``````using System;

namespace Whittle.Sorting.Exchange {
class Comb<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Comb"; }
}

override public void Sort(T[] items) {
double shrink_factor = 1.247330950103979;
int gap = items.Length;
bool swapped = true;
int i;

while ((gap > 1) || swapped) {
if (gap > 1) gap = (int)(gap/ shrink_factor);
swapped = false;
i = 0;
while (gap + i < items.Length) {
if (items[i].CompareTo(items[i+gap]) > 0) {
Swap(items, i, i + gap);
swapped = true;
}
i++;
}
}
}
}
}``````
Momerath 1,327

Cocktail sort

``````using System;

namespace Whittle.Sorting.Exchange {
class Cocktail<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Cocktail"; }
}

override public void Sort(T[] items) {
int begin = -1;
int end = items.Length - 2;
Boolean swapped;

do {
swapped = false;
begin++;
for (int i = begin; i <= end; i++) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
swapped = true;
}
}
if (swapped == false) {
break;
}
swapped = false;
end--;
for (int i = end; i >= begin; i--) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
swapped = true;
}
}
} while (swapped);
}
}
}``````
Momerath 1,327

Bubble sort

``````using System;

namespace Whittle.Sorting.Exchange {
class Bubble<T> :Sorts<T> where T : IComparable {
override public string Name {
get { return "Bubble"; }
}

override public void Sort(T[] items) {
int n = items.Length;
do {
int newn = 0;
for (int i = 0; i < n - 1; i++) {
if (items[i].CompareTo(items[i + 1]) > 0) {
Swap(items, i, i + 1);
newn = i + 1;
}
}
n = newn;
} while (n > 1);
}
}
}``````
Momerath 1,327

Heap Sort

``````using System;

namespace Whittle.Sorting.Selection {
class Heap<T> : Sorts<T> where T : IComparable {
public override string Name {
get { return "Heap"; }
}

public override void Sort(T[] array) {
Heapify(array, array.Length);
int end = array.Length - 1;
while (end > 0) {
Swap(array, end, 0);
SiftDown(array, 0, end - 1);
end--;
}
}

public void Heapify(T[] array, int count) {
int start = count / 2 - 1;
while (start >= 0) {
SiftDown(array, start, count - 1);
start--;
}
}

public void SiftDown(T[] array, int start, int end) {
int root = start;
while (root * 2 + 1 <= end) {
int child = root * 2 + 1;
int swap = root;
if (array[swap].CompareTo(array[child]) < 0) {
swap = child;
}
if (child < end && array[swap].CompareTo(array[child + 1]) < 0) {
swap = child + 1;
}
if (swap != root) {
Swap(array, root, swap);
root = swap;
} else {
break;
}
}
}
}
}``````
Momerath 1,327

Shell sort

``````using System;

namespace Whittle.Sorting.Insertion {
class Shell<T> : Sorts<T> where T : IComparable {
override public string Name {
get { return "Shell"; }
}

override public void Sort(T[] items) {
int n = items.Length;
int inc = n / 2;
while (inc > 0) {
for (int i = inc; i < n; i++) {
T temp = items[i];
int j = i;
while (j >= inc && items[j - inc].CompareTo(temp) > 0) {
items[j] = items[j - inc];
j -= inc;
}
items[j] = temp;
}
inc = (int)(inc / 2.2);
}
}
}
}``````
ddanbe 2,724

Great! It teaches me a lot to see your class design.
This is my own humble contribution from a time ago http://www.daniweb.com/code/snippet217212.html
My BubbleSort is a bit different and I have a sort called straight insertion sort.