Insertion Sort Analysis - Python Implementation

Insertion sort always maintains a sorted sublist at the beginning of a list. New items are then again "inserted" back into the previous sorted sublist such that the sublist remain sorted and it becomes just one item larger.

Time Complexity:
Worst Case and Average Case: O(n²)
Best Case: O(n)

It works as the same way we arrange cards.

Look at the example of swapping items in insertion sort below:

Consider [3, 2, 1]

The loop starts with 3. Since it is the first item in the list there is nothing else to do.

[3, 2, 1]

The next item is 2. It compares 2 to 3 and since 2 is less than 3 it swaps them, first putting 3 in the second position and then placing 2 in the first position.

[2, 3, 1]

The last item is 1. Since 1 is less than 3 it moves 3 over.

[2, 3, 3]

Since 1 is less than 2 it swaps moves 2 over.

[2, 2, 3]

Then it inserts 1 at the beginning.

[1, 2, 3]

Let's see the python implementation of Insertion sort.

def insertion_sort(array):
    """
    Function to do insertion sort.
    
    Args:
      array (List[int]): input array.
    
    Returns:
      array (List[int]): The return value. A sorted list. 
    """

    for idx in range(1, len(array)):

        key = array[idx]

        j = idx - 1
        while j >= 0 and array[j] > key:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key
    return array


if __name__ == "__main__":
    arr = [1, 12, 11, 13, 5, 6]
    print(insertion_sort(arr))

Comments

Difference between a Singly LinkedList and Doubly LinkedList

DFS Performance Measurement

Completeness DFS is not complete, to convince yourself consider that our search start expanding the left subtree of the root for so long path (maybe infinite) when different choice near the root could lead to a solution, now suppose that the left subtree of the root has no solution, and it is unbounded, then the search will continue going deep infinitely, in this case , we say that DFS is not complete. Optimality Consider the scenario that there is more than one goal node, and our search decided to first expand the left subtree of the root where there is a solution at a very deep level of this left subtree , in the same time the right subtree of the root has a solution near the root, here comes the non-optimality of DFS that it is not guaranteed that the first goal to find is the optimal one, so we conclude that DFS is not optimal. Time Complexity Consider a state space that is identical to that of BFS, with branching factor b, and we start the search fro...

A Brief Overview of GPT-3 by OpenAI

You have probably already seen some articles like "A robot wrote an entire article. Aren't you scared yet, human?" So, who is the robot here? It's GPT-3 model. It's a transformer based language model. The full form of GPT is Generative Pre-trained Transformers. This model is developed by OpenAI. There were GPT-2 and other models released by OpenAI previously. GPT-3 was released in May 2020. GPT-3 is more robust than its predecessors. Though architecturally it doesn't have that mush difference. GPT-3 can write articles, poems, and even working code for you*, given some context. There are some limitations which I am going explain later in this article. It's a language model means given a text, it probabilistically predicts what tokens from a known vocabulary will come next in that string. So, it's sort of a autocomplete that we see on a phone keyboard. We type a word, and then the keyboard suggests another word that can come next. What sets GPT...

Soumik's Tech Blog

Search This Blog