Friday, May 10, 2013

Reversing an array

In this post we will discuss a simple problem on Arrays. Given an array of numbers, how do we reverse it efficiently?

Here is the simple and effective approach. We start with one index pointing to the start, and another index pointing to the end of the array. We swap the two elements at these indices, increment left index, and decrement right index. We continue this procedure until both indices meet each other. Then we stop. At the end, the array is reversed.

For example, let us consider the array with 5 elements, Here is how it works

Array: [1  2  3  4  5] - swap
        |           |
       left       right
      
       [5  2  3  4  1] - swap
           |     |
          left  right
      
       [5  4  3  2  1] - stop
              |
             left
             right


 
#include <iostream>
#include <string>

using namespace std;

void swap( int &a, int &b)
{
 int temp = a;
 a = b;
 b = temp;
}
//function to reverse the array
void reverseArray(int *array, int n)
{
 int low = 0; //initialize low to first element
 int high = n-1; //initialize high 

 while( low < high ) //until both ends meet
 {
  swap( array[low], array[high] ); //swap the elements
  low++; //increment left
  high--;//decrement right
 }
}
void printArray( int *array,int n)
{
 for(int i = 0 ; i < n;i++ )
 {
  cout<<array[i]<<" ";
 }
 cout<<endl;
}
int main()
{
 int n;
 cin>>n;
 int* array = new int[n];
 int i;

 for( i = 0 ; i < n ; i++)
 {
  cin>>array[i];
 }
 reverseArray( array, n);
 printArray( array, n);
 return 0;
}