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

Edited 5 Years Ago by Momerath: Added timings

Comments
helpful :)
Great stuff!
Great job! (beyond that, I haven't tested them yet)
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;
        }
    }
}

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);
                }
            }
        }
    }
}

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;
            }
        }
    }
}

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;
        }

    }
}

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;
                    }
                }
            }
        }
    }
}

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++;
                    }
                }
            }
        }
    }
}

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++;
                }
            }
        }
    }
}

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);
        }
    }
}

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);
        }
    }
}

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;
                }
            }
        }
    }
}

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);
            }
        }
    }
}

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.
Maybe you could add them to your collection.
I found it always fun to know how these things work, but as your testdata show, if you really want to sort .NET is way ahead. :)

Your bubble sort is an unoptimized bubble sort, so it's not much different.

The two insertions sorts are basically the same. The difference being that yours starts from the beginning of the array to find where to place the item (then pushes all the items down) while mine starts at the end (effectively) and moves each item until it finds the spot where the new item should go.

Edited 5 Years Ago by Momerath: n/a

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.