Insertion Sort

Insertion sort is one of the most widely-used sorting algorithms, and it is a staple of data structures and algorithms courses. Insertion sort is a simple, straightforward algorithm that is easy to understand and implement. It is also relatively efficient in terms of time and space complexity. In this article, we will explore the mechanics of insertion sort, its time complexity, and its space complexity. We will also learn how to implement insertion sort with Python code.

What is Insertion Sort?

Insertion sort is an algorithm that sorts a given list by building up a sorted list one element at a time. The algorithm begins by sorting the first two elements of the list. It then compares each subsequent element to the elements already in the sorted list, and inserts it in the correct place. This process is repeated until the entire list is sorted.

Insertion sort is a simple algorithm, but it can be surprisingly efficient. It is also a stable algorithm, meaning that elements with equal values maintain their relative order in the sorted list.

How Does Insertion Sort Work?

Insertion sort works by comparing each element to the elements already in the sorted list. To understand how insertion sort works, we can use the following example. Suppose we have the following list of numbers:

[5, 3, 7, 1, 4]

The algorithm begins by sorting the first two elements, [5, 3], resulting in the following sorted list:

[3, 5]

Next, the algorithm compares the third element, 7, to the elements already in the sorted list. Since 7 is greater than 5, it is inserted after 5:

[3, 5, 7]

The algorithm then compares the fourth element, 1, to the elements in the sorted list. Since 1 is less than 3, it is inserted before 3:

[1, 3, 5, 7]

Finally, the algorithm compares the fifth element, 4, to the elements in the sorted list. Since 4 is greater than 3 and less than 5, it is inserted between 3 and 5:

[1, 3, 4, 5, 7]

And the list is now sorted.

Time Complexity of Insertion Sort

The time complexity of insertion sort is dependent on the size of the list being sorted. The best-case time complexity is O(n), which occurs when the list is already sorted. The average-case time complexity is O(n^2), which occurs when the list is in random order. The worst-case time complexity is also O(n^2), which occurs when the list is in reverse order.

Space Complexity of Insertion

Sort Insertion sort has a space complexity of O(1), meaning that it requires only a small amount of extra space to operate. This makes it an ideal algorithm for sorting lists in-place, since it does not require additional memory to operate. Implementing

Insertion Sort with Python

Now that we understand the mechanics of insertion sort, let’s learn how to implement it with Python code. We will begin by defining a function to sort a given list:

def insertion_sort(list): 
 for i in range(1, len(list)): 
  key = list[i] 
  j = i - 1 
  while j >= 0 and list[j] > key: 
   list[j + 1] = list[j] 
   j -= 1 
  list[j + 1] = key

This function takes a list as an argument and sorts it using the insertion sort algorithm. The function begins by looping through the list, starting at the second element. The current element is stored as the key, while the previous element is stored as j.

The function then enters a while loop that checks if the previous element is greater than the key. If so, the element is shifted to the right and the key is inserted in its place. This process is repeated until the list is sorted.

Conclusion

In this article, we have explored the mechanics of insertion sort, its time and space complexity, and how to implement it with Python code. Insertion sort is a simple and efficient algorithm that is used for sorting lists of elements. With its O(n) best-case time complexity and O(1) space complexity, it is an ideal algorithm for sorting lists in-place.

Exercises

def insertion_sort(list): 
 for i in range(1, len(list)): 
  key = list[i] 
  j = i - 1 
  while j >= 0 and list[j] > key: 
   list[j + 1] = list[j] 
   j -= 1 
  list[j + 1] = key

def insertion_sort(list): 
 sorted_list = list.copy() 
 for i in range(1, len(sorted_list)): 
  key = sorted_list[i] 
  j = i - 1 
  while j >= 0 and sorted_list[j] > key: 
   sorted_list[j + 1] = sorted_list[j] 
   j -= 1 
  sorted_list[j + 1] = key
 return sorted_list

def insertion_sort(list): 
 for i in range(1, len(list)): 
  key = list[i] 
  j = i - 1 
  while j >= 0 and list[j] > key: 
   list[j + 1] = list[j] 
   j -= 1 
  list[j + 1] = key
 
 print(list)

def insertion_sort(list, element): 
 sorted_list = list.copy() 
 for i in range(1, len(sorted_list)): 
  key = sorted_list[i] 
  j = i - 1 
  while j >= 0 and sorted_list[j] > key: 
   sorted_list[j + 1] = sorted_list[j] 
   j -= 1 
  sorted_list[j + 1] = key
 
 if element in sorted_list: 
  return sorted_list.index(element)
 else: 
  return -1

def insertion_sort_time_complexity(list): 
 n = len(list) 
 if n == 0 or n == 1: 
  print("Best case time complexity: O(n)") 
 else: 
  print("Average case time complexity: O(n^2)") 
  print("Worst case time complexity: O(n^2)")