Table of contents | |
Introduction | |
Understanding Insertion Sort | |
C++ Implementation of Insertion Sort | |
Sample Problems |
When it comes to sorting algorithms, Insertion Sort is one of the simplest and easiest to understand. It is a comparison-based sorting algorithm that builds the final sorted array one item at a time. Insertion Sort is particularly useful for small data sets or partially sorted arrays. In this article, we will explore the concept of Insertion Sort, provide a step-by-step explanation of how it works, and present multiple examples and code snippets in C++ to solidify your understanding.
Insertion Sort works by dividing the array into two parts: the sorted part and the unsorted part. Initially, the sorted part contains only the first element of the array, while the rest of the elements are in the unsorted part. The algorithm iterates through the unsorted part, selects an element, and places it in the correct position within the sorted part.
The steps of the Insertion Sort algorithm can be summarized as follows:
Example 1: Sorting an Array using Insertion Sort
Let's take a look at an example to illustrate the Insertion Sort algorithm:
Consider the following array of integers: [5, 2, 4, 6, 1, 3]
The final sorted array is [1, 2, 3, 4, 5, 6].
Now, let's dive into the C++ code that implements the Insertion Sort algorithm:
#include <iostream>
void insertionSort(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[] = {5, 2, 4, 6, 1, 3};
int size = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Explanation of the Code
Output of the Code
The output of the above code will be:
Sorted array: 1 2 3 4 5 6
Now that you have a good understanding of Insertion Sort, try solving the following problems:
Problem 1: Sort the following array in non-decreasing order using Insertion Sort: [9, 7, 5, 8, 3, 1]
The sorted array will be: [1, 3, 5, 7, 8, 9]
Problem 2: Implement Insertion Sort in reverse order (non-increasing) in C++.
Simply modify the comparison in the while loop to 'arr[j] < key' instead of 'arr[j] > key'.
Problem 3: What is the time complexity of Insertion Sort?
The time complexity of Insertion Sort is O(n^2) in the worst and average cases. However, it has an O(n) best case time complexity when the array is already sorted.
By solving these problems and experimenting with different scenarios, you will reinforce your understanding of Insertion Sort and improve your problem-solving skills.
Insertion Sort is a straightforward sorting algorithm that is easy to understand and implement. It is particularly useful for small or partially sorted arrays. In this article, we explored the concept of Insertion Sort, provided step-by-step explanations, and demonstrated its implementation in C++. By practicing with the provided examples and solving the sample problems, you can gain hands-on experience with Insertion Sort and strengthen your grasp of this fundamental sorting algorithm.
153 videos|115 docs|24 tests
|
|
Explore Courses for Software Development exam
|