Table of contents  
Introduction  
How Insertion Sort Works  
Implementation in C++  
Example Usage  
Time Complexity  
Conclusion 
Sorting is a fundamental operation in computer science and is essential for organizing data efficiently. Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It is often used for small datasets or as a part of more complex sorting algorithms. In this article, we will explore how insertion sort works and implement it in C++.
Insertion sort works by dividing the input array into two sections: the sorted section and the unsorted section. Initially, the sorted section consists of only the first element, and the rest of the array is considered unsorted. The algorithm iterates through the unsorted section, takes each element, and inserts it into its correct position in the sorted section. This process continues until the entire array is sorted.
The key steps of the insertion sort algorithm are as follows:
Let's see how we can implement the insertion sort algorithm in C++. We'll start by writing a function called 'insertionSort' that takes an array of integers and sorts it using insertion sort.
#include <iostream>
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i  1;
// Shift elements in the sorted section
// that are larger than the key to the right
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j;
}
// Insert the key into its correct position
arr[j + 1] = key;
}
}
In the code above, we start iterating from the second element ('i = 1') and compare it with the elements in the sorted section (j = i  1'). We shift the elements in the sorted section that are larger than the key to the right until we find the correct position for the key. Finally, we insert the key into its correct position.
Now let's see how we can use the 'insertionSort' function to sort an array of integers.
int main() {
int arr[] = {4, 2, 9, 1, 6};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
insertionSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Original array: 4 2 9 1 6
Sorted array: 1 2 4 6 9
In the example above, we initialize an array 'arr' with some random integers. We calculate the size of the array and then call the 'insertionSort' function to sort the array. Finally, we print the original and sorted arrays to verify the correctness of the algorithm.
The time complexity of insertion sort is O(n^2) in the worst and average cases. This is because, in the worst case, each element needs to be compared with all the elements in the sorted section, resulting in nested loops. However, in the best case scenario where the input array is already sorted, the time complexity reduces to O(n) since no element needs to be shifted.
1. Write a program to sort an array of strings using insertion sort.
#include <iostream>
#include <string>
void insertionSort(std::string arr[], int size) {
for (int i = 1; i < size; i++) {
std::string key = arr[i];
int j = i  1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j;
}
arr[j + 1] = key;
}
}
int main() {
std::string arr[] = {"apple", "banana", "orange", "grape", "cherry"};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
insertionSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Original array: apple banana orange grape cherry
Sorted array: apple banana cherry grape orange
2. Implement a modified version of insertion sort that sorts an array in descending order.
#include <iostream>
void insertionSortDescending(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i  1;
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {4, 2, 9, 1, 6};
int size = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
insertionSortDescending(arr, size);
std::cout << "Sorted array (descending): ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Original array: 4 2 9 1 6
Sorted array (descending): 9 6 4 2 1
In this modified version, we simply change the comparison condition in the while loop from arr[j] > key to 'arr[j] < key' to 'sort' the array in descending order.
Insertion sort is a simple yet effective sorting algorithm that is easy to understand and implement. It works well for small datasets or as a part of more complex sorting algorithms. By following the steps outlined in this article, you should now have a good understanding of how insertion sort works and how to implement it in C++. So go ahead and try it out in your own programs!
70 videos45 docs15 tests

70 videos45 docs15 tests


Explore Courses for Software Development exam
