Insertion Sort in C++

Insertion sort is an algorithm used to sort a collection of items into a certain order. It is a simple and effective sorting algorithm that works by taking one element of the collection, comparing it to the elements already sorted and then inserting it into the right place. Insertion sort is an in-place algorithm, meaning it doesn’t require any extra space. Insertion sort is commonly used in language such as C++ and is a useful algorithm for sorting data. In this article, we will discuss the insertion sort algorithm in C++, the time and space complexities and the implementation of the algorithm using C++ code. 

What is Insertion Sort? 

Insertion sort is an algorithm used to sort a collection of items into a certain order. It works by taking one element of the collection, comparing it to the elements already sorted and then inserting it into the right place. Insertion sort is a comparison-based algorithm, meaning it uses comparisons to sort the elements of the collection. The algorithm works by taking one element of the collection and comparing it to the elements already sorted. If the element is less than the one already sorted, it is inserted into the right place. This process is repeated until all the elements are sorted. 

Insertion Sort Algorithm 

The insertion sort algorithm is a simple and effective sorting algorithm. It works by taking one element of the collection, comparing it to the elements already sorted and then inserting it into the right place. The algorithm works by taking one element of the collection and comparing it to the elements already sorted. If the element is less than the one already sorted, it is inserted into the right place. This process is repeated until all the elements are sorted. The algorithm can be illustrated with the following example: 

Let’s say we have an unsorted array of integers: 

5, 3, 2, 6, 4 

The algorithm will take the first element in the array (5) and compare it to the elements already sorted (none in this case). Since there are no elements already sorted, 5 is inserted into the right place. The array now looks like this: 

5, 3, 2, 6, 4 

The algorithm then takes the next element (3) and compares it to the elements already sorted (5). Since 3 is less than 5, it is inserted into the right place. The array now looks like this: 

3, 5, 2, 6, 4 

The algorithm then takes the next element (2) and compares it to the elements already sorted (3 and 5). Since 2 is less than 3 and 5, it is inserted into the right place. The array now looks like this: 

2, 3, 5, 6, 4 

The algorithm then takes the next element (6) and compares it to the elements already sorted (2, 3 and 5). Since 6 is greater than 2, 3 and 5, it is inserted into the right place. The array now looks like this: 

2, 3, 5, 6, 4 

Finally, the algorithm takes the last element (4) and compares it to the elements already sorted (2, 3, 5 and 6). Since 4 is less than 5 and 6, it is inserted into the right place. The array now looks like this: 

2, 3, 4, 5, 6 

And the array is sorted! 

Implementation of Insertion Sort in C++ 

Now that we have an understanding of the insertion sort algorithm, let’s look at how it can be implemented using C++ code. The following code implements the insertion sort algorithm in C++. The code takes an array of integers as input and sorts them in ascending order using the insertion sort algorithm: 

// insertion sort algorithm
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; 
   } 
} 

Time Complexity (Best, Average, and Worst) 

The time complexity of the insertion sort algorithm is a function of the number of elements in the collection. The best case time complexity is O(n), meaning that the algorithm will take the same amount of time to sort regardless of the number of elements in the collection. The average case time complexity is O(n^2), meaning that the algorithm will take longer to sort as the number of elements in the collection increases. The worst case time complexity is also O(n^2), meaning that the algorithm will take longer to sort as the number of elements in the collection increases. 

Space Complexity (Worst) 

The space complexity of the insertion sort algorithm is O(1), meaning that the algorithm does not require any additional memory. The algorithm is an in-place algorithm, meaning that it does not require any extra space. 

Conclusion 

In this article, we have discussed the insertion sort algorithm in C++. We have discussed how the algorithm works, the time and space complexities and the implementation of the algorithm using C++ code. Insertion sort is a simple and effective sorting algorithm that works by taking one element of the collection, comparing it to the elements already sorted and then inserting it into the right place. It is an in-place algorithm, meaning it does not require any extra space. The time complexity of the insertion sort algorithm is a function of the number of elements in the collection and the space complexity is O(1).

Exercises 

// Insertion Sort Algorithm
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; 
   } 
} 

// Insertion Sort Algorithm
void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = n - 1; i >= 0; i--) 
   { 
       key = arr[i]; 
       j = i + 1; 
  
       /* Move elements of arr[i+1..n-1], that are 
          smaller than key, to one position behind 
          of their current position */
       while (j < n && arr[j] > key) 
       { 
           arr[j-1] = arr[j]; 
           j = j + 1; 
       } 
       arr[j-1] = key; 
   } 
} 

// Insertion Sort Algorithm 
void insertionSort(string arr[], int n) 
{ 
   int i, j; 
   string key; 
   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; 
   } 
} 

// Insertion Sort Algorithm 
void insertionSort(string arr[], int n) 
{ 
   int i, j; 
   string key; 
   for (i = n - 1; i >= 0; i--) 
   { 
       key = arr[i]; 
       j = i + 1; 
  
       /* Move elements of arr[i+1..n-1], that are 
          smaller than key, to one position behind 
          of their current position */
       while (j < n && arr[j] > key) 
       { 
           arr[j-1] = arr[j]; 
           j = j + 1; 
       } 
       arr[j-1] = key; 
   } 
} 

// Insertion Sort Algorithm 
void insertionSort(Object arr[], int n, string key) 
{ 
   int i, j; 
   Object key; 
   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 > key.key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
}