Special Array Techniques
This section introduces some supplementary techniques for solving problems often encountered when working with arrays. In particular, this section
Presents a sorting program based on a famous sorting algorithm called Bubble Sort
Compares the speed of the Bubble Sort program with that of the sorting program found in the .NET Framework
Introduces a couple of algorithms to search for a particular value in an array
Compares the speed of our implementation with that of the search method found in the .NET Framework
Sorting
The next couple sections introduce you to the simple bubble sort algorithm and compares its speed to the much faster, built-in sorting program found in the .NET Framework.
Presenting Bubble Sort
With the simple sorting program introduced in Chapter 7, "Types Part II: Operators, Enumerators and Strings," we were able to sort just three words in alphabetic order. By comparing and swapping values repeatedly (if necessary), smaller values would rise upward and larger values sink downward in a list of three words. The idea behind this algorithm can be applied to sort arrays of varying length, and is then commonly known as the bubble sort technique, because smaller values, like bubbles in water, gradually drift to the "top" (beginning) of the array.
Note
 | The bubble sort technique is also referred to as the sinking sort technique because large values sink to the "bottom" (end) of the array. |
In the following description of the bubble sort algorithm, testScores is a one-dimensional array containing ten elements. It is declared/defined as follows:
int [] testScores = {300, 90, 50, 120, 100, 10, 290, 85, 90, 120} ; Our aim is to sort the ten elements in ascending order (meaning smaller values first).
The algorithm traverses through the entire array (referred to as a pass) several times. During each pass, the algorithm repeatedly compares consecutive pairs of adjacent array element values as illustrated in Figure 11.14. The first pair compared is the pair with index 0 and 1. The second pair has indexes 1 and 2. This repeated action is continued until the end of the array is reached. In our case, the last pair to be compared has indexes 8 and 9. Observe that in an array with ten elements, there are nine (10 1) comparable pairs, and in an array with length number of elements, there are length 1 comparable pairs. During each comparison, the value of the array element with the lower index (called 1st value in the figure) is compared to that of the array element with the higher index (called 2nd value in the figure). If the 1st value is greater than the 2nd value, the two values are swapped; otherwise, nothing happens. If no elements were swapped during one full pass, it indicates that the array is sorted in the desired order and the algorithm is terminated. Notice in Figure 11.14 that 300 is the largest value in the list, and that during the first pass, it is moved to the last position. During the first comparison, it is moved to the second position because it is greater than 90. During the second comparison, it is moved to the third position because it is greater than 50, and so on until it is placed in the last position.
Figure 11.14. One pass through the testScores.
Let's now turn to the actual implementation of the algorithm. First of all, we need the ability to swap two elements of an array. The swapping technique used here employs a temporary variable and is identical to that of our simple word sorter program from Chapter 7. However, in this case, the swap takes place in a separate method that receives a reference to the array and two indexes specifying which two elements to swap. We will look closer at the swap method later in the finished program of Listing 11.8.
We can now concentrate on the core parts of the sorting algorithm. First, an outer loop is needed that will repeat itself as long as the last pass performed at least one swap. This can be expressed with pseudocode as in Listing 11.6.
Listing 11.6 Pseudocode for Outer Framework Bubble Sort Algorithm Initial Design
let swapped be a variable of type bool. Set it to true. while swapped is true { set swapped equal to false make one full pass, if any swaps are made set swapped to true } We now have an initial design of the outer framework that holds the code for what constitutes one pass. Let's then have a closer look at the pass part of the algorithm. As already mentioned, an array of length n has n 1 comparable pairs. Consequently, we need to perform n 1 comparisons. If bubbles is the name of the array we want to sort, we can express the loop part of the pass with a for loop:
for (int j = 0; j < (bubbles.Length 1); j++) { // comparisons } If j is the loop counter and moves from index 0 to the largest index minus one, we can specify a pair of comparable array elements to have the indexes j and j + 1, respectively. Each comparison would look like the following:
if (bubbles[j] > bubbles[j + 1]) { Swap the two elements. Set swapped equal to true } By putting the pieces already presented together, we end up with the pseudocode of a valid bubble sort algorithm, as presented in Listing 11.7.
Listing 11.7 Pseudocode for Bubble Sort Slow Version
let swapped be a variable of type bool. Set it equal to true. while swapped is true { set swapped equal to false for (int j = 0; j < (bubbles.Length 1); j++) { if (bubbles[j] > bubbles[j + 1]) { Swap the two elements. Set swapped equal to true } } } Listing 11.7 represents a fully working algorithm, but by observing a subtle point about the nature of this algorithm, we can make it faster. Recall how the largest value (300) of testScores during the first pass was brought all the way to the last position. During the next pass, the second largest value (290) is brought to the second-to-the-last position. After n passes, the n last positions of the array will be sorted in the correct order and contain the largest values of the array. Consequently, any attempt to let the comparison algorithm move into this territory is a waste of time. By equipping the outer loop with a pass counter, here called i, we can gradually let i reduce the number of comparisons performed by the inner for statement, as more passes are carried out.
The resulting pseudocode is shown in Figure 11.15.
Figure 11.15. Pseudocode for bubble sort algorithm faster version.
Listing 11.8 presents the final C# source code for the bubble sort method (called BubbleSortAscending of lines 6 22) along with its helper method Swap (lines 25 32). The Main() method (lines 43 54) utilizes BubbleSortAscending to sort its testScores array (line 45). The result of the sorting is shown in the sample output after Listing 11.8.
Listing 11.8 BubbleSort.cs
01: using System; 02: 03: class BubbleSorter 04: { 05: // Sort the elements of an array in ascending order 06: public static void BubbleSortAscending(int [] bubbles) 07: { 08: bool swapped = true; 09: 10: for (int i = 0; swapped; i++) 11: { 12: swapped = false; 13: for (int j = 0; j < (bubbles.Length - (i + 1)); j++) 14: { 15: if (bubbles[j] > bubbles[j + 1]) 16: { 17: Swap(j, j + 1, bubbles); 18: swapped = true; 19: } 20: } 21: } 22: } 23: 24: //Swap two elements of an array 25: public static void Swap(int first, int second, int [] arr) 26: { 27: int temp; 28: 29: temp = arr[first]; 30: arr[first] = arr[second]; 31: arr[second] = temp; 32: } 33: 34: //Print the entire array 35: public static void PrintArray (int [] arr) 36: { 37: for (int i = 0; i < arr.Length; i++) 38: { 39: Console.Write("{0} , ", arr[i]); 40: } 41: } 42: 43: public static void Main() 44: { 45: int [] testScores = {300, 90, 50, 120, 100, 10, 290, 85, 90, 120} ; 46: 47: BubbleSortAscending(testScores); 48: Console.WriteLine("The test scores sorted in ascending order:\n"); 49: for (int i = 0; i < testScores.Length; i++) 50: { 51: Console.Write("{0} ", testScores[i]); 52: } 53: } 54: } The test scores sorted in ascending order: 10 50 85 90 90 100 120 120 290 300 The method Swap (lines 25 32) declares in its header three formal parameters first, second, and arr. The latter is of type reference-to-array-object-of-base-type-int. During the execution of this method, arr is referencing exactly the same array object as the reference that was passed as an argument. Any changes made to arr will be reflected as changes in the array argument. first and second specify the indexes of the array elements to be swapped. The swap follows the same technique as the swapping algorithm presented in Listing 7.10 of Chapter 7.
The BubbleSortAscending method (lines 6 22) receives a reference to the array object, which must be sorted. The formal parameter containing this reference is called bubbles. During the execution of BubbleSortAscending, bubbles is referencing the same array object as testScores declared in line 45. Any changes made to bubbles inside BubbleSortAscending is reflected in testScores.
If you have read the previous section, the source code of this method should be comprehensible.
The bubble sort is simple to implement, but very inefficient. Its use is limited to relatively short arrays or arrays that are nearly sorted. Other more sophisticated algorithms with names like Quick sort, Shell sort, Merge sort, and Heap sort should be applied to solve more elaborate sorting problems. These algorithms are beyond the scope of this book, but more information can be found in books and courses with names containing words like "algorithms" or "data structures."
If you want the functionality of a very fast sorting method, but have no interest in implementing it yourself, why not utilize what other highly-skilled programmers have already created and tested? You can do this by calling System.Array's built-in Sort method presented briefly in Table 11.3 in the next section.
Sorting with System.Array's Sort Method
The predefined Sort method of System.Array is static and is called by applying the dot operator to the classname System.Array. To sort the array testScores declared/defined as
int [] testScores = {300, 90, 50, 120, 100, 10, 290, 85, 90, 120} ; we simply write
System.Array.Sort (testScores)
Listing 11.9 investigates how fast the Array.Sort method is compared to the BubbleSortAscending method. The implementation of the BubbleSortAscending and Swap methods are identical to that of Listing 11.8. The Main() method (lines 43 73) utilizes the System.DateTime structure to time the full sort of the testScores array (line 45) by using the bubble sort method and the Array.Sort method. By changing the length of testScores in line 45, it is possible to test how the two algorithms fare on small and large collections. The sample output displayed after Listing 11.9 shows the results I got on my computer when testing two arrays of length 1000 and 40000, respectively. As expected, both methods took less than a second to sort 1000 array elements. However, at 40000, the limitations of the bubble sort appears. While Array.Sort still took less than a second, bubble sort spent a staggering 23 seconds.
Listing 11.9 SortingCompetition.cs
01: using System; 02: 03: class SortingCompetition 04: { 05: // Sort the elements of an array in ascending order 06: public static void BubbleSortAscending(int [] bubbles) 07: { 08: bool swapped = true; 09: 10: for (int i = 0; swapped; i++) 11: { 12: swapped = false; 13: for (int j = 0; j < (bubbles.Length - (i + 1)); j++) 14: { 15: if (bubbles[j] > bubbles[j + 1]) 16: { 17: Swap(j, j + 1, bubbles); 18: swapped = true; 19: } 20: } 21: } 22: } 23: 24: //Swap two elements of an array 25: public static void Swap(int first, int second, int [] arr) 26: { 27: int temp; 28: 29: temp = arr[first]; 30: arr[first] = arr[second]; 31: arr[second] = temp; 32: } 33: 34: //Print the entire array 35: public static void PrintArray (int [] arr) 36: { 37: for (int i = 0; i < arr.Length; i++) 38: { 39: Console.Write("{0} , ", arr[i]); 40: } 41: } 42: 43: public static void Main() 44: { 45: int [] testScores = new int [1000]; 46: DateTime sortStart; 47: DateTime sortEnd; 48: 49: for (int i = 0; i < testScores.Length; i++) 50: { 51: testScores[i] = testScores.Length - i; 52: } 53: 54: Console.WriteLine("Now timing the bubble sort method please wait..."); 55: sortStart = DateTime.Now; 56: BubbleSortAscending(testScores); 57: sortEnd = DateTime.Now; 58: Console.WriteLine("Seconds elapsed bubble sorting an array of length {0} : 
{1} ", 59: testScores.Length, ((sortEnd - sortStart).Ticks/10000000)); 60: 61: for (int i = 0; i < testScores.Length; i++) 62: { 63: testScores[i] = testScores.Length - i; 64: } 65: 66: Console.WriteLine("\nNow timing the built in sort method" + 67: " of System.Array. Please wait..."); 68: sortStart = DateTime.Now; 69: Array.Sort(testScores); 70: sortEnd = DateTime.Now; 71: Console.WriteLine("Seconds elapsed .NET sorting an array of length {0} : {1} ", 72: testScores.Length, ((sortEnd - sortStart).Ticks/10000000)); 73: } 74: } Sample output 1. testScores containing 1000 elements:
Now timing the bubble sort method please wait... Seconds elapsed bubble sorting an array of length 1000: 0 Now timing the built in sort method of System.Array. Please wait... Seconds elapsed .NET sorting an array of length 1000: 0
Sample output 2. testScores containing 40000 elements:
Now timing the bubble sort method please wait... Seconds elapsed bubble sorting an array of length 40000: 23 Now timing the built in sort method of System.Array. Please wait... Seconds elapsed .NET sorting an array of length 40000: 0
Note:
Results will vary according to the speed of your computer. You might want to use array lengths other than those shown here to get similar results.
After line 45, testScores has been initialized by the runtime to contain a long list of zeros. Both the sorting methods will sort the arrays in ascending order, so to challenge them, lines 49 52 assigns values of descending order to testScores. The value of testScores[0] will be testScores.Length (here 1000), and the value of testScores[testScores.Length] will be 1.
Lines 46 and 47 declare two variables of type System.DateTime. This structure type is useful when dealing with dates and time. The computer has an internal clock that keeps track of the date and time of the day down to milliseconds. With DateTime's static Now property, we are able to access the time of the computer clock right now. The time returned via Now is in the form of a DateTime value. Thus, the following line assigns the time right now of the computer clock to sortStart:
sortStart = DateTime.Now;
If we assign the current time to sortStart immediately before beginning a sorting process, and to sortEnd instantly after the process has been terminated, it is possible to estimate the time elapsed during the process by deducting sortStart from sortEnd. This is done in lines 59 and 72. DateTime offers several different formats when printing a time interval on the console. In this case, I chose to express the interval in seconds. The Ticks property is suitable for this purpose. It returns a time interval as the amount of 100-nanosecond-intervals it contains. A nanosecond is one billionth (10-9) of a second. 100 nanoseconds is 10 millionth of a second. Converting the amount returned by Ticks to seconds requires us to divide it by ten million, as displayed in lines 59 and 72.
When you run Listing 11.9 as it is displayed here, you will see sample output 1 appear onscreen. To run the program with 40,000 elements instead, you need to exchange 1000 in line 45 with 40000. The elapsed seconds will vary among different computer systems. If you have a very fast computer, you might have to increase to 40,000 to see a visible delay.
EAN: 2147483647
Pages: 286