Python Coding Test Course, Insertion Sort

Introduction

Algorithms are one of the most important topics in coding interviews. The ability to understand and implement algorithms is essential for programming and software development. In this course, we will study the Insertion Sort algorithm in depth and increase our understanding through relevant problems.

What is Insertion Sort?

Insertion Sort is a simple sorting algorithm that divides a given data set into a sorted list and an unsorted list, then takes data one by one from the unsorted list and inserts it into the correct position in the sorted list. This algorithm is intuitive and has the advantage of being easy to implement.

How Insertion Sort Works

Insertion Sort works through the following steps:

  1. Starting from the second element, each element is compared to the current element (C).
  2. If the current element (C) is smaller than the previous element (A) of the sorted list, the current element (C) is inserted into the correct position in the sorted list.
  3. This process is repeated until the end of the array is reached, ultimately yielding a sorted array.

Time Complexity of Insertion Sort

The time complexity of Insertion Sort is O(n^2) in the worst case, O(n) in the best case, and O(n^2) on average. It is generally efficient when the data is nearly sorted. However, its performance can degrade when the data is distributed randomly.

Problem: Implement Insertion Sort

Let’s solve the following problem.


Problem: Sort the given list of integers using Insertion Sort.

Input: [5, 2, 9, 1, 5, 6]
Output: [1, 2, 5, 5, 6, 9]

Solution Process

To solve the problem above, we will implement the Insertion Sort algorithm. Below is the code that implements Insertion Sort using Python.


def insertion_sort(arr):
    # Start from the second element of the list
    for i in range(1, len(arr)):
        key = arr[i]  # Current element
        j = i - 1  # Previous index of the current element

        # Find the correct position in the sorted list
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]  # Move the element to the right
            j -= 1  # Decrease the index
        
        arr[j + 1] = key  # Insert the current element in the correct position
    return arr

# Example list
example_list = [5, 2, 9, 1, 5, 6]
sorted_list = insertion_sort(example_list)
print(sorted_list)

Explanation of the Code

The code above has the following structure:

  1. def insertion_sort(arr): - Defines the Insertion Sort function.
  2. for i in range(1, len(arr)): - Begins the iteration from the second element.
  3. key = arr[i] - Stores the current element.
  4. while j >= 0 and key < arr[j]: - Looks for an element in the sorted list that is larger than the current element.
  5. arr[j + 1] = arr[j] - Moves the element to the right to make space.
  6. arr[j + 1] = key - Inserts the current element in the correct position.
  7. Finally, it returns the sorted array.

Advantages and Disadvantages of Insertion Sort

Advantages

  • It is simple and intuitive to implement.
  • It is particularly efficient when the data is nearly sorted.
  • As an in-place sorting algorithm, it uses little additional space.

Disadvantages

  • Its time complexity of O(n^2) does not offer good performance in absolute terms.
  • It is inefficient when the data is distributed randomly.

Conclusion

In this course, we learned about the Insertion Sort algorithm. Insertion Sort is a simple yet useful sorting algorithm that can often appear in coding tests. Understanding the principles of the algorithm and practicing its rigorous implementation is important to solve given problems. In the next course, we will cover another sorting algorithm.

References