Windows 2008 R2Windows 2008Windows VistaWindows 7Visual Studio 2008Visual Studio 2010C# 3.5C# 3.0C# 4.0IntermediateDevVisual StudioWindowsC#
Searching and Sorting Algorithms via C#
4.67/5 (11 votes)
An article that details coding algorithms with 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 has 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<T> class found in the System.Collections.Generic namespace and the ArrayList class found in the System.Collections namespace. Both of these classes have properties that are very similar to C# arrays and, in addition, also come with their own methods for performing efficient sorting and searching. However, one key advantage of using collection classes over conventional arrays is that collections can dynamically grow and shrink as their number of elements change. Arrays, on the other hand, do not automatically adjust their size at runtime to accommodate changes in their initial number of allotted elements unless the one writing the code manually codes in a new array or uses the array class' Resize method. Note that the referenced material contained within this article was obtained from the book "Numerical Methods, Algorithms, and Tools in C#", written by Waldemar Dos Passos, CRC Press.
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 Bubble Sort:
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 Bubble Sort 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");
//Look for the 4th data entry in the list
int location = LinearSearch(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 = 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");
//Look for the 4th data entry in the list
int location = LinearSearch(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 = 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();
}
}
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.