Insertion Sort in Python
Insertion Sort in Python
Insertion Sort in Python is one of the simplest yet valuable sorting algorithms that every aspiring programmer and data enthusiast should understand. In this guide, we will explore the inner workings of Insertion Sort, provide Python code examples for its implementation, discuss its time and space complexity, and offer insights into when and why you might choose Insertion Sort for your sorting needs.
What is Insertion Sort in Python?
Insertion Sort is a simple, comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by iteratively taking an element from the unsorted portion of the array and inserting it into its correct position within the sorted portion of the array.
Working of Insertion Sort Program in Python
Let us try to sort the array using Insertion Sort in ascending order :
Step 1: We initially consider the first element in the array as already sorted. Subsequently, we isolate the second element, denoted as “key.”
A comparison is made between the key and the first element. If the first element is larger than the key, we insert the key ahead of the first element.
Step 2: Presently, the initial two elements have been arranged in ascending order.
When handling the third element, it’s compared to the elements to its left. It is positioned immediately behind the element that is smaller than itself. In the event that there is no smaller element, it’s positioned at the very start of the array.
Step 3: In a similar fashion, position each unsorted element in its rightful place.
Final Sorted Array :
Algorithm for Insertion Sort in Python
Algorithm describes the steps for performing Insertion Sort Program in Python:
We start with the second element (index 1) and compare it to the previous elements in the sorted portion of the list.
The key variable holds the current element we’re considering for insertion.
We move elements greater than key one position to the right, effectively making space for key in the sorted portion of the list.
Finally, we insert key into its correct position within the sorted portion.
This process continues for each element in the list until the entire list is sorted.
Implementation of Insertion Sort in Python
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:
if __name__ == "__main__":
my_list = [64, 34, 25, 12, 22, 11, 90]
print("Original list:", my_list)
insertion_sort(my_list)
print("Sorted list:", my_list)
Output :
Original list: [64, 34, 25, 12, 22, 11, 90] Sorted list: [11, 12, 22, 25, 34, 64, 90]
Explanation
- The Python code implements the Insertion Sort algorithm. It iterates through a list, comparing each element with the sorted portion of the list and inserting it into the correct position.
- This process repeats for all elements, resulting in a sorted list. The example shows the algorithm in action.
Time and Space Complexity for Insertion Sort in Python
The time and space complexity of Insertion Sort is as follows:
Time Complexity:
- Worst-case time complexity: O(n^2) – This occurs when the input list is in reverse order, and Insertion Sort has to perform the maximum number of comparisons and element movements.
- Average-case time complexity: O(n^2) – On average, Insertion Sort requires n^2 comparisons and element swaps.
- Best-case time complexity: O(n) – The best-case scenario happens when the input list is already sorted. In this case, Insertion Sort only requires n-1 comparisons and no swaps.
Space Complexity:
- Insertion Sort has a space complexity of O(1) because it sorts the elements within the same array or list without requiring additional memory allocation that scales with the input size. Regardless of the size of the input list, Insertion Sort uses a constant amount of extra memory for temporary variables.
To wrap it up:
Insertion Sort is a fundamental sorting algorithm in Python, known for its simplicity and stability. While it’s not the most efficient choice for large datasets, its adaptability to partially sorted data and ease of implementation make it a valuable tool for educational purposes and small-scale sorting tasks. Understanding Insertion Sort is essential for building a strong foundation in sorting algorithms.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
FAQs
An insertion sort program in Python has a time complexity of O(n²), making it suitable only for small or nearly sorted lists. In contrast, Python’s built-in sort uses the highly optimized Timsort algorithm, which performs better on large datasets.
Insertion Sort in Python builds the sorted array one element at a time by inserting each item into its correct position. This process mimics the way we sort playing cards in our hand, hence the name “insertion.”
You should test with empty lists, single elements, already sorted arrays, reverse-sorted lists, and lists with duplicates. These edge cases ensure the insertion sort program in Python works correctly across all input types.
Yes, insertion sort can be optimized by using binary search to find the correct position and slicing for faster shifts. It’s also commonly used in hybrid algorithms where small subarrays benefit from its simplicity and speed.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment