Searching and Sorting Algorithms via C#
Searching and Sorting Algorithms via C#
Introduction and References
This article will focus on the sorting and searching algorithms enabled via the .NET Framework's Class Library. As such, it assumes that the reader have a working knowledge of generics. The FCL provides several classes, called collections, which are used to store groups of related objects. Along with methods for organizing, storing, and retrieving data, these classes provides methods for sorting and searching. Consider the generic List
A sorting algorithm is essentially a sort of cookbook containing code instructions for organizing the elements of a list into a well-defined numerical or alphabetical order. A list is an abstract concept consisting of a finite collection of fixed-length entities that can be arranged either in random order or in an increasing or decreasing sequential order. In actual practice, technical documentation asserts that a list is usually expressed in the form of an array or a more advanced data structure such as a linked list. If we are sorting data, we are obviously inputting unsorted data into the computational model. The output is sorted data. Let’s look at a basic example of a C# algorithm called BubbleSort:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; public class Program { public static void bubbleSort1(ref int[] x) { bool exchanges; do { exchanges = false; for (int i = 0; i < x.Length - 1; i++) { if (x[i] > x[i + 1]) { // Exchange elements int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; exchanges = true; } } } while (exchanges); } public static void DisplayElements(ref int[] xArray, char status, string sortname) { if (status == 'a') Console.WriteLine("After sorting using algorithm: " + sortname); else Console.WriteLine("Before sorting"); for (int i = 0; i <= xArray.Length - 1; i++) { if ((i != 0) && (i % 10 == 0)) Console.Write("\n"); Console.Write(xArray[i] + " "); } Console.ReadLine(); } static void MixDataUp(ref int[] x, Random rdn) { for (int i = 0; i <= x.Length - 1; i++) { x[i] = (int)(rdn.NextDouble() * x.Length); } } public static void Main(string[] args) { Console.WriteLine("Sorting Algorithms Demo Code\n\n"); const int nItems = 20; Random rdn = new Random(nItems); int[] xdata = new int[nItems]; MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); Console.WriteLine(); bubbleSort1(ref xdata); DisplayElements(ref xdata, 'a', "bubbleSort1"); Console.WriteLine("\n\n"); Console.WriteLine("Press Enter to Exit..."); } }
Admittedly, the amount of data in this example is very small. The example code, however, is meant to demonstrate how it works. Take a look at the output:
Sorting Algorithms Demo Code Before sorting 3 13 14 16 4 0 17 9 9 12 0 1 7 17 19 10 5 7 4 1 After sorting using algorithm: bubbleSort1 0 0 1 1 3 4 4 5 7 7 9 9 10 12 13 14 16 17 17 19 Press Enter to Exit...
Bubble sort works by stepping through the entire list to be sorted while comparing two items at a time and swapping their positions if they are found to be in the wrong order. This process is repeated until no swaps are needed thereby indicating that the list has been sorted. The algorithm gets its name from the way smaller elements seem to bubble to the top of the list. In fact, one of the many performance problems with the Bubble sort algorithm is that it is inefficient with large amounts of data. MIT Open Course Ware offers a course on Algorithms and insists that a major part of algorithm design is performance analysis. Here is another example of the BubbleSort algorithm:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; public class Program { public static void bubbleSort2(ref int[] x) { for (int pass = 1; pass < x.Length - 1; pass++) { // Count how many times this next loop // becomes shorter and shorter for (int i = 0; i < x.Length - pass; i++) { if (x[i] > x[i + 1]) { // Exchange elements int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; } } } } public static void DisplayElements(ref int[] xArray, char status, string sortname) { if (status == 'a') Console.WriteLine("After sorting using algorithm: " + sortname); else Console.WriteLine("Before sorting"); for (int i = 0; i <= xArray.Length - 1; i++) { if ((i != 0) && (i % 10 == 0)) Console.Write("\n"); Console.Write(xArray[i] + " "); } Console.ReadLine(); } static void MixDataUp(ref int[] x, Random rdn) { for (int i = 0; i <= x.Length - 1; i++) { x[i] = (int)(rdn.NextDouble() * x.Length); } } public static void Main(string[] args) { Console.WriteLine("Sorting Algorithms Demo Code\n\n"); const int nItems = 20; Random rdn = new Random(nItems); int[] xdata = new int[nItems]; MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); Console.WriteLine(); bubbleSort2(ref xdata); DisplayElements(ref xdata, 'a', "bubbleSort2"); Console.WriteLine("\n\n"); Console.WriteLine("Press Enter to Exit..."); } }
Notice the output. It is relatively the same, but coded differently to make it more efficient with the 20 data elements:
Sorting Algorithms Demo Code Before sorting 3 13 14 16 4 0 17 9 9 12 0 1 7 17 19 10 5 7 4 1 After sorting using algorithm: bubbleSort2 0 0 1 1 3 4 4 5 7 7 9 9 10 12 13 14 16 17 17 19 Press Enter to Exit...
The Cocktail sort, also known as the Bi-directional Bubble sort, is just another slightly improved variation of the fundamental Bubble sort algorithm. The difference between the Cocktail and the Bubble sort algorithms is that instead of repeatedly iterating through an input list from bottom to top, the Cocktail sort iterates alternating from bottom to top and then from top to bottom. By performing bidirectional iterations, the Cocktail sort can achieve a slightly better performance time than the standard Bubble sort algorithm which only iterates through the input list in one direction and therefore can only reposition items by one step per iteration. Here is an example of the Cocktail sort algorithm:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; public class Program { public static void CocktailSort(ref int[] x) { for (int k = x.Length - 1; k > 0; k--) { bool swapped = false; for (int i = k; i > 0; i--) if (x[i] < x[i - 1]) { // swap int temp = x[i]; x[i] = x[i - 1]; x[i - 1] = temp; swapped = true; } for (int i = 0; i < k; i++) if (x[i] > x[i + 1]) { // swap int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; swapped = true; } if (!swapped) break; } } public static void DisplayElements(ref int[] xArray, char status, string sortname) { if (status == 'a') Console.WriteLine("After sorting using algorithm: " + sortname); else Console.WriteLine("Before sorting"); for (int i = 0; i <= xArray.Length - 1; i++) { if ((i != 0) && (i % 10 == 0)) Console.Write("\n"); Console.Write(xArray[i] + " "); } Console.ReadLine(); } static void MixDataUp(ref int[] x, Random rdn) { for (int i = 0; i <= x.Length - 1; i++) { x[i] = (int)(rdn.NextDouble() * x.Length); } } public static void Main(string[] args) { const int nItems = 50; Random rdn = new Random(nItems); int[] xdata = new int[nItems]; MixDataUp(ref xdata, rdn); Console.WriteLine(); DisplayElements(ref xdata, 'b', ""); Console.WriteLine(); CocktailSort(ref xdata); DisplayElements(ref xdata, 'a', "CocktailSort"); Console.WriteLine("\n\n"); } }
Here is the output of the different approach. Notice that again we use a method that mixes up the data, displays the data, calls the sorting algorithm, and displays the results:
Before sorting Before sorting 42 24 35 11 39 12 15 26 8 35 6 25 0 24 49 12 44 49 1 33 23 5 22 24 30 34 46 33 17 17 32 31 20 12 5 46 22 22 45 17 44 30 36 46 13 41 17 12 1 41 After sorting using algorithm: CocktailSort 0 1 1 5 5 6 8 11 12 12 12 12 13 15 17 17 17 17 20 22 22 22 23 24 24 24 25 26 30 30 31 32 33 33 34 35 35 36 39 41 41 42 44 44 45 46 46 46 49 49
The downloadable zip file contains the above sorting examples, along with a plethora of other sorting algorithms and searching algorithms. Describing them all would be out of the scope of this article. At this point, we should consider searching algorithms.
Searching Algorithms
Linear search is a search algorithm, also known as sequential search, that is apt for searching a list of data for a particular value. It operates by checking every element of a list one at a time in sequence until a match is found.
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; public class Program { public static int LinearSearch(ref int[] x, int valueToFind) { for (int i = 0; i < x.Length; i++) { if (valueToFind == x[i]) { return i; } } return -1; } public static void DisplayElements(ref int[] xArray, char status, string sortname) { if (status == 'a') Console.WriteLine("After sorting using algorithm: " + sortname); else Console.WriteLine("Before sorting"); for (int i = 0; i <= xArray.Length - 1; i++) { if ((i != 0) && (i % 10 == 0)) Console.Write("\n"); Console.Write(xArray[i] + " "); } Console.ReadLine(); } static void MixDataUp(ref int[] x, Random rdn) { for (int i = 0; i <= x.Length - 1; i++) { x[i] = (int)(rdn.NextDouble() * x.Length); } } public static void Main(string[] args) { const int nItems = 20; Random rdn = new Random(nItems); int[] xdata = new int[nItems]; MixDataUp(ref xdata, rdn); //Randomize data to be searched DisplayElements(ref xdata, 'b', ""); //Display random data Console.WriteLine("Using LINEAR SEARCH ALGORITHM to look for 4th data entry in randomized list"); int location = LinearSearch(ref xdata, xdata[4]); //Look for the 4th data entry in the list if (location == -1) Console.WriteLine("Value was not found in list"); else Console.WriteLine("Found it at location = {0}", location); location = LinearSearch(ref xdata, 19); //Look for the number 19 in the list. if (location == -1) Console.WriteLine("Value of 19 was not found in list"); else Console.WriteLine("Value of 19 was found at location = {0}", location); Console.WriteLine("\n\n"); } }
Here is the output:
Before sorting 3 13 14 16 4 0 17 9 9 12 0 1 7 17 19 10 5 7 4 1 Using LINEAR SEARCH ALGORITHM to look for 4th data entry in randomized list Found it at location = 4 Value of 19 was found at location = 14
Recall that an array, as signified by brackets [], is normally zero-based. That is, if there are [4] elements, then they are 0, 1,2, and 3. Check this by verifying the location in the output of the code shown above. Now, let’s take a look at code that consolidates the entire solution file:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; public class Program { #region Bubble Sorts public static void bubbleSort1(ref int[] x) { bool exchanges; do { exchanges = false; for (int i = 0; i < x.Length - 1; i++) { if (x[i] > x[i + 1]) { // Exchange elements int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; exchanges = true; } } } while (exchanges); } public static void bubbleSort2(ref int[] x) { for (int pass = 1; pass < x.Length - 1; pass++) { // Count how many times this next loop // becomes shorter and shorter for (int i = 0; i < x.Length - pass; i++) { if (x[i] > x[i + 1]) { // Exchange elements int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; } } } } public static void bubbleSort3(ref int[] x) { bool exchanges; int n = x.Length; do { n--; // Make loop smaller each time. // and assume this is last pass over array exchanges = false; for (int i = 0; i < x.Length - 1; i++) { if (x[i] > x[i + 1]) { // Exchange elements int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; exchanges = true; } } } while (exchanges); } public static void bubbleSortRange(ref int[] x) { int lowerBound = 0; // First position to compare. int upperBound = x.Length - 1; // First position NOT to compare. int n = x.Length - 1; // Continue making passes while there is a potential exchange. while (lowerBound <= upperBound) { int firstExchange = n; // assume impossibly high index for low end. int lastExchange = -1; // assume impossibly low index for high end. // Make a pass over the appropriate range. for (int i = lowerBound; i < upperBound; i++) { if (x[i] > x[i + 1]) { // Exchange elements int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; // Remember first and last exchange indexes. if (i < firstExchange) { // True only for first exchange. firstExchange = i; } lastExchange = i; } } //--- Prepare limits for next pass. lowerBound = firstExchange - 1; if (lowerBound < 0) { lowerBound = 0; } upperBound = lastExchange; } } #endregion #region Cocktail Sort public static void CocktailSort(ref int[] x) { for (int k = x.Length - 1; k > 0; k--) { bool swapped = false; for (int i = k; i > 0; i--) if (x[i] < x[i - 1]) { // swap int temp = x[i]; x[i] = x[i - 1]; x[i - 1] = temp; swapped = true; } for (int i = 0; i < k; i++) if (x[i] > x[i + 1]) { // swap int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; swapped = true; } if (!swapped) break; } } #endregion #region Odd Even Sort public static void OddEvenSort(ref int[] x) { int temp; for (int i = 0; i < x.Length / 2; ++i) { for (int j = 0; j < x.Length - 1; j += 2) { if (x[j] > x[j + 1]) { temp = x[j]; x[j] = x[j + 1]; x[j + 1] = temp; } } for (int j = 1; j < x.Length - 1; j += 2) { if (x[j] > x[j + 1]) { temp = x[j]; x[j] = x[j + 1]; x[j + 1] = temp; } } } } #endregion #region Comb Sort public static int newGap(int gap) { gap = gap * 10 / 13; if (gap == 9 || gap == 10) gap = 11; if (gap < 1) return 1; return gap; } public static void CombSort(ref int[] x) { int gap = x.Length; bool swapped; do { swapped = false; gap = newGap(gap); for (int i = 0; i < (x.Length - gap); i++) { if (x[i] > x[i + gap]) { swapped = true; int temp = x[i]; x[i] = x[i + gap]; x[i + gap] = temp; } } } while (gap > 1 || swapped); } #endregion #region Gnome Sort public static void GnomeSort(ref int[] x) { int i = 0; while (i < x.Length) { if (i == 0 || x[i - 1] <= x[i]) i++; else { int temp = x[i]; x[i] = x[i - 1]; x[--i] = temp; } } } #endregion #region Insertion Sort public static void InsertionSort(ref int[] x) { int n = x.Length - 1; int i, j, temp; for (i = 1; i <= n; ++i) { temp = x[i]; for (j = i - 1; j >= 0; --j) { if (temp < x[j]) x[j + 1] = x[j]; else break; } x[j + 1] = temp; } } #endregion #region Quick Sort public static void QuickSort(ref int[] x) { qs(x, 0, x.Length - 1); } public static void qs(int[] x, int left, int right) { int i, j; int pivot, temp; i = left; j = right; pivot = x[(left + right) / 2]; do { while ((x[i] < pivot) && (i < right)) i++; while ((pivot < x[j]) && (j > left)) j--; if (i <= j) { temp = x[i]; x[i] = x[j]; x[j] = temp; i++; j--; } } while (i <= j); if (left < j) qs(x, left, j); if (i < right) qs(x, i, right); } #endregion #region Shell Sort public static void ShellSort(ref int[] x) { int i, j, temp; int increment = 3; while (increment > 0) { for (i = 0; i < x.Length; i++) { j = i; temp = x[i]; while ((j >= increment) && (x[j - increment] > temp)) { x[j] = x[j - increment]; j = j - increment; } x[j] = temp; } if (increment / 2 != 0) { increment = increment / 2; } else if (increment == 1) { increment = 0; } else { increment = 1; } } } #endregion #region Selection Sort public static void SelectionSort(ref int[] x) { int i, j; int min, temp; for (i = 0; i < x.Length - 1; i++) { min = i; for (j = i + 1; j < x.Length; j++) { if (x[j] < x[min]) { min = j; } } temp = x[i]; x[i] = x[min]; x[min] = temp; } } #endregion #region Merge Sort public static void MergeSort(ref int[] x, int left, int right) { if (left < right) { int middle = (left + right) / 2; MergeSort(ref x, left, middle); MergeSort(ref x, middle + 1, right); Merge(ref x, left, middle, middle + 1, right); } } public static void Merge(ref int[] x, int left, int middle, int middle1, int right) { int oldPosition = left; int size = right - left + 1; int[] temp = new int[size]; int i = 0; while (left <= middle && middle1 <= right) { if (x[left] <= x[middle1]) temp[i++] = x[left++]; else temp[i++] = x[middle1++]; } if (left > middle) for (int j = middle1; j <= right; j++) temp[i++] = x[middle1++]; else for (int j = left; j <= middle; j++) temp[i++] = x[left++]; Array.Copy(temp, 0, x, oldPosition, size); } #endregion #region Bucket Sort public static void BucketSort(ref int[] x) { //Verify input if (x == null || x.Length <= 1) return; //Find the maximum and minimum values in the array int maxValue = x[0]; int minValue = x[0]; for (int i = 1; i < x.Length; i++) { if (x[i] > maxValue) maxValue = x[i]; if (x[i] < minValue) minValue = x[i]; } //Create a temporary "bucket" to store the values in order //each value will be stored in its corresponding index //scooting everything over to the left as much as possible (minValue) LinkedList<int>[] bucket = new LinkedList<int>[maxValue - minValue + 1]; //Move items to bucket for (int i = 0; i < x.Length; i++) { if (bucket[x[i] - minValue] == null) bucket[x[i] - minValue] = new LinkedList<int>(); bucket[x[i] - minValue].AddLast(x[i]); } //Move items in the bucket back to the original array in order int k = 0; //index for original array for (int i = 0; i < bucket.Length; i++) { if (bucket[i] != null) { LinkedListNode<int> node = bucket[i].First; //start add head of linked list while (node != null) { x[k] = node.Value; //get value of current linked node node = node.Next; //move to next linked node k++; } } } } #endregion #region Heap Sort public static void Heapsort(ref int[] x) { int i; int temp; int n = x.Length; for (i = (n / 2) - 1; i >= 0; i--) { siftDown(ref x, i, n); } for (i = n - 1; i >= 1; i--) { temp = x[0]; x[0] = x[i]; x[i] = temp; siftDown(ref x, 0, i - 1); } } public static void siftDown(ref int[] x, int root, int bottom) { bool done = false; int maxChild; int temp; while ((root * 2 <= bottom) && (!done)) { if (root * 2 == bottom) maxChild = root * 2; else if (x[root * 2] > x[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (x[root] < x[maxChild]) { temp = x[root]; x[root] = x[maxChild]; x[maxChild] = temp; root = maxChild; } else { done = true; } } } #endregion #region Count Sort public static void Count_Sort(ref int[] x) { try { int i = 0; int k = FindMax(x); //Finds max value of input array // output array holds the sorted output int[] output = new int[x.Length]; // provides temperarory storage int[] temp = new int[k + 1]; for (i = 0; i < k + 1; i++) { temp[i] = 0; } for (i = 0; i < x.Length; i++) { temp[x[i]] = temp[x[i]] + 1; } for (i = 1; i < k + 1; i++) { temp[i] = temp[i] + temp[i - 1]; } for (i = x.Length - 1; i >= 0; i--) { output[temp[x[i]] - 1] = x[i]; temp[x[i]] = temp[x[i]] - 1; } for (i = 0; i < x.Length; i++) { x[i] = output[i]; } } catch (System.Exception e) { Console.WriteLine(e.ToString()); Console.ReadLine(); } } #endregion #region Radix Sort //RadixSort takes an array and the number of bits used as //the key in each iteration. public static void RadixSort(ref int[] x, int bits) { //Use an array of the same size as the original array //to store the result of each iteration. int[] b = new int[x.Length]; int[] b_orig = b; //Mask is the bitmask used to extract the sort key. //We start with the bits least significant bits and //left-shift it the same amount at each iteration. //When all the bits are shifted out of the word, we are done. int rshift = 0; for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits) { //An array is needed to store the count for each key value. int[] cntarray = new int[1 << bits]; //Count each key value for (int p = 0; p < x.Length; ++p) { int key = (x[p] & mask) >> rshift; ++cntarray[key]; } //Sum up how many elements there are with lower //key values, for each key. for (int i = 1; i < cntarray.Length; ++i) cntarray[i] += cntarray[i - 1]; //The values in cntarray are used as indexes //for storing the values in b. b will then be //completely sorted on this iteration's key. //Elements with the same key value are stored //in their original internal order. for (int p = x.Length - 1; p >= 0; --p) { int key = (x[p] & mask) >> rshift; --cntarray[key]; b[cntarray[key]] = x[p]; } //Swap the a and b references, so that the //next iteration works on the current b, //which is now partially sorted. int[] temp = b; b = x; x = temp; } } #endregion #region Linear Search public static int LinearSearch(ref int[] x, int valueToFind) { for (int i = 0; i < x.Length; i++) { if (valueToFind == x[i]) { return i; } } return -1; } #endregion #region Binary Search public static int BinSearch(ref int[] x, int searchValue) { // Returns index of searchValue in sorted array x, or -1 if not found int left = 0; int right = x.Length; return binarySearch(ref x, searchValue, left, right); } public static int binarySearch(ref int[] x, int searchValue, int left, int right) { if (right < left) { return -1; } int mid = (left + right) >> 1; if (searchValue > x[mid]) { return binarySearch(ref x, searchValue, mid + 1, right); } else if (searchValue < x[mid]) { return binarySearch(ref x, searchValue, left, mid - 1); } else { return mid; } } #endregion #region Interpolation Search public static int InterpolationSearch(ref int[] x, int searchValue) { // Returns index of searchValue in sorted input data // array x, or -1 if searchValue is not found int low = 0; int high = x.Length - 1; int mid; while (x[low] < searchValue && x[high] >= searchValue) { mid = low + ((searchValue - x[low]) * (high - low)) / (x[high] - x[low]); if (x[mid] < searchValue) low = mid + 1; else if (x[mid] > searchValue) high = mid - 1; else return mid; } if (x[low] == searchValue) return low; else return -1; // Not found } #endregion #region Nth Largest public static int NthLargest1(int[] array, int n) { //Copy input data array into a temporary array //so that original array is unchanged int[] tempArray = new int[array.Length]; array.CopyTo(tempArray, 0); //Sort the array QuickSort(ref tempArray); //Return the n-th largest value in the sorted array return tempArray[tempArray.Length - n]; } public static int NthLargest2(int[] array, int k) { int maxIndex; int maxValue; //Copy input data array into a temporary array //so that original array is unchanged int[] tempArray = new int[array.Length]; array.CopyTo(tempArray, 0); for (int i = 0; i < k; i++) { maxIndex = i; // index of minimum element maxValue = tempArray[i];// assume minimum is the first array element for (int j = i + 1; j < tempArray.Length; j++) { // if we've located a higher value if (tempArray[j] > maxValue) { // capture it maxIndex = j; maxValue = tempArray[j]; } } Swap(ref tempArray[i], ref tempArray[maxIndex]); } return tempArray[k - 1]; } #endregion #region Mth Smallest public static int MthSmallest1(int[] array, int m) { //Copy input data array into a temporary array //so that original array is unchanged int[] tempArray = new int[array.Length]; array.CopyTo(tempArray, 0); //Sort the array QuickSort(ref tempArray); //Return the m-th smallest value in the sorted array return tempArray[m - 1]; } public static int MthSmallest2(int[] array, int m) { int minIndex; int minValue; //Copy input data array into a temporary array //so that original array is unchanged int[] tempArray = new int[array.Length]; array.CopyTo(tempArray, 0); for (int i = 0; i < m; i++) { minIndex = i; // index of minimum element minValue = tempArray[i];// assume minimum is the first array element for (int j = i + 1; j < array.Length; j++) { if (tempArray[j] < minValue) { // capture it minIndex = j; minValue = tempArray[j]; } } Swap(ref tempArray[i], ref tempArray[minIndex]); } return tempArray[m - 1]; } #endregion #region Miscellaneous Utilities public static int FindMax(int[] x) { int max = x[0]; for (int i = 1; i < x.Length; i++) { if (x[i] > max) max = x[i]; } return max; } public static int FindMin(int[] x) { int min = x[0]; for (int i = 1; i < x.Length; i++) { if (x[i] < min) min = x[i]; } return min; } static void MixDataUp(ref int[] x, Random rdn) { for (int i = 0; i <= x.Length - 1; i++) { x[i] = (int)(rdn.NextDouble() * x.Length); } } static void Swap(ref int left, ref int right) { int temp = left; left = right; right = temp; } // Determines if int array is sorted from 0 -> Max public static bool IsSorted(int[] arr) { for (int i = 1; i < arr.Length; i++) { if (arr[i - 1] > arr[i]) { return false; } } return true; } // Determines if string array is sorted from A -> Z public static bool IsSorted(string[] arr) { for (int i = 1; i < arr.Length; i++) { if (arr[i - 1].CompareTo(arr[i]) > 0) // If previous is bigger, return false { return false; } } return true; } // Determines if int array is sorted from Max -> 0 public static bool IsSortedDescending(int[] arr) { for (int i = arr.Length - 2; i >= 0; i--) { if (arr[i] < arr[i + 1]) { return false; } } return true; } // Determines if string array is sorted from Z -> A public static bool IsSortedDescending(string[] arr) { for (int i = arr.Length - 2; i >= 0; i--) { if (arr[i].CompareTo(arr[i + 1]) < 0) // If previous is smaller, return false { return false; } } return true; } public static void DisplayElements(ref int[] xArray, char status, string sortname) { if (status == 'a') Console.WriteLine("After sorting using algorithm: " + sortname); else Console.WriteLine("Before sorting"); for (int i = 0; i <= xArray.Length - 1; i++) { if ((i != 0) && (i % 10 == 0)) Console.Write("\n"); Console.Write(xArray[i] + " "); } Console.ReadLine(); } #endregion static void Main(string[] args) { Console.WriteLine("Sorting Algorithms Demo Code\n\n"); const int nItems = 20; Random rdn = new Random(nItems); int[] xdata = new int[nItems]; MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); bubbleSort1(ref xdata); DisplayElements(ref xdata, 'a', "bubbleSort1"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); bubbleSort2(ref xdata); DisplayElements(ref xdata, 'a', "bubbleSort2"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); bubbleSort3(ref xdata); DisplayElements(ref xdata, 'a', "bubbleSort3"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); bubbleSortRange(ref xdata); DisplayElements(ref xdata, 'a', "bubbleSortRange"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); CocktailSort(ref xdata); DisplayElements(ref xdata, 'a', "CocktailSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); OddEvenSort(ref xdata); DisplayElements(ref xdata, 'a', "OddEvenSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); CombSort(ref xdata); DisplayElements(ref xdata, 'a', "CombSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); GnomeSort(ref xdata); DisplayElements(ref xdata, 'a', "GnomeSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); InsertionSort(ref xdata); DisplayElements(ref xdata, 'a', "InsertionSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); QuickSort(ref xdata); DisplayElements(ref xdata, 'a', "QuickSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); ShellSort(ref xdata); DisplayElements(ref xdata, 'a', "ShellSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); SelectionSort(ref xdata); DisplayElements(ref xdata, 'a', "SelectionSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); MergeSort(ref xdata, 0, xdata.Length - 1); DisplayElements(ref xdata, 'a', "MergeSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); BucketSort(ref xdata); DisplayElements(ref xdata, 'a', "BucketSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); Heapsort(ref xdata); DisplayElements(ref xdata, 'a', "HeapSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); Count_Sort(ref xdata); DisplayElements(ref xdata, 'a', "CountSort"); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); int bits = 4; RadixSort(ref xdata, bits); DisplayElements(ref xdata, 'a', "RadixSort"); Console.WriteLine("\n\n"); //The search tests that follow are divided into two steps //(1) Tries to find the 4th data entry in a randomized list. //Since this data value always exist, the result will always be successful //(2) Tries to find a numerical value of 100 in a randomized list. //Since this data value is beyond the maximum value that the random generator is setup //to produce, the result will always fail. This way all possible outcomes are fully checked. //Note that the linear search strategy is the out method that accepts randomized data. //For all other searches, the data must be sorted first. Console.WriteLine("Search Algorithms Demo Code\n\n"); MixDataUp(ref xdata, rdn); //Randomize data to be searched DisplayElements(ref xdata, 'b', ""); //Display random data Console.WriteLine("Using LINEAR SEARCH ALGORITHM to look for 4th data entry in randomized list"); int location = LinearSearch(ref xdata, xdata[4]); //Look for the 4th data entry in the list if (location == -1) Console.WriteLine("Value was not found in list"); else Console.WriteLine("Found it at location = {0}", location); location = LinearSearch(ref xdata, 100); //Look for the number 100 in the list. if (location == -1) Console.WriteLine("Value of 100 was not found in list"); else Console.WriteLine("Value of 100 was found at at location = {0}", location); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); //Display random data QuickSort(ref xdata); Console.WriteLine("Using INTERPOLATION SEARCH ALGORITHM to look for 4th data entry in randomized list"); location = InterpolationSearch(ref xdata, xdata[4]); if (location == -1) Console.WriteLine("Value was not found in list"); else Console.WriteLine("Found it at location = {0}", location); location = InterpolationSearch(ref xdata, 100); if (location == -1) Console.WriteLine("Value of 100 was not found in list"); else Console.WriteLine("Value of 100 was found at at location = {0}", location); Console.WriteLine("\n\n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); //Display random data QuickSort(ref xdata); Console.WriteLine("Using BINARY SEARCH ALGORITHM to look for 4th data entry in randomized list"); location = BinSearch(ref xdata, xdata[4]); if (location == -1) Console.WriteLine("Value was not found in list"); else Console.WriteLine("Found it at location = {0}", location); location = InterpolationSearch(ref xdata, 100); if (location == -1) Console.WriteLine("Value of 100 was not found in list"); else Console.WriteLine("Value of 100 was found at at location = {0}", location); Console.WriteLine("\n\n"); //The ArrayList collection in C# comes with its own built-in search algorithm. //And can be called up to perform a search as shown below. MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); //Display random data Console.WriteLine("Using the built-in BINARY SEARCH ALGORITHM in ArrayList data structure"); ArrayList alist = new ArrayList(); //Set up an ArrayList object for (int i = 0; i < xdata.Length; i++) alist.Add(xdata[i]); //and add some radomized data to it location = alist.BinarySearch(xdata[4]); //Call up its BinarySearch method if (location == -1) //and run the examples Console.WriteLine("Value was not found in list"); else Console.WriteLine("Found it at location = {0}", location); location = alist.BinarySearch(100); if (location < 0) Console.WriteLine("Value was not found in list"); else Console.WriteLine("Found it at location = {0}", location); Console.WriteLine("Testing to find the n-th largest value in a random array\n\nOriginal Data (method 1): \n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); int nthMathIndex1 = 8; int nthMaxValue1 = NthLargest1(xdata, nthMathIndex1); Console.WriteLine("\nThe " + nthMathIndex1 + " largest value in the array above is: " + nthMaxValue1 + "\n"); Console.WriteLine("Verifying result... \nFirst verify that original data array is not changed.\n"); DisplayElements(ref xdata, 'b', ""); Console.WriteLine("\nThen sort the array and count the requested position from the largest value at the top\n"); QuickSort(ref xdata); DisplayElements(ref xdata, 'a', "QuickSort"); ////// Console.WriteLine("\n\nTesting to find the n-th largest value in a random array\n\nOriginal Data (method 2): \n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); int nthMathIndex2 = 4; int nthMinValue2 = NthLargest2(xdata, nthMathIndex2); Console.WriteLine("\nThe " + nthMathIndex2 + " largest value in the array above is: " + nthMinValue2 + "\n"); Console.WriteLine("Verifying result... \nFirst verify that original data array is not changed.\n"); DisplayElements(ref xdata, 'b', ""); Console.WriteLine("\nThen sort the array and count the requested position from the smallest value at the bottom\n"); QuickSort(ref xdata); DisplayElements(ref xdata, 'a', "QuickSort"); Console.WriteLine("\n\nTesting to find the m-th smallest value in a random array\n\nOriginal Data (method 1): \n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); int mthMathIndex1 = 3; int mthMinValue1 = MthSmallest1(xdata, mthMathIndex1); Console.WriteLine("\nThe " + mthMathIndex1 + " smallest value in the array above is: " + mthMinValue1 + "\n"); Console.WriteLine("Verifying result... \nFirst verify that original data array is not changed.\n"); DisplayElements(ref xdata, 'b', ""); Console.WriteLine("\nThen sort the array and count the requested position from the smallest value at the bottom\n"); QuickSort(ref xdata); DisplayElements(ref xdata, 'a', "QuickSort"); Console.WriteLine("\n\nTesting to find the m-th smallest value in a random array\n\nOriginal Data (method 2): \n"); MixDataUp(ref xdata, rdn); DisplayElements(ref xdata, 'b', ""); int mthMathIndex2 = 3; int mthMinValue2 = MthSmallest2(xdata, mthMathIndex2); Console.WriteLine("\nThe " + mthMathIndex2 + " smallest value in the array above is: " + mthMinValue2 + "\n"); Console.WriteLine("Verifying result... \nFirst verify that original data array is not changed.\n"); DisplayElements(ref xdata, 'b', ""); Console.WriteLine("\nThen sort the array and count the requested position from the smallest value at the bottom\n"); QuickSort(ref xdata); DisplayElements(ref xdata, 'a', "QuickSort"); Console.WriteLine("\n\nTesting sorting utitlities\n"); int[] sortedInts = new int[] { 1, 5, 20, 50 }; int[] unsortedInts = new int[] { 35, 2, 56, 1 }; int[] reversedInts = new int[] { 10, 9, 8, 7 }; string[] sortedStrings = new string[] { "monkey", "duck", "bird" }; string[] unsortedStrings = new string[] { "duck", "monkey", "dog" }; string[] reversedStrings = new string[] { "dog", "duck", "monkey" }; Console.WriteLine(IsSorted(sortedInts)); // True Console.WriteLine(IsSortedDescending(sortedInts)); // False Console.WriteLine(IsSorted(unsortedInts)); // False Console.WriteLine(IsSortedDescending(unsortedInts)); // False Console.WriteLine(IsSorted(reversedInts)); // False Console.WriteLine(IsSortedDescending(reversedInts)); // True Console.WriteLine(IsSorted(sortedStrings)); // True Console.WriteLine(IsSortedDescending(sortedStrings)); // False Console.WriteLine(IsSorted(unsortedStrings)); // False Console.WriteLine(IsSortedDescending(unsortedStrings)); // False Console.WriteLine(IsSorted(reversedStrings)); // False Console.WriteLine(IsSortedDescending(reversedStrings)); // True Console.ReadLine(); Console.WriteLine("\n\nTesting Conversion from List to Array\n"); List<string> myList = new List<string>(); myList.Add("dog"); myList.Add("cat"); myList.Add("duck"); myList.Add("monkey"); myList.Add("bird"); string[] myString = myList.ToArray(); foreach (string s in myString) Console.WriteLine(s); Console.WriteLine("\n\nTesting Conversion from Array to List\n"); string[] str = new string[] { "duck", "cat", "dog", "monkey", "bird" }; List<string> myOtherList = new List<string>(str); myOtherList = str.ToList(); foreach (string s in myOtherList) Console.WriteLine(s); Console.ReadLine(); } } </string></string></string></string></int></int></int></int>
The single most important purpose of learning algorithms is to be able to code them to work with large amounts of data to solve problems. The code shown above was not coded using data parallelism. Perhaps it could be an exercise to the reader to find parallelizable “hotspots” and use the appropriate Task Parallel Library construct on them.
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架