Insertion Sort in Python
Sorting – 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 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 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
Question 1.
Can Insertion Sort be optimized?
Yes, there are variations of Insertion Sort that include optimizations, such as binary insertion sort, which reduces the number of comparisons in the inner loop.
Question 2.
Is Insertion Sort a stable sorting algorithm in Python?
Yes, Insertion Sort is stable, ensuring that the relative order of equal elements remains unchanged after sorting.
Question 3.
Is Insertion Sort memory-efficient in Python?
Yes, Insertion Sort is an in-place sorting algorithm, meaning it doesn’t require additional memory proportional to the input size. It sorts the elements within the same array or list.
Question 4.
When should I use Insertion Sort in Python?
Insertion Sort is best suited for small datasets or partially sorted data. It’s also useful when you want to sort data as it’s received (online sorting) because it efficiently inserts elements into a sorted list.
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