Insertion Sort
Insertion Sort is a simple comparison-based sorting algorithm that works by building a sorted sequence one element at a time. It is suitable for small datasets or when the input is partially sorted. However, its time complexity increases rapidly as the size of the dataset grows, making it inefficient for large datasets.
Algorithm[edit]
The Insertion Sort algorithm works as follows:
Consider the first element of the list as sorted. Insert the second element in its correct position in the sorted part of the list. Move to the next unsorted element and insert it in its correct position in the sorted part of the list. Repeat step 3 until the entire list is sorted.
Pseudocode[edit]
Here is a simple pseudocode for Insertion Sort:
function insertionSort(arr)
for i = 1 to length(arr) - 1
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key
arr[j + 1] = arr[j]
j = j - 1
end while
arr[j + 1] = key
end for
end function
Time Complexity[edit]
The worst-case and average time complexity of Insertion Sort is O(n^2), where n is the number of elements in the list. The best-case time complexity is O(n) when the input list is already sorted. In practice, Insertion Sort performs well for small datasets or when the input is partially sorted.
Space Complexity[edit]
The space complexity of Insertion Sort is O(1) because it is an in-place sorting algorithm, meaning it does not require additional memory for temporary storage.
C++ Example[edit]
Here is an example implementation of Insertion Sort in C++:
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
size_t n = arr.size();
for (size_t i = 1; i < n; ++i) {
int key = arr[i];
size_t j = i - 1;
while (j != SIZE_MAX && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6};
insertionSort(arr);
std::cout << "Sorted array is: ";
for (int i : arr) {
std::cout << i << " ";
}
return 0;
}