Insertion Sort is a simple and intuitive sorting algorithm that is particularly useful for small datasets or nearly sorted arrays. This algorithm builds the final sorted array one item at a time, with each iteration placing an element in its correct position. This article will guide you through the implementation of Insertion Sort in C++, providing detailed explanations and examples to illustrate its application.
Prerequisites
Before diving into the implementation, ensure you have a basic understanding of the following concepts:
- Arrays: A collection of elements stored at contiguous memory locations.
- C++ Syntax: Basic knowledge of C++ programming, including loops, conditional statements, and functions.
1. Introduction to Insertion Sort
1.1 Definition
Insertion Sort is an efficient algorithm for sorting a small number of elements. It works similarly to how you might sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
1.2 Algorithm Steps
- Start: Assume the first element is already sorted.
- Iterate: Pick the next element and compare it with the elements in the sorted part.
- Shift: Move the sorted elements to the right until the correct position for the picked element is found.
- Insert: Insert the picked element at its correct position.
- Repeat: Repeat the process for all elements in the array.
2. Implementation of Insertion Sort in C++
2.1 Example 1: Basic Insertion Sort
Let’s start with a basic implementation of Insertion Sort in C++.
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int 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;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Sorted array: 5 6 11 12 13
2.2 Example 2: Insertion Sort with Larger Array
Here is another example with a larger array to show how Insertion Sort handles more data.
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int 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;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {29, 10, 14, 37, 13, 44, 19, 28, 22, 5, 6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Sorted array: 5 6 8 10 13 14 19 22 28 29 37 44
2.3 Example 3: Insertion Sort with Strings
Insertion Sort can also be applied to an array of strings. This example demonstrates sorting an array of strings in lexicographical order.
#include <iostream>
#include <string>
using namespace std;
void insertionSort(string arr[], int n) {
for (int i = 1; i < n; i++) {
string key = arr[i];
int 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;
}
}
void printArray(string arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
string arr[] = {"apple", "orange", "banana", "grape", "cherry"};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Sorted array: apple banana cherry grape orange
Conclusion
Insertion Sort is a straightforward and effective sorting algorithm for small or nearly sorted datasets. With a time complexity of O(n^2) in the worst case, it is not the most efficient for large datasets but shines in simplicity and ease of implementation.