C++

Insertion Sort in C++

Insertion sort is a basic organizing algorithm or approach that operates in the same manner that you might arrange decks of cards in your palms. The assortment is separated into two parts: one that is ordered and the other that is not. Items from the unordered segment are designated and located in the organized fragment in the correct order. The Insertion sort will compare the two consecutive values with each other and this methodology is more effective than the Bubble and Selection sort, but not as fast as Quick sort or Merge sort.

Let’s start with the shell application launch in Ubuntu 20.04 system with Ctrl+Alt+T. After launching it, create a C++ file in your Home folder via the “touch” instruction shown in the image. Name the C++ file with the “cc” extension. After that, open your file in any built-in editor of Ubuntu 20.04 system (i.e. Gnu Nano, text, or vim).

Example 1:

Let’s get started with the very first example to use the insertion sort to sort a random unordered array in ascending order of numbers. We started our code with the inclusion of the “bits/stdc++.h” standard library. Then, we added the standard “namespace” of C++ with the short word “using” and “std”. The “Sort()” function uses the array “A” and its size “n” to sort the unordered random array into sorted one via the insertion sort technique.

We declared an integer variable “key” and the “for” loop is in progress. Until the loop is interacting up to the “n” size of an array, the value at each index “I” of array “A” is saved to the variable “key”.

Initialize another variable “j” with the previous value of index “I” i.e. “j = I -1”. Here comes the while loop. While the previous index “j” is greater than or equal to 0 and the value at index “j” is greater than the value at variable “key” i.e. the value at index “I”, it will continue to add the value at index “j” to index “j+1” which is actually ‘I”. Along with that, the index “j” will decrement by 1 i.e. the previous of “j” will become “j”.

After the while loop ends, the value at “j+1” is assigned with value “key”. i.e. at “I”. To make it more clear, let say if i=1 then j=0. So, if the value at “j” is greater than “key”, we will swap the value at “j” with the next consecutive value.

This function is executed by the main() function by passing the array and its specific size in the parameters. The “for” loop is used to iterate the array values from index 0 to the last index “n-1” of an array. On each iteration, each value is displayed on the shell using the specific index of an array for a particular iteration via the cout statement. The last cout statement is used to put the line end after the display of whole array “A” on the shell.

The execution of this code starts from the main() method. We initialized an array “A” of integer type with some random number values. This array is not sorted yet. We are getting the size of an array using the variable “n” and applying the sizeof() function on array “A”.

The cout object is used to let the user know that the program will display the original unsorted array on your screen. The “Show” function is called by passing the array “A” and size “n” to display the randomly ordered array. The next cout statement is used to let you know that the program is going to display the sorted array on the shell through the use of insertion sort.

The “sort()” is called by passing a random-ordered array “A” and its size. The sort() function sorts the array and the show() function displays the updated sorted array “A” on the shell screen of our Linux terminal. The overall code is now completed here.

After the compilation of our code, we have got no errors. We executed our code via the “./a.out” instruction shown below. The unsorted array has been displayed and then the sorted array is in an ascending order via the insertion sort.

Example 2:

Let’s take a look at another example of insertion sort. Within this example, we will not use any user-defined sorting functions to perform insertion sort. We will only use the main() function in the code to perform it. So, we open the same code file and update the code. Add the C++ standard input and output stream library with the “#include” keyword. The “standard namespace” is declared using the “using” keyword.

We start the main() function of integer type and initialize an integer array “A” of size 10 with the 10 numerical values. These elements of an array “A” are randomly placed regardless of the order. The cout statement is used to state that we are going to display the list before sorting it. After this, we use the “for” loop to iterate the values of the unsorted original array “A” up to its last element. On each iteration of the “for” loop, each same index value from the array “A” is displayed on the shell via the “cout” statement. After this “for” loop, we utilize another “for” loop to perform “insertion” sorting.

This “for” loop is initialized from “k=0” to “k=10”. While the loop is iterating itself from 0 to 10th index of array “A”, we continue to assign the value at index “k” of array “A” to the new integer variable “temp”. Also, we find out the predecessor “j” of the value “k” using the “k-1”. The “while” loop is here to check whether the predecessor index “j” is greater than 0 and the value at the “temp” variable is less than or equal to the value of predecessor “j” of array “A”.

If this condition satisfies, the value of the predecessor is assigned to the next of “j” predecessor i.e. “j+1”. Along with this, we continue to decrement the predecessor index i.e. moving in the backward direction. After the while loop ends, we assign the value of “temp” to the next of “j” predecessor. After the “for” loop ends, we display the sorted array “A”. For this, we utilize the “cout” statement in the “for” loop. The code is completed here and are ready for use.

We compiled the code file “insertion.cc” successfully and executed the file with the “./a.out” instruction. The unsorted random array is displayed first. After that, the sorted array through the insertion sort is displayed at the end as per the output below.

Conclusion

This article is all about the use of insertion sort to sort a random array in a C++ program. We discussed the conventional way of sorting the array with the insertion sort within the first examples i.e. use of sort, display, and the main() driver function. After this, we used the new method to perform the insertion sort in a single driver main() function.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.