Introduction
Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It builds the final sorted array one item at a time, with the assumption that the initial part of the array is already sorted. It is particularly useful for small datasets or nearly sorted data.
Key Concepts
- In-place Sorting: Insertion Sort sorts the array without requiring additional storage.
- Stable Sorting: It maintains the relative order of equal elements.
- Adaptive: Efficient for data sets that are already substantially sorted.
Algorithm Steps
- Start with the second element (index 1) as the key.
- Compare the key with the elements before it.
- Shift elements that are greater than the key to one position ahead.
- Insert the key into its correct position.
- Repeat the process for all elements.
Pseudocode
for i from 1 to length(A) - 1
key = A[i]
j = i - 1
while j >= 0 and A[j] > key
A[j + 1] = A[j]
j = j - 1
A[j + 1] = keyExample
Consider the array: [5, 2, 9, 1, 5, 6]
- Initial array:
[5, 2, 9, 1, 5, 6] - Key = 2, Compare with 5, Shift 5:
[5, 5, 9, 1, 5, 6], Insert 2:[2, 5, 9, 1, 5, 6] - Key = 9, No shift needed:
[2, 5, 9, 1, 5, 6] - Key = 1, Compare and shift:
[2, 5, 9, 9, 5, 6],[2, 5, 5, 9, 5, 6],[2, 2, 5, 9, 5, 6], Insert 1:[1, 2, 5, 9, 5, 6] - Key = 5, Compare and shift:
[1, 2, 5, 9, 9, 6], Insert 5:[1, 2, 5, 5, 9, 6] - Key = 6, Compare and shift:
[1, 2, 5, 5, 9, 9], Insert 6:[1, 2, 5, 5, 6, 9]
Final sorted array: [1, 2, 5, 5, 6, 9]
Python Implementation
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Example usage
arr = [5, 2, 9, 1, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)Explanation of Code
- Line 1: Define the
insertion_sortfunction that takes an arrayarras input. - Line 2: Loop through the array starting from the second element.
- Line 3: Set the current element as the key.
- Line 4: Initialize
jto the index before the key. - Line 5-7: Shift elements greater than the key to the right.
- Line 8: Insert the key into its correct position.
Practical Exercises
Exercise 1
Sort the following array using Insertion Sort: [8, 4, 3, 7, 6, 5, 2, 1]
Solution
Expected Output: [1, 2, 3, 4, 5, 6, 7, 8]
Exercise 2
Write a function to sort a list of strings using Insertion Sort.
Solution
def insertion_sort_strings(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Example usage
arr = ["banana", "apple", "cherry", "date"]
insertion_sort_strings(arr)
print("Sorted array:", arr)Expected Output: ['apple', 'banana', 'cherry', 'date']
Common Mistakes and Tips
- Off-by-One Errors: Ensure the loop indices are correctly set to avoid out-of-bound errors.
- Unnecessary Comparisons: Avoid comparing elements that are already in the correct order.
- Handling Edge Cases: Consider edge cases such as empty arrays or arrays with a single element.
Conclusion
Insertion Sort is a fundamental algorithm that is easy to understand and implement. While it may not be the most efficient for large datasets, it is a valuable tool for small or nearly sorted arrays. Understanding Insertion Sort provides a solid foundation for learning more complex sorting algorithms.