Page 1 of 1

Searching and sorting arrays in C#

#1 PsychoCoder  Icon User is offline

  • Google.Sucks.Init(true);
  • member icon

Reputation: 1638
  • View blog
  • Posts: 19,853
  • Joined: 26-July 07

Posted 17 March 2008 - 06:23 PM

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 NamespacesSo lets bring in our references


using System;
using System.Collections.Generic;
using System.Text;




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:


/// <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:


/// <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:


/// <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:


/// <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#:


/// <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:


/// <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! :)

This post has been edited by PsychoCoder: 17 March 2008 - 06:24 PM


Is This A Good Question/Topic? 1
  • +

Replies To: Searching and sorting arrays in C#

#2 Ändrew  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 25
  • View blog
  • Posts: 312
  • Joined: 21-April 08

Posted 12 December 2009 - 04:14 PM

Very good, Just what i wanted to learn :D
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1