C Program to Reverse an Array

Algorithm to Reverse an Array in C

Reversing an array is one of the easiest problems while learning the arrays topic, while there are several methods to reverse an array in C, all of them are very easy and interesting, two of them being the most efficient solutions; Using an auxiliary array and In-place Swapping.

Let's discuss their algorithms:

Algorithm for reversing an array using an Auxiliary array

Let us assume we are given an array $arr$ of length $n$, the steps of the algorithm to reverse it will be:

1. Firstly, input the size $n$ and the elements of the array $arr$.
2. Initialize an auxiliary array $rarr$ of size same as the array $arr$.
3. Run a for loop with an integer $i = 0$, where $i \lt 0$ and $i$ increments by $1$ in each iteration.
4. Inside the for loop, assign $rarr[i]$ to be $arr[n - i - 1]$.
5. Then copy the elements of the array $rarr$ into the array $arr$.
6. Print the array $arr$.

Algorithm for Reversing an Array by In-place Swapping

Let us assume we are given an array $arr$ of length $n$, the steps of the algorithm to reverse it will be:

1. Firstly, input the size $n$ and the elements of the array $arr$.
2. Assign a pointer $l = 0$ at the first element of the array and a pointer $r = n - 1$ at the last element of the array.
3. Run a while loop while $l \lt r$.
4. Inside the while loop, initialize a $temp$ variable to store the value of $arr[l]$. Then assign $arr[l]$ to be $arr[r]$ and $arr[r]$ to be $temp$. Lastly, increment the pointer $l$ by $1$ and decrement the pointer $r$ by $1$.
5. The array $arr$ is reversed now, just print it using a for a loop.

1. Reverse Array in C By Printing It from the Last Element

This method is useful when we just want to print the reverse of the given array without modifying the original array or using another array to store the reverse of the original array.

Code

Output

Explanation

In the above implementation, we are printing the reverse of the given array by printing it from the last element to the very first element.

Complexity Analysis

Time Complexity: $O (n)$

While printing the reverse of the array $arr$, the whole of the array is traversed from the last element to the first element, i.e., $n$ iterations. Therefore, the time complexity of this method is $O(n)$.

Space Complexity: $O (1)$

No auxiliary space is used. Therefore its space complexity is $O(1)$.

2. Reverse Array in C Using Pointers

In this method, we are initializing an array using a pointer and then printing its reverse, this approach is very similar to the first one.

Code

Output

Explanation

In the above implementation, we are initializing an array using a pointer and then print its reverse by printing it from the last element to the very first element.

Complexity Analysis

Time Complexity: $O(n)$

While printing the reverse of the array $arr$, the whole of the array is traversed from the last element to the first element, i.e., $n$ iterations. Therefore, the time complexity of this method is $O(n)$.

Space Complexity: $O(1)$

No auxiliary space is used. Therefore its space complexity is $O(1)$.

3. Reverse Array in C Using Iterative Method

In this method, we are using another array $rarr$ to store the reverse of the given array $arr$, we do the same by iterating over the given array in a for loop and assigning the $(n - 1)th$ value of $arr$ to the first position of $rarr$ and so on.

Code

Output

Explanation

In the above implementation, we are reversing the array by assigning the element from reverse traversing the $arr$ array to the adjacent $rarr$ array element by traversing it. At last, we are printing the $rarr$ array.

Complexity Analysis

Time Complexity: $O(n)$

The whole of the array is traversed while reversing it. Therefore, the time complexity of this method is $O(n)$.

Space Complexity: $O(n)$

Another array $rarr$ of length $n$ is used to store the reverse of the array $arr$. Therefore its space complexity is $O(n)$.

4. Reverse Array in C Using an Auxiliary Array

In this method, we will be using an auxiliary array $rarr$ to temporarily store the reverse of the given array $arr$, and later we will modify the given array by copying $rarr$'s elements to the array $arr$.

Code

Output

Explanation

In the above implementation, we are using an auxiliary array $rarr$ and assigning its first element to be $arr$'s last element, and so on.

Complexity Analysis

Time Complexity: $O(n)$

The whole of the array is traversed while reversing it. Therefore, the time complexity of this method is $O(n)$.

Space Complexity: $O(n)$

An auxiliary array $rarr$ of length $n$ is used to store the reverse of the array $arr$. Therefore its space complexity is $O(n)$.

5. Reverse Array in C Using Function

In this method, we will use the same technique we used in the $4th$ approach, i.e., the auxiliary array. We will pass the array and its size to the function $reverse()$ which will reverse the given array $arr$.

Code

Output

Explanation

In the above implementation, we are reversing the array by calling the $reverse()$ function which uses the auxiliary array technique to reverse the array passed to it.

Complexity Analysis

Time Complexity: $O(n)$

The whole of the array is traversed while reversing it. Therefore, the time complexity of this method is $O(n)$.

Space Complexity: $O(n)$

Another array $rarr$ of length $n$ is used to store the reverse of the array $arr$. Therefore its space complexity is $O(n)$.

6. Reverse Array in C Using For Loop

In this method, we will use a for loop to fill the auxiliary array with elements from the input array $arr$ backward, and then copy the auxiliary array’s contents into the original one.

Code

Output

Explanation

In the above implementation, instead of reversing the original array $arr$, we are creating another array $rarr$ and filling it backward with the elements of $arr$ using a for a loop. As result, we get the reverse of the array $arr$ as the array $rarr$.

Complexity Analysis

Time Complexity: $O(n)$

The whole of the array is traversed while reversing it. Therefore, the time complexity of this method is $O(n)$.

Space Complexity: $O(n)$

Another array $rarr$ of length $n$ is used to store the reverse of the array $arr$. Therefore its space complexity is $O(n)$.

7. Reverse Array in C Using While Loop

In this method, we will use a while loop to fill the auxiliary array with elements from the input array $arr$ backward, and then copy the auxiliary array’s contents into the original one.

Code

Output

Explanation

In the above implementation, instead of reversing the original array $arr$, we are creating another array $rarr$ and filling it backward with the elements of $arr$ using a while loop. As result, we get the reverse of the array $arr$ as the array $rarr$.

Complexity Analysis

Time Complexity: $O(n)$

The whole of the array is traversed while reversing it. Therefore, the time complexity of this method is $O(n)$.

Space Complexity: $O(n)$

Another array $rarr$ of length $n$ is used to store the reverse of the array $arr$. Therefore its space complexity is $O(n)$.

8. Reverse Array in C by Swapping

In this method, instead of using an auxiliary array, we will use the in-place swapping technique.

Let's understand this method by an example, We are given an array $arr = [1, 5, 8, 5, 3, 55, 22, 2]$ of size $n = 8$, let us assign two pointers $l$ at the first element ($0 _ { th }$ position) and $r$ at the last element ($7 _ { th }$ position). The steps to reverse the array will be:

1. Swap the values at $l _ {th}$ position ($0$ index) and $r _ {th}$ position ($7$ index). The resultant array will be $[\mathbf {2}, 5, 8, 5, 3, 55, 22, \mathbf {1}]$. Increment $l$ by $1$ and decrement $r$ by $1$.
2. Swap the values at $l _ {th}$ position ($1$ index) and $r _ {th}$ position ($6$ index). The resultant array will be $[\mathbf {2}, \mathbf {22}, 8, 5, 3, 55, \mathbf {5}, \mathbf {1}]$. Increment $l$ by $1$ and decrement $r$ by $1$.
3. Swap the values at $l _ {th}$ position ($2$ index) and $r _ {th}$ position ($5$ index). The resultant array will be $[\mathbf {2}, \mathbf {22}, \mathbf {55}, 5, 3, \mathbf {8}, \mathbf {5}, \mathbf {1}]$. Increment $l$ by $1$ and decrement $r$ by $1$.
4. Swap the values at $l _ {th}$ position ($3$ index) and $r _ {th}$ position ($4$ index). The resultant array will be $[\mathbf {2}, \mathbf {22}, \mathbf {55}, \mathbf {3}, \mathbf{5}, \mathbf {8}, \mathbf {5}, \mathbf {1}]$. Increment $l$ by $1$ and decrement $r$ by $1$.
5. The $l$ pointer is at the $4th$ index and the $r$ pointer is at the $3rd$ index. We can only continue if $l \lt r$, that is not the case here so we will stop. Therefore the reversed array is $[\mathbf {2}, \mathbf {22}, \mathbf {55}, \mathbf {3}, \mathbf{5}, \mathbf {8}, \mathbf {5}, \mathbf {1}]$.

Let's see how to implement this method.

Code

Output

Explanation

In the above implementation, we are reversing the given array $arr$ using the in-place swapping technique by reading the elements from both ends of the array and swapping them.

Complexity Analysis

Time Complexity: $O(n)$

The pointer $l$ starts at $0th$ position and it increments by $1$ in each iteration and the pointer $r$ starts at $(n - 1)th$. The loop runs till $l$ and $r$ pointer meet, so there are total $n / 2$ iterations. Therefore, the time complexity will be $O(n)$.

Space Complexity: $O(1)$

No auxiliary space is used in this method. Therefore its space complexity is $O(1)$.

9. Reverse Array in C Using Recursion

In this method, we will use recursion to implement the in-place swapping technique that we discussed in the previous approach. Instead of a for loop, we are just using an $if$ condition which runs if $l \lt r$, swaps elements at $l _ { th }$ and $r _ { th }$ position and then calls the $reverse ( arr, l + 1, r - 1 )$ function.

Code

Output

Explanation

In the above implementation, we are reversing the given array $arr$ using the in-place swapping technique by reading the elements from both ends of the array and swapping them.

Complexity Analysis

Time Complexity: $O(n)$

The reverse function is a recursive function that runs till $l$ is less than $r$, which would take $n / 2$ recursive calls. Therefore, the time complexity is $O(n)$.

Space Complexity: $O(n)$

A stack data structure is used for memory allocation when a recursive function is called. Therefore, its space complexity is $O(n)$.