Sorting Algorithms

Insertion Sort Algorithm

Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it has advantages in simplicity and in situations where the list is nearly sorted or when the list is small.

How Insertion Sort Works

  • The first element is considered as a sorted mini list.
  • Pick the next element in the list
  • Compare the picked element with the sorted elements, moving from right to left.
  • Shift all the sorted elements greater than the picked element to the right.
  • Insert the picked element into its correct position.
  • Repeat until all elements are sorted.

Pseudocode

Here is the pseudocode for an insertion sort algorithm:

BEGIN
    FUNCTION insertion_sort(list)
        FOR i = 1 TO length(list) - 1 DO
            SET key = list[i]
            SET j = i - 1
            WHILE j >= 0 AND list[j] > key DO
                SET list[j + 1] = list[j]
                SET j = j - 1
            ENDWHILE
            SET list[j + 1] = key
        ENDFOR
    ENDFUNCTION
END

Example in Python

Below is an example implementation of insertion sort in Python:

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

# Example usage
numbers = [12, 11, 13, 5, 6]
insertion_sort(numbers)
print("Sorted list is:", numbers)

Key Points

Use Cases: Suitable for small datasets or nearly sorted datasets.

Advantages

  • Simple to implement and understand.
  • Efficient for small or nearly sorted datasets.
  • In-place sorting, requiring no additional memory.

Disadvantages

  • Inefficient for large datasets.
  • Higher time complexity compared to more advanced algorithms like quicksort or mergesort.
  • Time Complexity: O(n^2) in the average and worst case, where n is the number of elements in the list.
  • Space Complexity: O(1), as it uses a constant amount of extra space.
Previous
Merge sort