Insertion Sort Algorithm

The given solution implements the Insertion Sort algorithm, which is a simple comparison-based sorting algorithm.

What is the Problem Being Solved?

The problem being solved is sorting an array of elements in ascending order.

The Solution

# O(n^2) time | O(1) space
def insertion_sort(array):
    """
    Sorts an array using the insertion sort algorithm.
    
    Parameters:
    array (list): The unsorted array to be sorted.
    
    Returns:
    list: The sorted array.
    """
    # Iterate over the array starting from the second element
    for i in range(1, len(array)):
        j = i  # Store the current index
        # Move elements of array[0..i-1], that are greater than
        # the key, to one position ahead of their current position
        while j > 0 and array[j] < array[j-1]:
            # Swap elements if they are in the wrong order
            array[j], array[j-1] = array[j-1], array[j]
            j -= 1  # Move to the previous index
    return array  # Return the sorted array

# Test the insertion_sort function
print(insertion_sort([8, 5, 2, 9, 5, 6, 3]))

Solution Overview

The function insertion_sort takes an array as input.

It iterates over the array starting from the second element (index 1), assuming that the first element (index 0) is already sorted.

Main Loop (i)

The main loop iterates over each element of the array from index 1 to the last element. For each element at index i, it temporarily stores the index in variable j.

Shift and Insert

Within the main loop, a while loop is used to compare the current element with the elements to its left (i.e., elements already sorted). If the current element is less than its adjacent element to the left (array[j] < array[j-1]), it swaps the elements until the current element is in its correct sorted position.

This process effectively "shifts" the current element to its correct position in the sorted sequence.

After the inner while loop completes, j is decremented by 1 to move to the next index to the left, continuing the comparison and shifting process until the current element is in its correct position.

After the main loop completes all its iterations, the array is sorted, and the function returns the sorted array.

Time Complexity

Here's a detailed analysis of the worst-case, best-case, and average-case time complexity.

Worst-Case Time Complexity

The worst-case time complexity of Insertion Sort is O(n^2), where n is the number of elements in the array. This occurs when the array is in reverse sorted order, and each element needs to be compared and shifted to the beginning of the array.

Best-Case Time Complexity

The best-case time complexity is O(n), which occurs when the array is already sorted, and no element needs to be shifted.

Average-Case Time Complexity

The average-case time complexity is also O(n^2), making Insertion Sort inefficient for large datasets.

Space Complexity

The space complexity of Insertion Sort is O(1), as it operates in-place and does not require any additional space proportional to the size of the input array.

Example:

For example, given the input array [8, 5, 2, 9, 5, 6, 3], the Insertion Sort algorithm would rearrange the elements in ascending order:

Pass 1: [5, 8, 2, 9, 5, 6, 3]
Pass 2: [2, 5, 8, 9, 5, 6, 3]
Pass 3: [2, 5, 8, 9, 5, 6, 3]
Pass 4: [2, 5, 5, 8, 9, 6, 3]
Pass 5: [2, 5, 5, 6, 8, 9, 3]
Pass 6: [2, 3, 5, 5, 6, 8, 9]

Unit Tests

Here are some unit tests using the unittest framework to test the insertion_sort. These tests cover various scenarios including:

class TestInsertionSort(unittest.TestCase):
    def test_insertion_sort(self):
        # Test case with random elements
        input_array = [8, 5, 2, 9, 5, 6, 3]
        expected_output = [2, 3, 5, 5, 6, 8, 9]
        self.assertEqual(insertion_sort(input_array), expected_output)

        # Test case with already sorted elements
        input_array = [1, 2, 3, 4, 5]
        expected_output = [1, 2, 3, 4, 5]
        self.assertEqual(insertion_sort(input_array), expected_output)

        # Test case with reverse sorted elements
        input_array = [5, 4, 3, 2, 1]
        expected_output = [1, 2, 3, 4, 5]
        self.assertEqual(insertion_sort(input_array), expected_output)

        # Test case with repeated elements
        input_array = [3, 2, 3, 1, 2]
        expected_output = [1, 2, 2, 3, 3]
        self.assertEqual(insertion_sort(input_array), expected_output)

        # Test case with empty array
        input_array = []
        expected_output = []
        self.assertEqual(insertion_sort(input_array), expected_output)

        # Test case with single element
        input_array = [5]
        expected_output = [5]
        self.assertEqual(insertion_sort(input_array), expected_output)

if __name__ == '__main__':
    unittest.main()