Now as we come to the end of our book and we reach our learning target, we have the core skills required to write applications in C#. We will now turn our attention to using the skills we have learned and apply
them to search and sort routines that developers may commonly use when programming commercial applications. Firstly, we will look at two common search routines, linear search and binary search, and then we will look at two common sorting algorithms, bubble sort and insertion sort.
Linear Search
A linear search
is used to search a series of elements in a data structure for a specified element. While a linear search can be used successfully, it will generally be slower than a binary search
, which we will also look at. The linear search can be thought of as a “brute-force
” algorithm since it simply compares each item in the data structure with the element being searched for. It does not need to have the state of the data structure
changed before it begins, for example, it does not need to have a sorted set of elements in a chronological or alphabetical order.
If we were to see an academic or technical interview
question based on a linear search, it might be in the form of a scenario like this:
Starting with an array of n integers and having a value to find, decide if the value to be found exists within the given array using the linear search algorithm. If the target exists in the array, display the array index of the required value.
The algorithm
to solve this problem using a linear search is as follows:
1.
Start at the first array element.
2.
Check if the value being searched for matches this current value of the data structure.
3.
If there is a match, the value has been found, and we return the index of the current data structure value and display it.
4.
If there is no match, the value has not been found, and –1 is returned.
5.
Move to the next array value.
6.
Repeat from step 2 to step 5 until the end of the array has been met.
Let’s code some C# and build our programming muscle.
Create an Application That Will Implement a Linear Search
Add a new project
to hold the code for this chapter.
1.
Right-click the solution CoreCSharp
.
2.
Choose Add.
3.
Choose New Project.
4.
Choose Console App from the listed templates that appear.
5.
Click the Next button.
6.
Name the project Chapter24 and leave it in the same location.
7.
Click the Next button.
8.
Choose the framework to be used, which in our projects will be .NET 6.0 or higher.
9.
Click the Create button.
Now we should see the Chapter24 project within the solution called CoreCSharp.
10.
Right-click the Chapter24 project in the Solution Explorer panel.
11.
Click the Set as Startup Project option.
Notice how the Chapter24 project name has been made to have bold text, indicating that it is the new startup project and that it is the Program.cs file within it that will be executed when we run the debugging.
12.
Right-click the Program.cs file in the Solution Explorer window.
13.
Choose Rename.
14.
Change the name to LinearSearch.cs.
15.
Press the Enter key.
16.
Double-click the LinearSearch.cs file to open it in the editor window.
We will now create the namespace, the class, and the Main() method.
Declare a variable and assign it the value to be found
20.
Amend the code, as in Listing 24-4, to call a method that will display the elements of the array.
// Value to be located using linear search
int valueToBeLocated = 1000;
// Display the elements of the array
DisplayArrayElements(claimValues);
} // End of Main() method
} // End of Customer class
} // End of Chapter24 namespace
Listing 24-4
Call a method that will display the array elements
We will now call a method that will perform a linear search of the array looking for a specified value and then assign the returned value to a variable.
Call the linear search method passing it the array and the
value to be located and store the returned value in a variable
called returnedValue
*/
int returnedValue = SearchForTheValue(claimValues, valueToBeLocated);
} // End of Main() method
} // End of Customer class
} // End of Chapter24 namespace
Listing 24-5
Call a method that will perform a linear search
We will now display one message if the returned value is –1 and another message if the returned value is not –1. The –1 value means no match was found.
int returnedValue = SearchForTheValue(claimValues, valueToBeLocated);
// Display the appropriate message (located or not)
if (returnedValue == -1)
{
Console.WriteLine("The value is not present in array");
}
else
{
// Using an interpolated string
Console.WriteLine($"The value was located at index {returnedValue} (position {returnedValue + 1})");
} // End of if else construct
} // End of Main() method
} // End of Customer class
} // End of Chapter24 namespace
Listing 24-6
Display an appropriate message based on the returned value
We will now create the method that will search the array for the required value. The method will have the array passed to it, as well as the value that is to be searched for. It is a parameter method
, and it will return an integer value. The method will be created outside the Main() method.
Great, that will have one of the red underlined messages in the Main() method satisfied, because the method being called now exists. So we will now create the second method that will display the array values, and this will clear the red underlined message we still have.
Create the method that will display the array values
25.
Click the File menu.
26.
Choose Save All.
27.
Click the Debug menu.
28.
Choose Start Without Debugging.
Figure 24-1 shows the console window, and we can see that the first method to display all array elements has worked and that the second method has compared the value 1000 with the array elements and then stopped when it has found the first occurrence, which is at position 6, index 5.
29.
Press the Enter key to close the console window.
Binary Search (Iterative Binary Search)
A binary search is used to search a series of elements in a data structure for a specified value, sometimes called the key. Unlike the linear search
, the binary search only works when the array is sorted. The binary search starts with the full sorted array and checks if the search value is less than the item in the middle of the array:
If it is, the search is narrowed to the lower half of the array, the left side.
If it is not, then we use the upper half, the right side, and we repeat the process, until the value is found or there are no elements to halve.
The binary search represents a divide-and-conquer algorithm, and the algorithm will discard one half of the array in each iteration
.
If we were to see an academic or technical interview question based on a binary search, it might be in the form of a scenario like this:
Starting with a sorted array of n integers and having a value to find, decide if the value to be found exists within the given array using the binary search algorithm. If the target exists in the array, display the array index of the value.
The algorithm to solve this problem using a binary search is as follows:
If the value to be found = array[middle value], return the middle value.
If the value to be found < array[middle value], then discard the elements of the array to the right of the middle value including the middle value.
If the value to be found > array[middle value], then discard the elements of the array to the left of the middle value including the middle value.
Let’s code some C# and build our programming muscle.
1.
Right-click the Chapter24 project.
2.
Choose Add.
3.
Choose Class.
4.
Name the class BinarySearch.cs.
5.
Click the Add button.
The BinarySearch class code will appear in the editor window and will be similar to Listing 24-9.
namespace Chapter24
{
internal class BinarySearch
{
} // End of BinarySearch class
} // End of Chapter24 namespace
Listing 24-9
Namespace with BinarySearch class
6.
Create a Main() method within the class, as in Listing 24-10, since this was not produced automatically, and delete the unwanted imports.
namespace Chapter24
{
internal class BinarySearch
{
static void Main(string[] args)
{
} // End of Main() method
} // End of BinarySearch class
} // End of Chapter24 namespace
Listing 24-10
Main() method
added to class
7.
Amend the code, as in Listing 24-11, to add a comment block, create an array, and initialize the values.
namespace Chapter24
{
/*
With a binary search we must first ensure the array is sorted.
The binary search starts with the whole array and checks if
the value of our search key is less than the item in the
middle of the array.
If it is, the search is narrowed to the lower
(left) half of the array.
If it is not, then we use the upper (right) half.
We repeat the process until the value is found or there
Declare a variable
and assign it the value to be found
We will now sort the array since a binary search requires a sorted array to perform a search correctly.
9.
Amend the code to sort the array as in Listing 24-13.
// Value to be located using binary search
int valueToBeLocated = 6000;
// Sort the array as this is essential for a Binary search
Array.Sort(claimValues);
} // End of Main() method
Listing 24-13
Sort the array prior to doing a binary search
10.
Amend the code, as in Listing 24-14, to call a method that will display the array.
// Sort the array as this is essential for a Binary search
Array.Sort(claimValues);
// Display the elements of the array
DisplayArrayElements(claimValues);
} // End of Main() method
} // End of BinarySearch class
Listing 24-14
Call the method that will display the elements of the array
We will now call the method that will perform a binary search of the array looking for a specified value and then assign the returned value to a variable.
Call the binary search method passing it the array and the
value to be located and store the returned value in a
variable called returnedValue
*/
int returnedValue = PerformBinarySearch(claimValues, valueToBeLocated);
} // End of Main() method
} // End of BinarySearch class
Listing 24-15
Call the method that will do the binary search
We will perform a selection that will display one message if the returned value is –1 and a different message if the returned value is not –1. A –1 value means no match has been found.
int returnedValue = PerformBinarySearch(claimValues, valueToBeLocated);
// Display the appropriate message (located or not)
if (returnedValue == -1)
{
Console.WriteLine("The value is not present in array");
}
else
{
// Using an interpolated string
Console.WriteLine($"The value was located at index {returnedValue} (position { returnedValue + 1})");
} // End of if else construct
} // End of Main() method
} // End of BinarySearch class
Listing 24-16
Perform a selection and display an appropriate message
We will now create the method that will binary search the array for the required value. In this example we are using an iterative method to perform the binary search, but there is an alternative recursive method that will work. The method will be created outside the Main() method.
Create the method to perform a search and return a value
Great, that will have one of the red underlined messages satisfied in the Main() method because the method being called now exists. So let us now create the second method that will display the array values, and this will clear the red underlined message we still have. The method will be created outside the Main() method.
Now that we have all the code we require, we can run the application to ensure it works as expected.
15.
Right-click the Chapter24 project in the Solution Explorer panel.
16.
Choose Properties from the pop-up menu.
17.
Choose the BinarySearch class in the Startup object drop-down list.
18.
Close the Properties window.
19.
Click the File menu.
20.
Choose Save All.
21.
Click the Debug menu.
22.
Choose Start Without Debugging.
Figure 24-2 shows the console, and we can see that 6000 was correctly identified as being at array index 5, which is position 6.
23.
Press the Enter key to close the console window.
Bubble Sort
A bubble sort is a simple sorting algorithm that works by comparing two adjacent
elements of an array, and if the first element is numerically greater than the next one, the elements are swapped. The process is then repeated to move across all the elements of the array. In Chapter 11 on arrays, we saw the sort method being used through code as Array.Sort(). Now we are going to look at how such a sort method might work “under the hood.”
If we were to see an academic or technical interview question based on a bubble sort, it might be in the form of a scenario like this:
Starting with an array of n integers, use a bubble sort to arrange the array values in ascending order.
The algorithm to solve this problem using a bubble sort is as follows:
1.
Pick the first value in the array.
2.
Compare this current value with the next value.
3.
If the next value is smaller than the current value, swap the two values; otherwise, leave the values as they are.
4.
Move to the next number in the array.
5.
Repeat steps 2–4 until we reach the last value in the array.
Let’s code some C# and build our programming muscle.
1.
Right-click the Chapter24 project.
2.
Choose Add.
3.
Choose Class.
4.
Name the class BubbleSort.cs.
5.
Click the Add button.
The BubbleSort class code will appear in the editor window and will be similar to Listing 24-19.
namespace Chapter24
{
internal class BubbleSort
{
} // End of BubbleSort class
} // End of Chapter24 namespace
Listing 24-19
Namespace
with BubbleSort class
6.
Create a Main() method within the class, as in Listing 24-20, since this was not produced automatically, and delete the unwanted imports.
namespace Chapter24
{
internal class BubbleSort
{
static void Main(string[] args)
{
}// End of Main() method
} // End of BubbleSort class
} // End of Chapter24 namespace
Listing 24-20
BubbleSort class with Main() method
7.
Amend the code, as in Listing 24-21, to add a comment block, create an array, and initialize the values.
namespace Chapter24
{
/*
A Bubble sort is a simple algorithm which compares
two adjacent elements of the array. If the first element
is numerically greater than the next one, the elements
are swapped. The process is then repeated to move across
Great, that will have one of the red underlined messages in the Main() method
removed, because the method being called now exists. So we will now create the second method that will display the array values, and this will clear the red underlined message we still have. The method will be created outside the Main() method.
Now that we have all the code we require, we can run the application to ensure it works as expected.
12.
Right-click the Chapter24 project in the Solution Explorer panel.
13.
Choose Properties from the pop-up menu.
14.
Choose the BubbleSort class in the Startup object drop-down list.
15.
Close the Properties window.
16.
Click the File menu.
17.
Choose Save All.
18.
Click the Debug menu.
19.
Choose Start Without Debugging.
Figure 24-3 shows the last part of the console window, with the final version of the sorted array displayed.
20.
Press the Enter key to close the console window.
Insertion Sort
An insertion sort is similar to a bubble sort but it is a more efficient sort. We should think about using the insertion sort when we have a large number of elements to sort since larger data sets will take more time.
If we were to see an academic
or technical interview question based on an insertion sort, it might be in the form of a scenario like this:
Starting with an array of n integers, use an insertion sort to arrange the array values in ascending order.
The algorithm to solve this problem using an insertion sort is as follows:
1.
Pick the second value in the array.
2.
Compare this current value with the value to the left.
3.
If the value to the left is greater than the current value, swap the two values, repeating this comparison to the value on the left until we meet a value less than it; otherwise, leave the values as they are.
4.
Move to the next number, from the original position, in the array.
5.
Repeat steps 2–4 until we reach the last value in the array.
Let’s code some C# and build our programming muscle.
1.
Right-click the Chapter24 project.
2.
Choose Add.
3.
Choose Class.
4.
Name the class InsertionSort.cs.
5.
Click the Add button.
The InsertionSort class code will appear in the editor window and will be similar to Listing 24-26.
namespace Chapter24
{
internal class InsertionSort
{
} // End of Insertion class
} // End of Chapter24 namespace
Listing 24-26
Namespace with InsertionSort class
6.
Create a Main() method within the class, as in Listing 24-27, since this was not produced automatically, and delete the unwanted imports.
namespace Chapter24
{
internal class InsertionSort
{
static void Main(string[] args)
{
} // End of Main() method
} // End of Insertion class
} // End of Chapter24 namespace
Listing 24-27
InsertionSort class with Main() method
7.
Amend the code, as in Listing 24-28, to add a comment block, create an array, and initialize the values.
namespace Chapter24
{
/*
An Insertion Sort is similar to a Bubble sort, however, it is
a more efficient sort. We should think about using the
Insertion sort when we have a large number of elements to sort.
Great, that will have one of the red underlined messages in the Main() method removed, because the method being called now exists. So we will now create the second method that will display the array values, and this will clear the red underlined message we still have. The method will be created outside the Main() method.
Now that we have all the code we require, we can run the application to ensure it works as expected.
12.
Right-click the Chapter24 project in the Solution Explorer panel.
13.
Choose Properties from the pop-up menu.
14.
Choose the InsertionSort class in the Startup object drop-down list.
15.
Close the Properties window.
16.
Click the File menu.
17.
Choose Save All.
18.
Click the Debug menu.
19.
Choose Start Without Debugging.
Figure 24-4 shows the last part of the console window, with the final version of the sorted array displayed.
20.
Press the Enter key to close the console window.
The original array is shown in Table 24-1, and Table 24-2 shows what comparisons are made during each iteration. We will see that at the start, the following happens:
6000 and 9000 are compared, and as they are in the correct order, they are ignored and stay in the same positions.
Now we swap 9000 and 3000 because 3000 is less than 9000.
Now we check 3000 with 6000, and as 3000 is less than 6000, we swap them and so on.
Table 24-1
Original values
6000
9000
3000
4000
8000
1000
2000
5000
7000
Table 24-2
Resulting
iterations
and the values being compared
6000
9000
3000
4000
8000
1000
2000
5000
7000
6000
9000
3000
4000
8000
1000
2000
5000
7000
6000
3000
9000
4000
8000
1000
2000
5000
7000
3000
6000
9000
4000
8000
1000
2000
5000
7000
3000
6000
4000
9000
8000
1000
2000
5000
7000
3000
4000
6000
9000
8000
1000
2000
5000
7000
3000
4000
6000
8000
9000
1000
2000
5000
7000
3000
4000
6000
8000
1000
9000
2000
5000
7000
3000
4000
6000
1000
8000
9000
2000
5000
7000
3000
4000
1000
6000
8000
9000
2000
5000
7000
3000
1000
4000
6000
8000
9000
2000
5000
7000
1000
3000
4000
6000
8000
9000
2000
5000
7000
1000
3000
4000
6000
8000
2000
9000
5000
7000
1000
3000
4000
6000
2000
8000
9000
5000
7000
1000
3000
4000
2000
6000
8000
9000
5000
7000
1000
3000
2000
4000
6000
8000
9000
5000
7000
1000
2000
3000
4000
6000
8000
9000
5000
7000
1000
2000
3000
4000
6000
8000
5000
9000
7000
1000
2000
3000
4000
6000
5000
8000
9000
7000
1000
2000
3000
4000
5000
6000
8000
9000
7000
1000
2000
3000
4000
5000
6000
8000
7000
9000
1000
2000
3000
4000
5000
6000
7000
8000
9000
From Table 24-2 we can see what our code has produced for each iteration, and the highlighted values are the values being compared during each iteration.
Chapter Summary
In this chapter we have looked at some common search and sort algorithms in the C# programming language. The linear search, binary search, bubble sort, and insertion sort algorithms are language independent and can be used in any programming language. We simply use the same business logic, but the code will be programming language specific, for example, C#, Java, Python, JavaScript, or COBOL.
Another great achievement! This is really good. We are seeing the application of our coding skills to routines regularly used in coding. We should be immensely proud of the learning to date. In finishing this chapter, we have increased our knowledge further. We are getting very close to our target. The end is in sight.