Recipe5.2.Reversing an Array Quickly

Recipe 5.2. Reversing an Array Quickly

Problem

You want an efficient method to reverse the order of elements within an array.

Solution

You can use the static Reverse method, as in this snippet of code:

 int[] someArray = new int[5] {1,2,3,4,5}; Array.Reverse(someArray);

or you can write your own reversal method:

 public static void DoReversal<T>(T[] theArray) {     T tempHolder = default(T);     if (theArray.Length > 0)     {         for (int counter = 0; counter < (theArray.Length / 2); counter++)         {             tempHolder = theArray[counter];             theArray[counter] = theArray[theArray.Length - counter - 1];             theArray[theArray.Length - counter - 1] = tempHolder;         }     }     else     {         Trace.WriteLine("Nothing to reverse");     } }

While there is more code to write, the benefit of the DoReversal<T> method is that it is about twice as fast as the Array.Reverse method. In addition, you can tailor the DoReversal<T> method to a specific situation. For example, the DoReversal<T> method accepts a value type array (int), whereas the Array.Reverse method accepts only a reference type (System.Array). This means that a boxing operation will occur for the int value types. The DoReversal<T> method removes any boxing operations.

Discussion

The following TestArrayReversal method creates a test array of five integers and displays the elements in their initial order. Next, the DoReversal<T> method is called to reverse the elements in the array. After this method returns, the array is then displayed a second time as a reversed array:

 public static void TestArrayReversal( ) {     int[] someArray = new int[5] {1,2,3,4,5};     for (int counter = 0; counter < someArray.Length; counter++)     {         Console.WriteLine("Element " + counter + " = " + someArray[counter]);     }     DoReversal(someArray);     for (int counter = 0; counter < someArray.Length; counter++)     {         Console.WriteLine("Element " + counter + " = " + someArray[counter]);     } }

This code displays the following:

 Element 0 = 1  The original array Element 1 = 2 Element 2 = 3 Element 3 = 4 Element 4 = 5 Element 0 = 5  The reversed array Element 1 = 4 Element 2 = 3 Element 3 = 2 Element 4 = 1

Reversing the elements in an array is a fairly common routine. The algorithm here swaps elements in the array until it is fully reversed. The DoReversal<T> method accepts a single parameter, theArray, which is a pointer to the first element in the array that is to be reversed.

The array is actually reversed inside of the for loop. The for loop counts from zero (the first element in the array) to a value equal to the array's length divided by two:

 for (int counter = 0; counter < (theArray.Length / 2); counter++)

Note that this is integer division, so if the array length is an odd number, the remainder is discarded. Since your array length is five, the for loop counts from zero to one.

Inside of the loop are three lines of code:

 tempHolder = theArray[counter]; theArray[counter] = theArray[theArray.Length - counter - 1]; theArray[theArray.Length - counter - 1] = tempHolder;

These three lines swap the first half of the array with the second half. As the for loop counts from zero, these three lines swap the first and last elements in the array. The loop increments the counter by one, allowing the second element and the next to last element to be swapped. This continues until all elements in the array have been swapped.

There is one element in the array that cannot be swapped; this is the middle element of an array with an odd number for the length. For example, in this code, there are five elements in the array. The third element should not be swapped. Put another way, all of the other elements pivot on this third element when they are swapped. This does not occur when the length of the array is an even number.

By dividing the array length by two, you can compensate for even or odd array elements. Since you get back an integer number from this division, you can easily skip over the middle element in an array with an odd length.