Insertion Sort Algorithm
Sorting algorithms are fundamental concepts in computer science, that are used to order a collection of elements. One such sorting algorithm is the Insertion Sort, which is simple, efficient, and easy to understand.
Insertion sort works by maintaining a sorted section of the collection and inserting unsorted elements into it, resulting in a completely sorted list. In this article, we will explore the Insertion Sort algorithm, understand how it works, and its practical applications.
We will also dive into an analogy to a real-life situation to make it easier to understand.
Insertion Sort Algorithm
Insertion Sort is a sorting algorithm that works by taking one element at a time from an unsorted list and inserts it into a sorted list, one element at a time until the entire list is sorted. It is like sorting a deck of cards and inserting each card in the sorted section.
The algorithm maintains a sorted section that starts with the first element of the list. We can think of the sorted section as the left-hand side of the list, with the unsorted section as the right-hand side of the list.
The algorithm picks the first element of the unsorted section and compares it to each element in the sorted section to determine its correct position in the sorted section.
Tracking the Index of the Unsorted Section and Starting Index for the Algorithm in Python
To implement the Insertion Sort algorithm in Python, we can use the index to track the unsorted section’s starting position and starting index. For example, if we have a list of integers, we can use the length of the list to determine the starting position of the unsorted section.
The following code shows how to implement the Insertion Sort algorithm 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
return arrThe above function takes an array as input and returns the sorted array using the Insertion Sort algorithm.
Comparison of New Element to Each Element in the Sorted Section to Find its Correct Position
The most crucial feature of the Insertion Sort algorithm is comparing the newly picked element with each element of the sorted section to find its correct position. The algorithm selects the first element of the unsorted section and compares it to each element in the sorted section.
If the newly picked element is smaller than the current element in the sorted section, the algorithm shifts the current element to the right until it finds the correct position. For example, let’s say the sorted section consists of the numbers [2, 4, 6], and the algorithm picks the number 3 from the unsorted section.
It will make a comparison between 3 and 2, which will result in a shift of 2 to the right, resulting in the list [3, 2, 4, 6]. The algorithm will then compare 3 with the next element, which is 4.
Since 3 is already in the correct position, the algorithm moves to the next element, which is 6. Again, the element 3 is in the correct position, so the algorithm moves to the next unsorted element.
Analogy of Insertion Sort to Sorting in Real Life
Sorting a collection of elements using the Insertion Sort algorithm can be compared to sorting something in real life. For instance, imagine that you have a pile of books that you want to sort alphabetically.
You would pick one book from the unsorted pile, compare it with each book in the sorted pile until you find its correct position, and then insert it into the sorted pile. This process would repeat until all the books have been sorted.
Conclusion
In conclusion, the Insertion Sort algorithm is a simple and easy-to-implement sorting algorithm that is efficient at sorting small lists. The algorithm works by maintaining a sorted section and inserting unsorted elements into it until the entire list is sorted.
Importantly, the algorithm tracks the starting position of the unsorted section and the starting index in Python. We also saw how each element of the unsorted section is compared to the sorted section to find its correct position.
Furthermore, we compared the sorting of elements using the Insertion Sort algorithm to a real-life situation to make it easier to comprehend.
3) Insertion Sort in Python
Insertion Sort is a sorting algorithm that is widely used due to its simplicity and effectiveness. It is also straightforward to implement it in Python.
Two vital points to consider concerning Python are in-place sorting and the possibility of altering the algorithm to return a sorted list.
In-place sorting with Python
One of the main features of Insertion Sort is that it is an in-place sorting algorithm. In other words, it does not require extra storage space to sort a list.
It sorts the list within its own memory space. In Python, list objects are mutable, meaning that we can change them in-place.
Therefore, there is an opportunity to sort them in-place using the Insertion Sort algorithm. The following code shows how to sort a list using the Insertion Sort algorithm:
def insertionSort(array):
for i in range(1, len(array)):
key = array[i]
j = i-1
while j >=0 and key < array[j] :
array[j+1] = array[j]
j -= 1
array[j+1] = keyWe can call the above function and pass an unsorted array as its parameter.
This algorithm will sort the given list and return the sorted list without using any additional memory space.
Possibility of altering algorithm to return a sorted list
In some cases, we may want to return the sorted list as well as the original unsorted list. To do so, we can modify the above algorithm slightly and create a new array to store the sorted list.
This approach means that we are no longer sorting in-place, and we will need the extra space to store the new array. The following code shows how to change the above algorithm to obtain both the sorted and unsorted lists.
def insertionSort(array):
for i in range(1, len(array)):
key = array[i]
j = i-1
while j >=0 and key < array[j] :
array[j+1] = array[j]
j -= 1
array[j+1] = key
sorted_array = array
return sorted_arrayIn the altered algorithm, we create a new variable called sorted_array and assign the sorted version of the original list to it. Finally, our function returns the sorted_array variable.
4) Understanding the Insertion Sort algorithm
To understand the Insertion Sort algorithm and how it works, let’s run the algorithm on an example list. Consider the following unsorted list:
[5, 2, 4, 6, 1, 3]
- The algorithm selects the first element of the unsorted section, which is the number 2.
- It then compares the number 2 with each element in the sorted section, which, at present, is only the first element, which is 5.
- Since 2 is less than 5, the algorithm shifts 5 to the right and inserts 2 in its correct position within the sorted section. The sorted section now consists of the numbers [2, 5], and the unsorted section is [4, 6, 1, 3].
- The algorithm selects the next element from the unsorted section, which is 4.
- It compares it with each element in the sorted section [2, 5]. Since 4 is greater than 2 and less than 5, it finds its correct position within the sorted section, the sorted section now consists of the numbers [2, 4, 5], and the unsorted section is [6, 1, 3].
- The algorithm continues this process until the entire list is sorted.
The inner loop of the algorithm is responsible for finding the correct position of the selected item in the sorted section and moving it to that position. The inner loop compares the selected item with each element in the sorted section and shifts the elements accordingly if necessary.
The outer loop repeats the same process for each item in the unsorted section. The outer loop takes each item, selects it, and compares it with the sorted elements to find the correct position.
Once it finds the position, it places the selected item within the sorted section.
Conclusion
The Insertion Sort algorithm is a simple yet effective sorting algorithm that can efficiently sort small lists. Understanding how to implement the algorithm in Python and its usage is crucial.
The algorithm is an in-place sorting algorithm in Python and therefore, no additional memory space is required. By modifying the algorithm slightly, we can also obtain the original unsorted list as well as the sorted list.
By understanding how the algorithm works, we can implement it efficiently and make use of its strengths.
5) The Output
After running the Insertion Sort algorithm on a list, the output is always sorted in ascending order. The final list provides the user with a clear picture of all the elements arranged in order.
The output is an essential aspect of the Insertion Sort algorithm because it is the end result for which we seek. It allows the user to understand the effectiveness of the algorithm and to get the intended use of sorting the given list.
For instance, if we run the Insertion Sort algorithm on the list [5, 3, 8, 6, 7, 1], the sorted list resulting from running the algorithm is [1, 3, 5, 6, 7, 8]. It is important to understand that the algorithm modifies the original list, meaning the original numbers are lost in the process and replaced with the sorted reflected order.
6)
Conclusion
The Insertion Sort algorithm is one of the most intuitive sorting algorithms in computer science. It is the easiest to understand and is therefore often used as a teaching tool for budding programmers.
High-level languages like Python make it possible to execute the Insertion Sort algorithm with fewer lines of code than low-level languages like C or assembly. In comparison to Bubble Sort, the Insertion Sort algorithm takes a similar approach to sorting, using two nested loops, but the Insertion Sort algorithm is typically more efficient.
Bubble Sort works by swapping elements as it traverses the list, which can be slow. Insertion Sort, on the other hand, locates the correct position of an element and then inserts it where it belongs.
Therefore, Insertion Sort takes fewer iterations to sort a list than Bubble Sort, making it a more efficient choice. The complexity of Insertion Sort is O(n^2), meaning that it requires a basic operation to run for every element in the list.
This means that for large lists, the algorithm may become computationally slow and less efficient than other sorting algorithms with lower complexity. The average time complexity of Insertion Sort is O(n^2), making it suitable for small data sets but not recommended for significant reasons.
In conclusion, the Insertion Sort algorithm is an effective and efficient sorting algorithm that is widely used in computer science. It is easy to implement in Python, making it a valuable addition to any programmer’s toolbox.
We have explored how the algorithm works, observed its implementation in Python, explained how to display the sorted list resulting from the algorithm, and compared it to Bubble Sort. With this overview and detailed understanding of the algorithm, we can appreciate its nuances and apply it in a variety of contexts.
The Insertion Sort algorithm might not be suitable for the largest data sets, but it is useful for many small to medium-sized projects. In summary, the Insertion Sort algorithm is a widely used and effective sorting algorithm in computer science.
With an overview of the algorithm and its implementation in Python, we have established that it is a valuable addition to any programmer’s toolkit. We explored how the algorithm works, its efficiency and complexity, the output of the sorted list, and compared it to Bubble Sort.
Although the algorithm is more efficient than Bubble Sort, it might not be suitable for large datasets. Overall, the simplicity of the Insertion Sort algorithm makes it a great teaching tool, and its effectiveness in sorting small lists makes it a practical solution in many contexts.
The takeaway is that this fundamental algorithm is a crucial skill to have for anyone in the computer science field and is worth learning and understanding for its practical and theoretical applications.