A Collection of Sorts

Momerath 3 825 Views

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
kvprajapati commented: helpful :) +12 
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;
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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);
                }
            }
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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;
            }
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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

    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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;
                    }
                }
            }
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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++;
                    }
                }
            }
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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++;
                }
            }
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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);
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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);
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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;
                }
            }
        }
    }
}
Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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);
            }
        }
    }
}
Member Avatar for ddanbe
ddanbe 2,724 Professional Procrastinator

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. :)

Member Avatar for Momerath
Momerath 1,327 Nearly a Senior Poster

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 by Momerath because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview