C++ Data Structures and Algorithms

Insertion sort

Insertion sort is a sorting algorithm that is similar to arranging a hand of poker cards. This sorting algorithm will also divide the list into a sorted and unsorted sublist in the sorting process. For clarity, we pick an item as a reference, then go through the sorted sublist and find the correct position based on performing a comparison. This process is repeated until all the items are sorted, which means that we have to iterate through all of the array's elements.

Let's use our previous array {43, 21, 26, 38, 17, 30} and then perform an insertion sort algorithm on it. First, we set array[0] as the sorted sublist, so we pick array[1] as the reference. Now, we compare the reference item, which is 21, with the sorted sublist. ...