C++ Arrays
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.
Let us try converting this flowchart in to C++ code.
Binary Search
The figure below shows a flow chart of binary search to find 33 in the given array.
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.
Insertion
To insert an element into an array
- First get the element to be inserted, say a
- Then get the position at which this element is to be inserted, say positionX
- Then shift the array elements from this position to one position forward, and do this for all the other elements next to positionX.
- Insert the element a now at the position positionX, as this is now empty.
C++ code for this is
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
After the first pass we see that some elements are still unsorted so the second pass.
Even after the second pass we see that 2 and 8 are still unsorted so the third pass.
Now the array is sorted but the compiler runs one final check to confirm the array is sorted
No elements are swapped and the sorted array is displayed.
Let us write the code for bubble sort now
Insertion Sort
In this algorithm elements are inserted at their appropriate place. Consider the figure to understand the working of insertion sort better.
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.
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.