Reverse an array in C++
This post will discuss how to reverse an array in C++.
1. Using reverse() function
The recommended solution for reversing elements of the specified array is to use the reverse() method defined in the algorithm header file.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <algorithm> using namespace std; // Utility function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Utility function to reverse elements of an array void reverse(int arr[], int n) { reverse(arr, arr + n); } int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, n); print(arr, n); return 0; } |
2. In-place Implementation
The standard solution is to read the elements from both ends of the array and swap them. This can be done in-place, as demonstrated below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <algorithm> using namespace std; // Utility function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Utility function to reverse elements of an array void reverse(int arr[], int n) { for (int low = 0, high = n - 1; low < high; low++, high--) { swap(arr[low], arr[high]); } } int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, n); print(arr, n); return 0; } |
3. Using Stack
Another plausible way of reversing an array is to use the stack data structure. The idea is to push each array element into a stack. Then pop values from the stack one by one and assign each popped item back to the original array starting from the beginning.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> #include <stack> using namespace std; // Utility function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Utility function to reverse elements of an array void reverse(int arr[], int n) { // create an empty stack of integers stack<int> stack; // push each array element into a stack for (int i = 0; i < n; i++) { stack.push(arr[i]); } // start from index 0 int index = 0; // pop values from the stack until it becomes empty while (!stack.empty()) { // assign each popped item back to the original array arr[index++] = stack.top(); stack.pop(); } } int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, n); print(arr, n); return 0; } |
4. Using Recursion
We can also use recursion for reversing an array. The logic remains the same as the in-place implementation discussed above, but requires O(n) extra space for the call stack.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <algorithm> using namespace std; // Utility function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Recursive function to reverse elements of a subarray formed // by `arr[low, high]` void reverse(int arr[], int low, int high) { if (low < high) { swap(arr[low], arr[high]); reverse(arr, low + 1, high - 1); } } int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, 0, n-1); print(arr, n); return 0; } |
Here is another recursive program that stores elements of the array into the call stack, and then put them back into the array in the correct order as the recursion unfolds.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> using namespace std; // Utility function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Utility function to reverse elements of an array void reverse(int arr[], int i, int n) { // base case: end of the array is reached or array index out-of-bounds if (i >= n) { return; } // store next element of the array int value = arr[i]; // reach the end of the array using recursion reverse(arr, i + 1, n); // put elements in the call stack back into the array // starting from the beginning arr[n - i - 1] = value; } int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, 0, n); print(arr, n); return 0; } |
5. Using Auxiliary Array
Finally, we can create an auxiliary array of the same type and size as the input array, fill it with elements from the original array in reverse order, and then copy the contents of the auxiliary array into the original one.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> using namespace std; // Utility function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Utility function to reverse elements of an array void reverse(int arr[], int n) { int aux[n]; for (int i = 0; i < n; i++) { aux[n - 1 - i] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = aux[i]; } } int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, n); print(arr, n); return 0; } |
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)