Array operations - Traversal, Copy, Reverse, Sort in C++
Written by
Arrays are a group of similar data types stored in contiguous memory locations. Elements of an array can be accessed using the indices. The index of an array starts from 0. Hence, an array of size n has an index ranging from 0 to n-1 A variety of operations can be performed on arrays such as Sorting, Searching, Traversal, Insertion, Deletion etc.
We shall discuss traversing, copying, reversing and sorting in this section.
Traversing:
Traversal refers to accessing each element of the array in a sequential format. Since an array is a linear data structure, it is rather easy to extract the element data as compared to other data structures like Linked lists, stacks, queues etc.
Array traversal plays an integral part in any array operation, as it is a fundamental step for inserting an element in an array, searching an element, and even sorting an array.
Below is the algorithm describing basic array traversal.
Algorithm:
- Step 1: Declare an array
a[]. - Step 2: Initialize variable
size - Step 3: Initialize variable
i = 0 - Step 4: Apply the specified operation on
a[i] - Step 5: Increment
iby 1 - Step 6: Repeat steps 4 and 5 until
i <= size-1 - Step 7: Stop.
Let us take a simple example of calculating the total marks obtained based on an array of 3 marks provided to us.
Similarly, the traversal algorithm can also be used to club two or more operations. Following the above example, now let us provide the three subject marks as input in the form of an array and generate its sum.
Source Code:
#include<stdio.h>
#include<conio.h>
void main() {
int n, a[10], i, sum = 0;
printf("\n Enter the array size ");
scanf("%d", & n);
for (i = 0; i < n; i++) {
printf("\n Enter Marks %d\n", i + 1);
scanf("%d", & a[i]);
sum += a[i];
}
printf("\n The total marks are: %d ", sum);
getch();
}
Output:
Enter the array size 5
Enter Marks 1
60
Enter Marks 2
76
Enter Marks 3
56
Enter Marks 4
87
Enter Marks 5
88
The total marks are: 367
Copying:
Copying an array refers to replicating it in another array of the same size or one greater than the original array.
The elements are copied using array indexing.
Algorithm:
- Step 1: Declare two arrays a[ ], b[ ].
- Step 2: Initialize variable ‘size’
- Step 3: Initialize variable i = 0
- Step 4: Accept elements into a[ ]
- Step 5: Assign the same elements to b[ ] and exit loop
- Step 6: Print the copied array.
- Step 7: Stop.
Source Code:
#include<stdio.h>
int main() {
int a[20], b[20], i, size;
printf("\nEnter the size of the array :");
scanf("%d", & size);
//Accepting values into Array
printf("\nEnter the array elements :");
for (i = 0; i < size; i++) {
printf("\n Enter Element %d\n", i + 1);
scanf("%d", & a[i]);
b[i] = a[i]; // Copying data from source array A to destination array 'b
}
//Printing of all elements of the array
printf("The copied array is as follows:");
for (i = 0; i < size; i++) {
printf("\nb[%d] = %d", i, b[i]);
}
return (0);
}
Output:
Enter the size of the array: 4
Enter the array elements:
Enter Element 1
5
Enter Element 2
8
Enter Element 3
9
Enter Element 4
2
The copied array is as follows:
b[0] = 5
b[1] = 8
b[2] = 9
b[3] = 2
An array can also be copied using functions with the original array passed as pointers. A predefined array can also be conveniently copied into another array of the same or greater size.
Reversing:
Reversing an array can be achieved in multiple ways. Some easy techniques to do so are:
i) Printing the same array in reversed order.
ii) Copying the array in reversed order into another array.
We will see the latter technique, given below is the algorithm to store and display a reversed array.
Algorithm:
- Step 1: Initialize arrays a[ ] and b[ ]
- Step 2: Initialize a size variable along with i and j.
- Step 3: Input array elements using the for loop.
- Step 4: Initialize a for loop with i=0 and j=size-1.
- Step 5: Assign the last element of a to the first element of b.
- Step 6: Copy the elements of b into a and print a.
- Step 7: Stop
Source Code:
#include<stdio.h>
int main() {
int a[20], b[20], i, j, size;
printf("\nEnter the size of the array :");
scanf("%d", & size);
//Accepting values into Array
printf("\nEnter the array elements :");
for (i = 0; i < size; i++) {
printf("\n Enter Element %d\n", i + 1);
scanf("%d", & a[i]);
}
for (i = size - 1, j = 0; i >= 0; i--, j++)
b[j] = a[i];
//Overwriting the array
for (i = 0; i < size; i++)
a[i] = b[i];
printf("The Reversed array is\n");
for (i = 0; i < size; i++)
printf("%d\n", a[i]);
return 0;
}
Output:
Enter the size of the array:5
Enter the array elements :
Enter Element 1
45
Enter Element 2
23
Enter Element 3
66
Enter Element 4
87
Enter Element 5
99
The Reversed array is
99
87
66
23
45
Sorting: Organizing or arranging the array elements in a definite order i.e, ascending or descending is known as sorting an array. The output of a sorting program produces a reordered input or its permutation.
Sorting can be achieved using multiple sorting techniques like Bubble, Selection, Insertion, Quick and Merge sorts. We will discuss sorting an array of elements using bubble and selection sort- considered to be the easiest of them all.
Bubble Sort: The bubble sort, compares each pair of adjacent elements and swaps them if they are in the incorrect order until the entire array is sorted. It basically pushes the largest element to the end of the list.
**Algorithm: **
- Step 1: Input an array of elements.
- Step 2: Declare a temporary variable for swapping the elements
- Step 3: Use a nested for loop to compare the elements and traverse through the array
- Step 4: If a variable ‘j’ represents the element in question then if j is greater than that of j+1, then the elements are swapped using the temporary variable.
- Step 5: Continue swapping until both the iterations are complete and the outer loop’s condition evaluates to false. Hence, the array is sorted.
Source Code:
#include <stdio.h>
int main() {
int i, j, temp, size, arr[30];
printf("Enter the size of the array: \n");
scanf("%d", & size);
printf("Enter the array elements: \n");
for (i = 0; i < size; ++i) {
printf("\n Enter Element %d\n", i + 1);
scanf("%d", & arr[i]);
}
for (i = 0; i < size; i++){
for (j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]){ // if current element > i+1th element, perform swap.
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("\nThe sorted array is as given below: \n");
for (i = 0; i < size; ++i)
printf("%d\n", arr[i]);
return 0;
}
Output:
Enter the size of the array:
5
Enter the array elements:
Enter Element 1
35
Enter Element 2
44
Enter Element 3
68
Enter Element 4
13
Enter Element 5
79
The sorted array is as given below:
13
35
44
68
79
Selection Sort: The selection sort technique identifies the smallest element in the array or list and moves it to the beginning of the list. This process is repeated until all the elements in the list are sorted. A selection sort requires n-1 passes to sort an array containing n elements. The algorithm is fairly similar to the bubble sort algorithm with the main principle being reversed. Follow the below program to understand the algorithm.
Source Code:
#include <stdio.h>
int main(){
int i, j, temp, size, arr[30], t;
printf("Enter the size of the array: \n");
scanf("%d", & size);
printf("Enter the array elements: \n");
for (i = 0; i < size; ++i) {
printf("\n Enter Element %d\n", i + 1);
scanf("%d", & arr[i]);
}
for (i = 0; i < size; i++){
t = i;
for (j = i + 1; j < size; j++){
if (arr[j] < arr[t]) t = j;
}
temp = arr[i];
arr[i] = arr[t];
arr[t] = temp;
}
printf("\nThe sorted array is as given below: \n");
for (i = 0; i < size; ++i)
printf("%d\n", arr[i]);
return 0;
}
Output:
Enter the size of the array:
5
Enter the array elements:
Enter Element 1
32
Enter Element 2
24
Enter Element 3
26
Enter Element 4
13
Enter Element 5
99
The sorted array is as given below:
13
24
26
32
99
