Commits

OJ Reeves  committed 1efddf3

Added sample code for multithreading.

  • Participants
  • Parent commits 2ce1713

Comments (0)

Files changed (1)

File 01-BubbleSort/BubbleSort-CSharp/Program.cs

 using System;
+using System.Threading;
 
 namespace BubbleSort_CSharp
 {
+    class BubbleSortThreadParam
+    {
+        public int[] dataSet;
+        public int startIndex;
+        public int endIndex;
+
+        public BubbleSortThreadParam(int[] dataSet, int startIndex, int endIndex)
+        {
+            this.dataSet = dataSet;
+            this.startIndex = startIndex;
+            this.endIndex = endIndex;
+        }
+    }
+
     class Program
     {
         /// <summary>
         /// <param name="args">Command line arguments.</param>
         static void Main(string[] args)
         {
+            SortSync();
+            SortAsync();
+        }
+
+        /// <summary>
+        /// Demonstrates the Bubble Sort in a synchronous fashion across
+        /// the entire array.
+        /// </summary>
+        static void SortSync()
+        {
             int[] dataSet = new int[] { 33, 98, 74, 13, 55, 20, 77, 45, 64, 83 };
-
-            Display(dataSet);
-
-            // pick any of the following implementations
-            //BubbleSortBasic(dataSet);
-            //BubbleSortBasicOptimised(dataSet);
             BubbleSort(dataSet);
             Display(dataSet);
         }
 
         /// <summary>
-        /// This is the basic bubble sort algorithm, hard-coded to work
-        /// with integer values.
+        /// Demonstrates the Bubble Sort across two threads.
         /// </summary>
-        /// <param name="dataSet">Array of integers to sort.</param>
-        static void BubbleSortBasic(int[] dataSet)
+        static void SortAsync()
         {
-            // loop n-1 times.
-            for (int i = dataSet.Length - 1; i > 0 ; --i)
-            {
-                // for each loop, iterate through the first i
-                // items (ie. the unsorted ones)
-                for (int j = 0; j < i; ++j)
-                {
-                    // if adjacent items need to be swapped
-                    if (dataSet[j] > dataSet[j + 1])
-                    {
-                        // swap them
-                        Swap(dataSet, j, j + 1);
-                    }
-                }
-            }
+            int[] dataSet = new int[] { 33, 98, 74, 13, 55, 20, 77, 45, 64, 83 };
+
+            // create a thread for the first section
+            ParameterizedThreadStart pst = new ParameterizedThreadStart(BubbleSortAsync);
+            Thread thread = new Thread(pst);
+
+            // kick the thread off
+            thread.Start(new BubbleSortThreadParam(dataSet, 0, 4));
+
+            // use the main thread for the second section
+            BubbleSort(dataSet, 5, 9);
+
+            // wait for the first thread to finish
+            thread.Join();
+
+            // show the interim results
+            Display(dataSet);
+
+            // combine the results
+            int[] results = CombineResults(dataSet, 2);
+
+            // show the final result
+            Display(results);
         }
 
         /// <summary>
-        /// This is the basic bubble sort algorithm, hard-coded to work
-        /// with integer values but with a slight difference - a minor
-        /// optimisation.
+        /// Combines the results from an async sort.
         /// </summary>
-        /// <param name="dataSet">Array of integers to sort.</param>
-        static void BubbleSortBasicOptimised(int[] dataSet)
+        /// <param name="dataSet">The set of items to combine.</param>
+        /// <param name="setCount">The number of sets the data was broken
+        /// <returns>The new combined set.</returns>
+        /// into prior to sorting.</param>
+        /// <remarks>It's assumed that setCount is a factor of dataSet.Length.</remarks>
+        static int[] CombineResults(int[] dataSet, int setCount)
         {
-            // loop n-1 times.
-            for (int i = dataSet.Length - 1; i > 0 ; --i)
+            int[] results = new int[dataSet.Length];
+            int[] setIndex = new int[setCount];
+            int setOffset = dataSet.Length / setCount;
+            int resultIndex = 0;
+
+            // initialise counters
+            for(int set = 0; set < setCount; ++set)
             {
-                // keep track of whether items were swapped
-                // for this iteration
-                bool swapped = false;
+                setIndex[set] = set * setOffset;
+            }
 
-                // for each loop, iterate through the first i
-                // items (ie. the unsorted ones)
-                for (int j = 0; j < i; ++j)
+            // rebuild the array in order
+            while (resultIndex < dataSet.Length)
+            {
+                int? nextSmallest = null;
+                int? setUsed = null;
+
+                // iterate through the sets
+                for (int set = 0; set < setCount; ++set)
                 {
-                    // if adjacent items need to be swapped
-                    if (dataSet[j] > dataSet[j + 1])
+                    // make sure we haven't gone through the whole
+                    // set before we check indices
+                    if(setIndex[set] < ((set + 1) * setOffset))
                     {
-                        // swap them
-                        Swap(dataSet, j, j + 1);
-
-                        // indicate that we found a swap
-                        swapped = true;
+                        // if no value has been stored yet, or the value at
+                        // the start of this set is smaller than the one
+                        // we've found..
+                        if (!nextSmallest.HasValue || dataSet[setIndex[set]] < nextSmallest.Value)
+                        {
+                            // store the details of the number we'll use.
+                            nextSmallest = dataSet[setIndex[set]];
+                            setUsed = set;
+                        }
                     }
                 }
 
-                // if nothing was swapped, then we should
-                // already have everything in order
-                if (!swapped)
-                {
-                    break;
-                }
+                // whack the found number in the result set.
+                results[resultIndex++] = nextSmallest.Value;
+
+                // increment in the index for the set that we've used
+                ++setIndex[setUsed.Value];
             }
+
+            // return the resulting combination
+            return results;
         }
 
         /// <summary>
         /// the individual items are comparable.</remarks>
         static void BubbleSort<T>(T[] dataSet) where T : IComparable
         {
-            // loop n-1 times.
-            for (int i = dataSet.Length - 1; i > 0 ; --i)
+            BubbleSort(dataSet, 0, dataSet.Length - 1);
+        }
+
+        /// <summary>
+        /// "Funnell" function which invokes the BubbleSort.
+        /// </summary>
+        /// <param name="param">Reference to the bubble sort params.</param>
+        static void BubbleSortAsync(object param)
+        {
+            BubbleSortThreadParam p = param as BubbleSortThreadParam;
+            BubbleSort(p.dataSet, p.startIndex, p.endIndex);
+        }
+
+        /// <summary>
+        /// A version of bubblesort that sorts a subset of elements in the array.
+        /// </summary>
+        /// <typeparam name="T">A comparable type.</typeparam>
+        /// <param name="dataSet">Array of those comparable types.</param>
+        /// <param name="startIndex">The index of the start of this subset.</param>
+        /// <param name="endIndex">The index of the end of this subset.</param>
+        /// <remarks>Both startIndex and endIndex are inclusive indices.</remarks>
+        static void BubbleSort<T>(T[] dataSet, int startIndex, int endIndex) where T : IComparable
+        {
+            for (int i = endIndex; i > startIndex ; --i)
             {
                 // keep track of whether items were swapped
                 // for this iteration
 
                 // for each loop, iterate through the first i
                 // items (ie. the unsorted ones)
-                for (int j = 0; j < i; ++j)
+                for (int j = startIndex; j < i; ++j)
                 {
                     // if adjacent items need to be swapped
                     if(dataSet[j].CompareTo(dataSet[j + 1]) > 0)