Hello geeks 😁, in this article we are going to discuss
- What reversing an Array means
- Different algorithms to reverse an array
- Time complexity of each code
Understanding the Question
Array is a data structure in which elements are stored in contiguous memory location.
Reversing the elements in array means changing the order of elements such that first element becomes last and the last element becomes first, Second becomes second last and so on .
This process continues until all the elements are reversed .
To understand this more clearly, let us consider an integer array with 6 elements : [1,2,3,4,5,6]
The reversed array of the above would look something like
How to approach ?
There are multiple approaches to solve the above given problem
1) Using a Temporary Array
As the name suggests here , we will be storing the values of our original array in a new array temp[] but, we will iterate in reverse order while storing the elements, it means that we will start storing elements into our temporary array from the last index of the original array . The value at the last index will be stored first followed by the second last and so on .
We can use a for loop or a while loop to iterate over the indexes . Let the size of array be n so the first index will be denoted by 0 and the last index will be denoted by n-1
The iteration will look something like:
Algorithm
1) Create a new array called temp
2) Store Value in temp by iterating in reverse order in given array
3) Store values of temp in original array
C++ code
#include <bits/stdc++.h>
using namespace std;
// Function to reverse array
void reverse(int arr[], int n) {
int temp[n];
int k = 0;
for (int i = n - 1; i >= 0; i--)
{
temp[k] = arr[i];
k++;
}
for (int i = 0; i < n; i++)
{
arr[i] = temp[i];
}
}
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // function calling
reverse(arr, n); // Displaying the array
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}C code
#include <stdio.h>
// Function to reverse array
void reverse(int arr[], int n)
{
int temp[n];
int k = 0;
for (int i = n - 1; i >= 0; i--)
{
temp[k] = arr[i];
k++;
}
for (int i = 0; i < n; i++)
{
arr[i] = temp[i];
}
}
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
// function calling
reverse(arr, n);
// Displaying the array
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}Java code
public class reverse {
// function to reverse array
static void reverse_array(int arr[], int n) {
int temp[] = new int[n];
int k = 0;
for (int i = n - 1; i >= 0; i--) {
temp[k] = arr[i];
k++;
}
for (int i = 0; i < n; i++) {
arr[i] = temp[i];
}
}
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// function calling
reverse_array(arr, arr.length);
// Displaying the array
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
Time Complexity : The time complexity of the above algorithm is O(n).
Space Complexity : The space Complexity of above algorithm is O(n).
2) Iterative way
In this approach we would be iterating over the array from both the ends and will swap the elements of the array successively.
For eg :
Consider an integer array with 6 elements : [0,1,2,3,4,5]
Now we will using two pointers . First pointer will be at start of the array and the other one will be at the end and we will be iterating both as follows:
0 will get swapped with 5
1 will get swapped with 4
2 will get swapped with 3
Final Array
Algorithm
1) Initialize p1 to start index of array and p2 to last index of array
Repeat the following steps while p1<p2
2) Swap the element arr[p1] with arr[p2]
3) increment p1 by 1 , decrement p2 by 1
C++ code
#include <bits/stdc++.h>
using namespace std;
// function to reverse the elements of array
void reverse(int arr[], int n)
{
int p1 = 0, p2 = n - 1;
while (p1 < p2)
{
swap(arr[p1], arr[p2]);
p1++;
p2--;
}
}
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// function calling
reverse(arr, n);
// displaying the array
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}C code
#include <stdio.h>
// function to reverse the elements of array
void reverse(int arr[], int n)
{
int p1 = 0, p2 = n - 1;
while (p1 < p2)
{
// swap the elements of array
int t = arr[p1];
arr[p1] = arr[p2];
arr[p2] = t;
p1++;
p2--;
}
}
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// function calling
reverse(arr, n);
// displaying the array
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
Java code
public class iterative {
// function to reverse an array
static void reverse(int arr[], int n) {
int p1 = 0;
int p2 = n - 1;
while (p1 < p2) {
int t = arr[p1];
arr[p1] = arr[p2];
arr[p2] = t;
p1++;
p2--;
}
}
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 3, 4, 5 };
// function call
reverse(arr, arr.length);
// displaying the array
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
Time Complexity: The time complexity of the above approach is O(n).
Space Complexity: The space complexity of the above approach is O(1).
3)Recursive Method
Recursion is a very easy approach to reverse an array if you understand the Iterative way.
Here we would be using two pointers p1 and p2, one which will point at the first element and other will point at the last element of the array . Next step is to swap the elements i.e. if the array name is arr1 then swap(arr1[p1],arr1[p2]). Then we will call the recursive function for the remaining array.
Algorithm
1) Initialize p1 to start index of array i.e. 0 and p2 to last index of array i.e. n-1
2) swap (arr[p1], arr[p2])
3) Recursively call the function for rest of the array
C++ code
#include <bits/stdc++.h>
using namespace std;
// function to reverse array
void reverse(int arr[], int p1, int p2)
{
if (p1 >= p2) // condition to terminate recursive calls
{
return;
}
swap(arr[p1], arr[p2]); // swapping the elements of the array
reverse(arr, p1 + 1, p2 - 1); // recursive call
}
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// function calling
reverse(arr, 0, n - 1);
// dsplay the array
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0
}C code
#include <stdio.h>
// function to reverse array
void reverse(int arr[], int p1, int p2)
{
if (p1 >= p2) // condition to terminate recursive calls
{
return;
}
// swapping the elements of the array
int t = arr[p1];
arr[p1] = arr[p2];
arr[p2] = t;
reverse(arr, p1 + 1, p2 - 1); // recursive call
}
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// function calling
reverse(arr, 0, n - 1);
// dsplay the array
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}Java code
public class recusrsive_reverse {
// function to reverse the array
static void reverse(int arr[], int p1, int p2) {
if (p1 >= p2) { // condition to terminate the recursive call
return;
}
// swap the array elements
int t = arr[p1];
arr[p1] = arr[p2];
arr[p2] = t;
reverse(arr, p1 + 1, p2 - 1); // recursive call
}
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 3, 4, 5};
// function calling
reverse(arr, 0, arr.length - 1);
// displaying the array
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}Time Complexity: The time complexity of the above approach is O(n).
Space Complexity: The space complexity of the above approach is O(n).
4)Using Library Functions
The easiest way to reverse an array is by using the Library functions available in C++.
Approach
In C++ we can use reverse() function which is available in STL .
C++ code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
reverse(arr, arr + n); // STL function to reverse the array
// display the array
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}FREQUENTLY ASKED QUESTIONS
1) What is easiest way of reversing an array ?
Answer: Easiest Way of reversing the elements of an array is by using the reverse() function available in the STL of C++.
2)How can we reverse a given array ?
Answer: There are mainly three methods of reversing an array
- Using a temporary array
- Iterative way
- Recursive method
3)How to reverse a given array without creating a new array ?
Answer: Array can be reversed by using Recursive way or Iterative way. They wont involve creation of a new array in their algorithms.
4)How to reverse an array in C++?
Answer: In C++ array can be reversed by using STL function reverse() or by using iterative way, recursive method, or by using a temporary array.
Conclusion
In this tutorial we learnt about the different ways of reversing the array. The same method can be applied for arrays of different data types.
Also read : How to Reverse A Linked List in Groups of Given Size
