What's Here?

Members: 84,852
Replies: 353,526
Topics: 51,568
Snippets: 1,757
Tutorials: 418
Total Online: 1,745
Members: 45
Guests: 1,700

C# Tutorials

Welcome to Dream.In.Code
	Getting C# Help is Easy! Join 84,852 C# Programmers. There are 1,745 online right now! Ask your question and get quick answers from Dream.In.Code experts. Join the #1 programming help community on the internet! Registration is fast and FREE... Join Now! Chat LIVE With a C# Expert Powered by LivePerson.com Register to Make This Box Go Away!

Searching and sorting arrays in C#

Searching and sorting arrays in C#

Options

PsychoCoder
Group Icon

17 Mar, 2008 - 06:23 PM

Post #1

In this tutorial we will be looking at working with Arrays in C#. In my time as a .Net developer I have been asked many times, and seen many questions in online programming forums, how to accomplish certain tasks when working with arrays, such as a bubble sort, selection sort and many searching questions, that is the reason I decided to write this tutorial. For some, especially new programmers, working with and manipulating arrays can seem like a daunting task. I will cover several functions used for working with arrays, functions like:

Linear Search of an array
Binary search of an array
Selection sort on an array
Bubble sort of an array
Find the smallest & largest value in an array

The code I am providing in this tutorial is tested and tried, and it is also very well commented to make it easier for the newer programmers to read it and see what is going on. Working with arrays, like I stated before, can seem like a very daunting task for new programmers. That really couldn't be further from the truth, yes it can take some time to get the hang of, but all it takes is practice, and understanding how looping structures in an array work. That is what I will be demonstrating in this tutorial, so lets get to some code.

The code offered here was originally written for a console application, but can easily be ported over to a Windows application, the logic for each method is the same. As with any .Net application we need to make sure we have references to the proper Namespaces so we have access to what we need. For this particular console application we only need 3 Namespaces

So lets bring in our references

csharp

Search An Array

For these examples we will be using integer arrays, but the logic is the same for strings and other data types. First we will look at a couple methods for searching for values in an array. The first method is doing a Linear Search. Here we will prompt the user for the size they want their array. From there we will ask them for the values in their array, with each value provided we will loop the size of the array, checking for numeric values.

Once all their values are in the array we will then ask them what value to search for, also checking to make sure they provided a numeric value. From there we will check each value of the array, in the order it was provided, looking for a match. If we find a match we let them know the location in the array where the match was found (the array index), otherwise we let them know the value wasn't found:

csharp

/// <summary> /// method to perform a linear search /// </summary> public static void LinearSearch() { //create an array to hold our integer array int[] numArray = new int[100]; //variable to determine if value is numeric bool isNum = false; //variable to hold the array size int sizeNum; //ask the user for array size Console.WriteLine("Enter array size"); //read in the value string sizeString = Console.ReadLine(); //use TryParse to check if user entered numeric value isNum = Int32.TryParse(sizeString, out sizeNum); //check value for true/false if (isNum) { //user entered umeric value so ask for array elements Console.WriteLine("-------------------------"); Console.WriteLine("\n Enter array items (numeric only) \n"); //now we loop (size of the array) and grab each element for (int i = 0; i < sizeNum; i++) { int tempNum; //read in each value 1 at a time string elements = Console.ReadLine(); //use TryParse to check for numeric values isNum = Int32.TryParse(elements, out tempNum); if (isNum) { //user entered numeric value so add to our array numArray[i] = tempNum; } else { Console.WriteLine("You entered a non-numeric value!"); break; } } //ask the user for their search value Console.WriteLine("-------------------------"); Console.WriteLine("Enter Search value (numeric only)\n"); //read in the value string searchString = Console.ReadLine(); //check for numeric value int searchNum; isNum = Int32.TryParse(searchString, out searchNum); //make sure search value is numeric if (isNum) { //now we start looping through the array for (int i = 0; i < sizeNum; i++) { //if this index of the array equals the search value //let the user know where it was found if (numArray[i] == searchNum) { Console.WriteLine("-------------------------"); Console.WriteLine("Value {0} found at location {1}\n", searchNum, i + 1); return; } } //otherwise the value was not found Console.WriteLine("Value {0} was not found \n", searchNum); } else { //user didnt enter a numeric search value Console.WriteLine("You entered a non-numeric search value!"); } } else { Console.WriteLine("Please enter numeric data only!"); } }

The next search type we will utilize is the Binary Search method. As with the linear search, we will follow the first few steps exactly when it comes to getting the array size and the array values. It is when we start the search that things get radically different. With the binary search we first find the highest, lowest and middle values in our array. We do this to help narrow down the location of the requested value.

On each iteration of the loop, the lowest, highest and middle values are altered based on the current value. We do this until we either find a match, or reach the end of the array, we then act accordingly:

csharp

/// <summary> /// method to perform a binary search /// </summary> public static void BinarySearch() { //create an array to hold out numbers int[] numArray = new int[100]; bool isNum = false; int sizeNum; //prompt the user to enter the size of their array Console.WriteLine("Enter the array size."); //read in the value string sizeString = Console.ReadLine(); //use TryParse to check for a numeric value isNum = Int32.TryParse(sizeString, out sizeNum); //now we check for a numeric value if (isNum) { //prompt the user to enter their array values Console.WriteLine("-----------------------"); Console.WriteLine("Enter array values (numeric only). "); Console.WriteLine("-----------------------"); //now we start our loop, for the size of the array for (int i = 0; i < sizeNum; i++) { //temp value variable int tempValue; string arrayItem = Console.ReadLine(); isNum = Int32.TryParse(arrayItem, out tempValue); //once again check for a numeric value if (isNum) { //user enteres numeric value so add it to our array numArray[i] = tempValue; } else { //user didnt enter numeric value Console.WriteLine("You enteres a non-numeric value!"); break; } } //ask the user for their search value Console.WriteLine("--------------------"); Console.WriteLine("Enter search value (numeric only)."); Console.WriteLine("--------------------"); //value to hold our search value int searchNum; //read in the users search value string searchString = Console.ReadLine(); //use TryParse to check for numeric value isNum = Int32.TryParse(searchString, out searchNum); //make sure the user entered a numeric value if (isNum) { //user entered a numeric value so we start our search int lowNum = 0; //get the high number in the array int highNum = sizeNum - 1; //loop while the low number is less or equal to the high number while (lowNum <= highNum) { //get the middle point in the array int midNum = (lowNum + highNum) / 2; //now start checking the values if (searchNum < numArray[midNum]) { //search value is lower than this index of our array //so set the high number equal to the middle number //minus 1 highNum = midNum - 1; } else if (searchNum > numArray[midNum]) { //search value is higher than this index of our array //so set the low number to the middle number + 1 lowNum = midNum + 1; } else if (searchNum == numArray[midNum]) { //we found a match! let the user know the //location of the match Console.WriteLine("-----------------"); Console.WriteLine("Search successful"); Console.WriteLine("-----------------"); Console.WriteLine("Value {0} found at location {1}\n", searchNum, midNum + 1); return; } } //no match found Console.WriteLine("Value {0} was not found \n", searchNum); } else { //user entered a non-numeric search value Console.WriteLine("Search value must be numeric!"); } } else { //user didnt enter a numeric value Console.WriteLine("You must enter a numeric value!"); } }

As far as search algorithms those are the 2 most common, so we will not go further into search algorithms. We will now switch our focus to sorting an array.

Sorting An Array

When it comes to sorting an array, or any kind of list really, there are many different sorting algorithms. In this tutorial we will look at 3

Selection Sort
Bubble Sort
Insertion Sort

Selection Sort

A Selection Sort works by selecting the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled. A selection sort is a fast and easy sorting algorithm to implement, but isn't really efficient when it comes to sorting a large list. So lets look at how we would perform a selection fort on an integer array:

csharp

/// <summary> /// method to perform a selection sort on an array /// </summary> public static void SelectionSort() { //variable to hold the array size int[] arrayNum = new int[100]; int minNum; bool isNum = false; int sizeNum; //ask the user for the size of the array Console.WriteLine("Number of elements in the array ?"); //read in the value string sizeString = Console.ReadLine(); isNum = Int32.TryParse(sizeString, out sizeNum); //now check for a numeric value if (isNum) { //ask the user for the array values Console.WriteLine("-----------------------"); Console.WriteLine("Enter array values (numeric)."); Console.WriteLine("-----------------------"); //now we loop to the size of the array for (int i = 0; i < sizeNum; i++) { //temp value for the loop int temp; //read in the users value string arrayValue = Console.ReadLine(); //use TryParse to convert to number isNum = Int32.TryParse(arrayValue, out temp); //now make sure it's numeric if (isNum) { arrayNum[i] = temp; } else { Console.WriteLine("Array values must be numeric!"); break; } } //start a 2nd loop for the size of the array for (int j = 0; j < sizeNum - 1; j++) { //assign value to value of the incrementer minNum = j; //start a 3rd loop for (int k = j + 1; k < sizeNum; k++) { //check this index of the array to see if it's larger //that the index of the second loop if (arrayNum[minNum] > arrayNum[k]) { minNum = k; } } //now see if the minNum isnt equal to the index of the 3rd loop if (minNum != j) { //now we start the sorting int finalNum = arrayNum[j]; arrayNum[j] = arrayNum[minNum]; arrayNum[minNum] = finalNum; } } //write out the sorted value of the initial array Console.WriteLine("--------------------------------------------"); Console.WriteLine("Selection Sort results: "); //now a final loop to retrieve the items in the sorted value for (int l = 0; l < sizeNum; l++) { Console.WriteLine(arrayNum[l]); } } else { Console.WriteLine("The array size must be numeric!"); } }

Bubble Sort

Though the Bubble Sort is the oldest and easiest sorting algorithm to use, it is also the slowest, making it unappealing when it comes to large lists and arrays.

The bubble sort compares each item in the list with the next item (the one next to it), and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list. Here is how a bubble sort in C# would be implemented:

csharp

/// <summary> /// method to perform a bubble sort /// </summary> public static void BubbleSort() { //variable too hold our array int[] arrayNum = new int[100]; //variable to hold the boolean from TryParse bool isNum = false; //variable to hold the return value if TryParse is successful int sizeNum=0; //prompt the user to enter the array size Console.WriteLine("Number of elements in the array ?"); //read the value in string sizeStr = Console.ReadLine(); //use TryParse to check if the value is numeric isNum = Int32.TryParse(sizeStr, out sizeNum); //now check isNum if (isNum) { //they entered a valid numeric value, so now prompt for the array values Console.WriteLine("-----------------------"); Console.WriteLine("Enter array values (numeric only)."); Console.WriteLine("-----------------------"); //now we need a loop for the size of the array to grab each value //they enter. We then need to check for numeric values for (int i = 0; i < sizeNum; i++) { //temp variable to hold each value the user enters int temp = 0; //read in each value on each iteration string arrayValue = Console.ReadLine(); //now make sure they entered a numeric value isNum=Int32.TryParse(arrayValue,out temp); //now check the value of isNum if (isNum) { arrayNum[i] = temp; } else { Console.WriteLine("You entered a non-numeric value!"); break; } } int limit = sizeNum - 1; //now we need to start 2 more loops, each holding the //index of the previous loop for (int j = 0; j < sizeNum - 1; j++) { for (int k = 0; k < limit - j; k++) { //check if the index of the inner loop of the array //matches the inner loops index of the array + 1 if (arrayNum[k] > arrayNum[k + 1]) { //now we will do our sorting. we will set //the index of the inner loop to our finalNum //variable, then set the index of the array to the //index plus 1 int finalNum = arrayNum[k]; arrayNum[k] = arrayNum[k + 1]; arrayNum[k + 1] = finalNum; } } } //now we will print out the final sorted array Console.WriteLine("----------------------------------"); Console.WriteLine("Bubble Sort results:"); //loop through the sorted array and print out the values for (int l = 0; l < sizeNum; l++) { Console.WriteLine(arrayNum[l]); } } else { Console.WriteLine("You must enter a numeric value!"); } }

Insertion Sort

The Insertion Sort works like its name implies, it inserts each item into its proper place in the sorted array. The insertion sort algorithm is almost twice as fast, thus far more efficient, than the bubble sort. The most common implementation, as we will be seeing shortly, is to use an in place sorting system, where in each iteration the value is inserted into it's right place, until the entire array has been sorted. This is how an insertion sort would be implemented in C#:

csharp

/// <summary> /// method for performing an insertion sort on an integer array /// </summary> public static void InsertionSort() { //variable too hold our array int[] arrayNum = new int[100]; //variable to hold the boolean from TryParse bool isNum = false; //variable to hold the return value if TryParse is successful int sizeNum = 0; //prompt the user to enter the array size Console.WriteLine("Number of elements in the array ?"); //read the value in string sizeStr = Console.ReadLine(); //use TryParse to check if the value is numeric isNum = Int32.TryParse(sizeStr, out sizeNum); //now check isNum if (isNum) { //they entered a valid numeric value, so now prompt for the array values Console.WriteLine("-----------------------"); Console.WriteLine("Enter array values (numeric only)."); Console.WriteLine("-----------------------"); //now we need a loop for the size of the array to grab each value //they enter. We then need to check for numeric values for (int i = 0; i < sizeNum; i++) { //temp variable to hold each value the user enters int temp = 0; //read in each value on each iteration string arrayValue = Console.ReadLine(); //now make sure they entered a numeric value isNum = Int32.TryParse(arrayValue, out temp); //now check the value of isNum if (isNum) { arrayNum[i] = temp; } else { Console.WriteLine("You entered a non-numeric value!"); break; } } int index; int x; //now we need to start 2 more loops, each holding the //index of the previous loop for (int j = 1; j < sizeNum ; j++) { index = arrayNum[j]; x = j; //now use a while loop to loop through our array inserting' //each value in the right spot in the list until we've //traversed the entire array while ((x > 0) && (arrayNum[x - 1] > index)) { arrayNum[x] = arrayNum[x - 1]; x = x - 1; } arrayNum[x] = index; } //now we will print out the final sorted array Console.WriteLine("----------------------------------"); Console.WriteLine("Insertion Sort results:"); //loop through the sorted array and print out the values for (int l = 0; l < sizeNum; l++) { Console.WriteLine(arrayNum[l]); } } else { Console.WriteLine("You must enter a numeric value!"); } }

The final item we will look at, and one there are many questions about, is finding the lowest and highest value in an integer array. Here we will, as with the sort and search methods we've looked at, will prompt the user for the size of their array and the values they want in their array. We will them loop through the array, examining each value. If the current value is higher than the previous value then the highest number variable is updated with that value, same goes with the current value being lower than the previous value.

We continue this format until we have reached the end of our array. Once we have reached the end of our array we will have the values for the highest and the lowest values in the array. Here is how that process would look like:

csharp

/// <summary> /// method to find the largest and smallest number /// in an integer array /// </summary> public static void FindLargestAndSmallest() { int arraySize; bool isNum; int largestNum; int smallestNum; int[] numArray = new int[50]; //ask the user for the size of their array Console.WriteLine("Enter the size of Array"); //read in the value string sizeString = Console.ReadLine(); //we will now use TryParse to get the numeric value entered isNum = Int32.TryParse(sizeString, out arraySize); //now we will determine if the value is numeric if (isNum) { //then entered a numeric value so now we need to //ask for the values they want in their array Console.WriteLine("Enter array value:"); for (int i = 0; i < arraySize; i++) { //int variable to hold the our value from TryParse int temp; //read in each value and add it to our array if it's //a numeric value string arrayValue = Console.ReadLine(); isNum = Int32.TryParse(arrayValue, out temp); //now do our check if (isNum) { //value is numeric soa dd to our array numArray[i] = temp; } else { //value isnt numeric Console.WriteLine("Array values must be numeric!"); break; } } Console.Write("\r\n"); //now we need to set the values of our largest //and smallest number variables largestNum = numArray[0]; smallestNum = numArray[0]; //now loop through the length of our array for (int i = 1; i < arraySize; i++) { //check if the current array index is larger //than the largest number variable if (numArray[i] > largestNum) { //if it is then that is the largest number //(for this iteration) largestNum = numArray[i]; } //otherwise check to see if this array index //is smaller than the smallest number else if (numArray[i] < smallestNum) { //that is our smallest number (for this iteration) smallestNum = numArray[i]; } } //now print out the results Console.WriteLine("Largest value is: {0}", largestNum); Console.WriteLine("Smallest value is: {0}", smallestNum); } else { Console.WriteLine("Array size must be numeric!"); } }

There you have it, that is how you work with arrays, well as far as searching and sorting arrays. There are many other search and sorting algorithms out there, some more efficient, some less efficient, but this tutorial should at least give you a good foundation for going further on this topic. I hope you found this tutorial useful and informative, and I thank you for reading.

Happy Coding!