Back Button
Back to Chapter
C++ Introduction
No items found.
C++ Basics
No items found.
C++ Control Statements
No items found.
C++ Logical Operators
No items found.
C++ Procedural Programming
No items found.
C++ Structural Programming
No items found.
C++ Implementation of OOPS
No items found.
C++ Arrays and Vectors
No items found.
C++ Error Handling
No items found.
C++ File Handling
No items found.
Collapse_Icon
Table of Contents

We already learned in C++ data types what an array is and how to declare an array now we will learn about the different operations we can perform on arrays.

Searching

Suppose you store the roll number of students in an array, now you need to find a specific roll number like 12 or 25 what is the approach you would take to search for this roll number.

The first and most obvious approach would be to start from the first element and go through the entire array until the last roll number. This is known as linear search.

The second approach would be to arrange all the numbers in ascending order and check if the required roll number is the same as the middle element of the array. If it is the same you have found the roll number if not, we make the array half of the required number is lesser than the middle number we make the middle element as the last element or if the required number is greater than the middle number, it becomes the first element of the array, and this process is repeated until the required element is found. This is known as binary search.

Linear Search

The diagram below gives us an idea of how our algorithm works.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/47154823-9f2e-4fe4-ba10-4045f49cabb2/Untitled_Diagram_(37).png

Let us try converting this flowchart in to C++ code.

int a[5]={12,40,50,26,7}; for(int i=0;i<5;i++) { if(a[i]=50) { cout<<"element found at:"<
Output: element found at:3

Binary Search

The figure below shows a flow chart of binary search to find 33 in the given array.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f90b2a01-638e-41d4-b078-c328e6683b3d/Untitled_Diagram_(38).png

We use the formula int mid = low + (high – low)/2 to find out the middle element.

Now let us try to write a C++ code for this.

int a[7]={10,13,23,26,28,30,33,35}; int Low=0; int High=7; int mid=Low+ (High-Low)/2; int flag =0; while(Low<=High) { if(a[mid]== 33) { flag=1; break; } else if(a[mid}<33) { Low=mid+1; } else { high=mid-1; } }

Insertion

To insert an element into an array

  1. First get the element to be inserted, say a
  2. Then get the position at which this element is to be inserted, say positionX
  3. Then shift the array elements from this position to one position forward, and do this for all the other elements next to positionX.
  4. Insert the element a now at the position positionX, as this is now empty.
https://s3-us-west-2.amazonaws.com/secure.notion-static.com/111e7e74-31e1-46be-8632-b9b6408df93c/Untitled_Diagram_(44).png

C++ code for this is

#include using namespace std; // Function to insert x in arr at position positionX int* insertA(int n, int arr[], int a, int pos) { int i; // increase the size by 1 n++; // shift elements forward for (i = n; i >= pos; i--) arr[i] = arr[i - 1]; // insert a at positionX arr[pos - 1] = a; return arr; } // Driver Code int main() { int arr[100] = { 0 }; int i, a, positionX, n = 10; // initial array of size 10 for (i = 0; i < 10; i++) arr[i] = i + 1; // print the original array for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; // element to be inserted a = 50; // position at which element is to be inserted pos = 5; // Insert x at posOutput insertA(n, arr, a, positionX); // print the updated array for (i = 0; i < n + 1; i++) cout << arr[i] << " "; cout << endl; return 0; }
Output: 1 2 3 4 5 6 7 8 9 10 1 2 3 4 50 5 6 7 8 9 10

Sorting

Suppose we need to use binary search to find an element in an unsorted array, that is an array in which the numbers are not arranged in ascending or descending order. It becomes impossible to use binary search in such a case, so we first sort the array in ascending order and then use binary search to find the element.

Another scenario where sorting is necessary is storing records of students in a school based on the name of the student to assign roll numbers.

Sorting refers to storing the elements of an array in descending or ascending order.

We will learn 2 sorting algorithm in this section.

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are not in ascending order.

Consider the array given in the figure

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/a36aecd1-6a50-44aa-b051-49315dba3ba1/Untitled_Diagram_(39).png

After the first pass we see that some elements are still unsorted so the second pass.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/0d435a9b-e67d-46d1-8f1b-fd283efe412f/Untitled_Diagram_(40).png

Even after the second pass we see that 2 and 8 are still unsorted so the third pass.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/3aa74a77-edc3-4ecb-9626-cfafa683a2a6/Untitled_Diagram_(41).png

Now the array is sorted but the compiler runs one final check to confirm the array is sorted

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d81ab708-af78-4d5c-99e4-af128cd687e1/Untitled_Diagram_(42).png

No elements are swapped and the sorted array is displayed.

Let us write the code for bubble sort now

#include using namespace std; void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } // to implement bubble sort void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) // Last i elements are already in place for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); } /* Function to display an array */ void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } // Driver code int main() { int arr[] = {10, 8, 2, 15, 20, 23}; int n = 6 bubbleSort(arr, n); cout<<"Sorted array: \n"; printArray(arr, n); return 0; }
Output: Sorted array: 2 8 10 15 20 23

Insertion Sort

In this algorithm elements are inserted at their appropriate place. Consider the figure to understand the working of insertion sort better.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c2ee44eb-8c64-47a8-be82-5b6c3c054d90/Untitled_Diagram_(43).png

To sort an unsorted array

First start from array[1] untill array[n].

Compare the current element to its predecessor.

If the current element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Now let us write the C++ code for this.

#include using namespace std; void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // A function to print an array of size n void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } /* Driver code */ int main() { int arr[] = {10,13,2,5,9,20,21}; int n = 7; insertionSort(arr, n); printArray(arr, n); return 0; }
Output: 2 5 9 10 13 20 21

Deletion

To delete an element from the array at desired Location we move the successive elements backward by one position and decrement the size of the array.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7318092d-e9a0-4994-8368-0079973cc12a/Untitled_Diagram_(45).png
// C++ program to remove a given element from an array #include using namespace std; // This function removes an element a from arr[] and // returns new size after removal (size is reduced only // when x is present in arr[] int deleteElement(int arr[], int n, int x) { // Search x in array int i; for (i=0; i
Output: Modified array is 10 15 7 9 1