Tag Archives: loop

Array reversal

In this post I would be discussing array reversal. Array reversal means reversing the order of elements in an array.

array reversalAnΒ  array can be reversed using various approaches, the simplest is by using another array. But, using another array requires double memory and hence is not a very good approach. Another approach is of reversing an array is to swap the first element with the last element, second element with the second last element and so on. The process of swapping would stop once we reach the halfway mark since all the elements would be swapped by then. Let us see the process with the help of an example:

1 2 3 4 5 6 
^         ^
6 2 3 4 5 1
  ^     ^

6 5 3 4 2 1
    ^ ^

6 5 4 3 2 1

The caret sign (^) marks the elements being swapped. The Java program for array reversal is as follows:

class ReverseArray{
    public static void displayArray( int []a ){
        for( int n: a ){
            System.out.print( n + " " );
        }
        System.out.println();
    }
    public static int[] reverseArrayIterative( int []a ){
        int half = a.length / 2, temp;
        for(int i = 0; i <= half ; i++ ){
            temp = a[ i ];
            a[ i ] = a[ a.length-i-1 ];
            a[ a.length-i-1 ] = temp;
        }
        return a;
    }
    public static void main( String args[] ){
        int []a = { 1, 2, 3, 4, 5, 6 };
        displayArray( a );
        a = reverseArrayIterative(a);        
    }
}

In the above Java program on array reversal the function displayArray() is a helper function to display the array. The displayArray function uses enhanced for loop which I have already discussed in an earlier post. The function reverseArrayIterative() accepts an integer array as an argument and returns the array after sorting as discussed above.

The above program on reversing an array can also be done using recursion. We can use two variables, say left and right, such that left is increased and right is decreased as the elements at position left and right are swapped. The base condition or the exit condition be when left >Β  right. The Java program for array reversal using recursion as discussed above is as follows:

class ReverseArray{
    public static void displayArray( int []a ){
        for( int n: a ){
            System.out.print( n + " " );
        }
        System.out.println();
    }
    public static int[] reverseArrayRecursive( int []a ){
        return reverseArrayRecursive(a, 0, a.length - 1 );
    }
    private static int[] reverseArrayRecursive( int []a, int left, int right ){
        if( left > right ) return a;
        else{
            int temp = a[ left ];
            a[ left ] = a[ right ];
            a[ right ] = temp;
            return reverseArrayRecursive(a, left+1, right-1 );
        }
    }
    public static void main( String args[] ){
        int []a = { 1, 2, 3, 4, 5, 6 };
        int []b = { 1, 2, 3, 4, 5 };
        a = reverseArrayRecursive( a );
        b = reverseArrayRecursive( b );
        displayArray( a );
        displayArray( b );
    }
}

Note that the function reverseArrayRecursive() is overloaded. The function which is public is the one which would be invoked for reversing the array. The function which is private would be invoked by the public function with the correct initial values. The private function would recursively call itself to reverse the array as discussed above. I would like to emphasize here, that iterative method of array reversal is more efficient due to time and memory overheads in case of recursion.

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.