The ELMO Principle - Part 2 - Sorting Algorithms

Sorting Benchmark
====================================


CPU speed 2 010 000 000 Hz


Preparing to sort 1 000 000 integers:


ArraySort sort started.
ArraySort sort completed in 	0 min 0 sec 125 ms.
Total cycles = 251 250 000, cycles/items = 251,25
Array_int_Sort sort started.
Array_int_Sort sort completed in 	0 min 0 sec 109 ms.
Total cycles = 219 843 750, cycles/items = 219,84375
BucketSort sort started.
BucketSort sort completed in 	0 min 0 sec 93 ms.
Total cycles = 188 437 500, cycles/items = 188,4375
BucketSortInplace sort started.
BucketSortInplace sort completed in 	0 min 0 sec 15 ms.
Total cycles = 31 406 250, cycles/items = 31,40625
ShellSort sort started.
ShellSort sort completed in 	10 min 19 sec 78 ms.
Total cycles = 1 244 347 031 250, cycles/items = 1244347,03125
InsertionSort sort started.
InsertionSort sort completed in 	16 min 41 sec 203 ms.
Total cycles = 2 012 418 281 250, cycles/items = 2012418,28125
BubbleSort sort started.
BubbleSort sort completed in 	59 min 48 sec 218 ms.
Total cycles = 7 212 319 687 500, cycles/items = 7212319,6875
-- All tests done --
Verify sort started.
Verify sort completed in 	0 min 0 sec 0 ms.
Total cycles = 0, cycles/items = 0
-- Everything done --

Sorting Benchmark
====================================


CPU speed 2 010 000 000 Hz


Preparing to sort 50 000 000 integers:


ArraySort sort started.
ArraySort sort completed in 	0 min 7 sec 734 ms.
Total cycles = 15 546 093 750, cycles/items = 310,921875
Array_int_Sort sort started.
Array_int_Sort sort completed in 	0 min 7 sec 828 ms.
Total cycles = 15 734 531 250, cycles/items = 314,690625
BucketSort sort started.
BucketSort sort completed in 	0 min 6 sec 93 ms.
Total cycles = 12 248 437 500, cycles/items = 244,96875
BucketSortInplace sort started.
BucketSortInplace sort completed in 	0 min 0 sec 875 ms.
Total cycles = 1 758 750 000, cycles/items = 35,175
-- All tests done --
Verify sort started.
Verify sort completed in 	0 min 0 sec 250 ms.
Total cycles = 502 500 000, cycles/items = 10,05
-- Everything done --

<code>
// Add System.Management.dll as reference
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace Sorting_ELMO
{
    class Program
    {
        public static int ArrLength = (int)1E6; // 50E6;
        public const int MaxSlowSort = (int)1E6;
        public const int MaxBigBucketSort = (int)60E6;
        public const int BiggestNum = 9;
        public static Random rand = new Random();
        public static double CPU_speed;

        public static int[] intArray;
        public static int[] refArray;

        public delegate void SortFunctionDelegate();

        [STAThread]
        static void Main(string[] args)
        {
            CPU_speed = GetCPU_speed();
            Console.WriteLine("Sorting Benchmark");
            Console.WriteLine("====================================\n\r");
            Console.WriteLine("CPU speed {0:n} Hz\n\r", CPU_speed);

            if (args.Length > 0)
            {
                try
                {
                    ArrLength = int.Parse(args[0]);
                }
                catch { }
            }
            // Fill array with random ints between 0 and 9
            intArray = new int[ArrLength];
            refArray = new int[ArrLength];

            for (int x = 0; x < ArrLength; x++)
            {
                refArray[x] = rand.Next(0, BiggestNum);
            }

            Console.WriteLine("Preparing to sort {0:n} integers:\n\r", intArray.Length);

            const int iterations = 1;
            for (int i = 0; i < iterations; i++)
            {
                SortRunner(ArraySort);
            }

            for (int i = 0; i < iterations; i++)
            {
                SortRunner(Array_int_Sort);
            }

            if (ArrLength <= MaxBigBucketSort)
            {
                for (int i = 0; i < iterations; i++)
                {
                    SortRunner(BucketSort);
                }
            }

            for (int i = 0; i < iterations; i++)
            {
                SortRunner(BucketSortInplace);
            }

            if (ArrLength <= MaxSlowSort)
            {
                for (int i = 0; i < iterations; i++)
                {
                    SortRunner(ShellSort);
                }

                for (int i = 0; i < iterations; i++)
                {
                    SortRunner(InsertionSort);
                }

                for (int i = 0; i < iterations; i++)
                {
                    SortRunner(BubbleSort);
                }
            }

            Console.WriteLine("-- All tests done --");

            // Reference-measure the Verify-part
            for (int i = 0; i < iterations; i++)
            {
                intArray.CopyTo(refArray, 0);
                SortRunner(Verify);
            }
            Console.WriteLine("-- Everything done --");
            Console.ReadKey();
        }

        static void SortRunner(SortFunctionDelegate sortFunction)
        {
            refArray.CopyTo(intArray, 0);
            string sortName = sortFunction.Method.Name;

            Console.WriteLine("{0} sort started…", sortName);
            // Stamp start time

            TimeSpan dtStart = System.Diagnostics.Process.GetCurrentProcess().TotalProcessorTime;

            sortFunction();

            // Stamp end time
            TimeSpan dtEnd = System.Diagnostics.Process.GetCurrentProcess().TotalProcessorTime;

            Verify();

            TimeSpan ts = dtEnd.Subtract(dtStart);

            Console.WriteLine("{3} sort completed in \t{0} min {1} sec {2} ms.", (int)ts.TotalMinutes, ts.Seconds, ts.Milliseconds, sortName);
            Console.WriteLine("Total cycles = {0:n}, cycles/items = {1}", CPU_speed * ts.TotalSeconds, CPU_speed * ts.TotalSeconds / (double)ArrLength);
        }

        static void ArraySort()
        {
            Array.Sort(intArray);
        }

        static void Array_int_Sort()
        {
            Array.Sort<int>(intArray);
        }

        static void BucketSort()
        {
            Dictionary<int, list<int="">> buckets = new Dictionary<int, list<int="">>();
            for (int i = 0; i < BiggestNum; i++)
            {
                buckets[i] = new List<int>();
            }

            foreach (int item in intArray)
            {
                buckets[item].Add(item);
            }

            int currArrPos = 0;
            for (int i = 0; i < BiggestNum; i++)
            {
                buckets[i].CopyTo(intArray, currArrPos);
                currArrPos += buckets[i].Count;
            }
        }

        static void BucketSortInplace()
        {
            int[] bucketLength = new int[BiggestNum];
            int[] bucketStart = new int[BiggestNum];
            int[] bucketFillCount = new int[BiggestNum];

            // First pass:
            // Count each bucket-size
            foreach (int item in intArray)
            {
                bucketLength[item]++;
            }

            // Include calculate offset including prevous buckets
            for (int i = 1; i < BiggestNum; i++)
            {
                bucketStart[i] += bucketStart[i - 1] + bucketLength[i - 1];
            }

            const int invalidMarker = -1;
            int x = intArray.Count();
            int lastElement = intArray[0];
            intArray[0] = invalidMarker;
            // Move one item at a time to the next empty place in the correct bucket.
            // Pick up the item att that place to continue with
            for (int i = 0; i < x; i++)
            {
                int currElement = lastElement;
                int currPos = bucketStart[currElement] + bucketFillCount[currElement];
                lastElement = intArray[currPos];
                intArray[currPos] = currElement;
                bucketFillCount[currElement]++;
                System.Diagnostics.Debug.Assert(bucketFillCount[currElement] <= bucketLength[currElement]);
                if (lastElement == invalidMarker)
                {
                    // If the element is put back in its original place, then find a new unsorted element to continue with
                    for (int idx = 0; idx < BiggestNum; idx++)
                    {
                        for (int j = bucketFillCount[idx]; j < bucketLength[idx]; j++)
                        {
                            int tmpElement = intArray[bucketStart[idx] + j];
                            if (tmpElement != invalidMarker)
                            {
                                lastElement = tmpElement;
                                intArray[bucketStart[idx] + j] = invalidMarker;
                                goto BreakAllFor;
                            }
                        }
                    }
                BreakAllFor: ;// Do nothing more
                    // Just a security-check, this code can be removed
#if DEBUG
                    if (lastElement == invalidMarker)
                    {
                        for (int idx = 0; idx < BiggestNum; idx++)
                        {
                            System.Diagnostics.Debug.Assert(bucketFillCount[idx] == bucketLength[idx]);
                        }
                    }
#endif
                }
            }
        }

        static void BubbleSort()
        {
            int i, j, x, iTemp;

            x = intArray.Length;

            for (i = (x - 1); i >= 0; i--)
            {
                for (j = 1; j <= i; j++)
                {
                    if (intArray[j - 1] > intArray[j])
                    {
                        iTemp = intArray[j - 1];

                        intArray[j - 1] = intArray[j];

                        intArray[j] = iTemp;
                    }
                }
            }

        }

        static void InsertionSort()
        {
            int i, j, x, index;
            x = intArray.Length;
            for (i = 1; i < x; i++)
            {
                index = intArray[i];
                j = i;

                while ((j > 0) && (intArray[j - 1] > index))
                {
                    intArray[j] = intArray[j - 1];
                    j = j - 1;
                }
                intArray[j] = index;
            }

        }

        static void ShellSort()
        {
            int i, j, inc, iTemp, x;
            x = intArray.Length;
            inc = 3;
            while (inc > 0)
            {
                for (i = 0; i < x; i++)
                {
                    j = i;
                    iTemp = intArray[i];

                    while ((j >= inc) && (intArray[j - inc] > iTemp))
                    {
                        intArray[j] = intArray[j - inc];
                        j = j - inc;
                    }
                    intArray[j] = iTemp;
                }
                if (inc / 2 != 0)
                {
                    inc = inc / 2;
                }
                else if (inc == 1)
                {
                    inc = 0;
                }
                else
                {
                    inc = 1;
                }
            }
        }

        static void Verify()
        {
            int last = -1;
            int i, x;
            x = intArray.Length;
            for (i = 0; i < x; i++)
            {
                if (intArray[i] < last)
                    Console.WriteLine("Item at index {0} was {1}, last was {2}", i, intArray[i], last);
                last = intArray[i];
            }
        }

        static double GetCPU_speed()
        {
            double ghz = 0;
            System.Management.SelectQuery q = new System.Management.SelectQuery("Win32_Processor");
            System.Management.ManagementObjectSearcher searcher = new System.Management.ManagementObjectSearcher(q);
            foreach (System.Management.ManagementObject cpu in searcher.Get())
            {
                ghz += ((UInt32)(cpu["MaxClockSpeed"]) / 1000.0);
                return ghz * 1000000000; // return speed of first CPU, not the sum as original
            }
            return ghz * 1000000000;
        }
    }
}
</int></int,></int,></int></code>