The reverse of this array is:
the characters become in reverse order, in the initializer_list. Note that in the reverse order, letter, ‘O’ remains at its position. This is because the number of elements in the array is odd.
Consider now the following array:
The reverse of this array is:
the characters become in reverse order, in the initializer_list. This time, the middle two elements are swapped because the number of elements in the array is even.
There are various ways of reversing the array, and this article explores those ways.
Article Content
– Using an Extra Array for Reversing
– Reverse Array by Swapping Elements
– Reversing Array using a Recursive Function
Using an Extra Array for Reversing
With this method, create another array of the same type and size as the original array but empty. Next, read the first array from the back and fit in the elements in the second array from the front using a for-loop. The following program illustrates this:
using namespace std;
int main()
{
char arrF[] = {'M', 'N', 'O', 'P', 'Q'};
int size = sizeof(arrF)/sizeof(arrF[0]); //obtaining the size of the array
char arrR[size];
for(int i=0,j=size-1; j>=0; i++,j--) {
arrR[i] = arrF[j];
}
for(int i=0; i<size; i++) {
cout<<arrR[i] << ' ';
}
cout<<endl;
return 0;
}
The output is:
The first statement in the C++ main function creates the first array without indicating the size. The second statement obtains the size by dividing the total size of the array in bytes by the size of the first element of the array (after all, all the elements of a C++ array, are of the same type). The next statement creates the second array of the same type and size, but empty.
The code segment after is the for-loop. The for-loop copies the last element of the first array, and puts it in the first position of the second array. It copies the last-but-one element of the first array and puts in the second position of the second array. It copies the third-to-last element of the first array and puts in the third position of the second array and until the variable index, i that is “moving-up” the second array reaches the last element of the second array at index size-1. Index, j “moves down” the first array from size-1 to 0. i moves up the second array while j moves down the first array.
In the parentheses of the for-loop, i and j are declared in the first statement. As long as j is greater than or equal to zero, the copying will continue – that is the while-condition. The increment of i and decrement of j, form the last statement in the parentheses.
The last for-loop prints out the elements of the second array.
Reverse Array by Swapping Elements
The last and first elements can be swapped for the only array. The last-but-one and second elements can be swapped for this same array. The third-to-last and third elements can be swapped and until the middle point of the array is reachedre and swapping stops. If the number of elements is odd, the middle element does not change its position. If the number of elements is even, then there are two middle elements which are swapped.
Again, there are two index variables: i and j but for one array only. i is incremented and j is decremented for each iterationr until they almost meet. The while-condition for this is, (i < j). The following program, illustrates this method:
using namespace std;
int main()
{
char arr[] = {'M', 'N', 'O', 'P', 'Q'};
int size = sizeof(arr)/sizeof(arr[0]);
for(int i=0,j=size-1; i< j; i++,j--) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for(int i=0; i<size; i++) {
cout<<arr[i] << ' ';
}
cout<<endl;
return 0;
}
The output is:
Reversing Array using a Recursive Function
A recursive function is a function that keeps calling itself until a condition is met. This is better explained with an example. Consider the following top part of the program:
using namespace std;
char arr[] = {'M', 'N', 'O', 'P', 'Q'};
int siz = sizeof(arr)/sizeof(arr[0]);
void reverseArray(char arr[], int i){
//base condition
if(i==siz)
return;
char element = arr[i]; //extracting element
reverseArray(arr, i+1); //recursive call
arr[siz-i-1] = element; //traceback
}
The array is declared and the size of the array is determined as siz (without e). After that in the code is the recursive function definition. The first code segment in the function (if-construct) is the condition to be met. The i is the index variable for accessing the array elements from index 0 to index siz-1. When i is equal to siz, the function returns and stops calling itself.
The C++ main function has the call,
This calls the recursive function with two arguments: the first is the name of the array; the second is the beginning index for i, zero.
When the function is called the first time, ‘M’ is assigned to a location in memory identified by element. After that statement, the function is called again within the function with “reverseArray(arr, i+1);”. The last statement in the function has not been attended to. This time the function is called with i = 1; and ‘N’ is assigned to a different memory location, still identified by, element.
The third time the function is called, i = 2; and ‘O’ is assigned to a third memory location still identified byrem element. The fourth time the function is called, i = 3; and ‘P’ is assigned to a fourth memory location remstill identified by element. The fifth time the function is called, i = 4; and ‘Q’ is assigned to a fifth memory location still identified by element.
The sixth time the function is called, i = 5 which is the size of the array and the function returns due to the if-construct. All this while, the last statement in the function has not been attended to. This last statement is:
With this statement, whatever is held by element, is assigned to an array position. Remember that there are five locations in memory with the identifier element holding the characters: ‘M’, ‘N’, ‘O’, ‘P’, ‘Q’, in that order.
It is true that the function has returned void, but the last statement still has to be executed, five times. For each call of the function, the last statement was recorded once, in memory. The first time it executes, siz-i-1 = 5 – 0 – 1 = 4; at the call for which the function returns, but using the first index. And so,
going backwards. The second time the last statement executes, siz-i-1 = 5 - 1 – 1 = 3. And so,
arr[3] = 'P'
The third time the last statement executes, siz-i-1 = 5 - 2 – 1 = 2. And so,
arr[2] = 'O'
The fourth time the last statement executes, siz-i-1 = 5 - 3 – 1 = 1. And so,
arr[1] = 'N'
The fifth and last time the last statement executes, siz-i-1 = 5 - 4 – 1 = 0. And so,
arr[0] = 'M'
And so the array has been reversed with a recursive function.
Use of std::reverse()
The std::reverse() of the algorithm library can also be used to reverse an array though it is not obvious. To use this function, the algorithm library has to be included into the program. The prototype for the function is:
constexpr void reverse(BidirectionalIterator first, BidirectionalIterator last);
The first argument is an iterator pointing to the first element of a container. The second argument is another iterator pointing just after the last element of the container. A pointer to the first element of the array can be used as the first argument. A pointer pointing just after the last element of the array can be used as the second argument.
If the array name is arr, then a pointer to the first element is arr. A pointer pointing just after the last element of the array is “arr + size” where size is the size of the array. The following program, shows how std::reverse() can be used to reverse an array:
#include <algorithm>
using namespace std;
char arr[] = {'M', 'N', 'O', 'P', 'Q'};
int siz = sizeof(arr)/sizeof(arr[0]); //size of array
int main()
{
reverse(arr, arr+siz);
for(int i=0; i<siz; i++) {
cout<<arr[i] << ' ';
}
cout<<endl;
return 0;
}
The output is:
Conclusion
Reversing an array can be done, using an Extra Array, by Swapping Array Elements, by using a Recursive Function, or by using std::reverse().
from https://ift.tt/BEpHf1I
0 Comments