Reverse an array in C
In this post, we will see how to reverse an array in C in linear time.
1. Using Auxiliary Array
A simple solution is to create an auxiliary array of the same type and size as the input array, fill it with elements from the input array backward, and then copy the auxiliary array’s contents into the original one. The time complexity of this solution is O(n) and requires O(n) extra space, where n is the size of the input.
|
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 |
#include <stdio.h> // Function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } // 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(void) { 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 above implementation requires O(n) extra space for the auxiliary array. A linear in-place algorithm can be implemented by reading the elements from both ends of the array and swap them, 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 31 |
#include <stdio.h> // Function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } // Function to reverse elements of an array void reverse(int arr[], int n) { for (int low = 0, high = n - 1; low < high; low++, high--) { int temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } } int main(void) { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, n); print(arr, n); return 0; } |
3. Using Recursion
We can easily convert the above code to use the recursion. The logic remains the same as the above iterative implementation but requires O(n) implicit 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 34 |
#include <stdio.h> // Function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", 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) { int temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; reverse(arr, low + 1, high - 1); } } int main(void) { 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’s another recursive program that stores elements into the call stack and then put them back into the array in the correct order when 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 |
#include <stdio.h> // Function to print contents of an array void print(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } // Function to reverse elements of an array void reverse(int arr[], int i, int n) { // base case: end of an array is reached or array index out-of-bounds if (i >= n) { return; } // store the next array element 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 // in the correct order arr[n - i - 1] = value; } int main(void) { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr)/sizeof(arr[0]); reverse(arr, 0, 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 :)