Skip to main content

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))














































Labels:

Comments

Post a Comment

Popular posts from this blog

Regularization in Deep Learning / Machine Learning - Prevent Overfitting

image source: mlexplained Overfittng happens in every machine learning (ML) problem.  Learning how to deal with overfitting is essential to mastering machine learning.  The fundamental issue in machine learning is the tension between optimization  and generalization. Optimization refers to the process of adjusting a model to get the  best performance possible on the training data (the learning in machine learning ),  whereas generalization refers to how well the trained model performs on data it has  never seen before . The goal of the game is to get good generalization, of course, but you don’t control generalization; you can only adjust the model based on its training  data.  The processing of fighting overfitting is a way  called regularization . [1].  How do you know whether a model is overfitting? The best initial method is to measure error on a training and test set. If you see a low error on the training set and...
1 comment
Read more

Lambda, Map, and Filter in Python

Lambda: Lambda functions are known as the anonymous functions in Python. This kind of functions are declared without any name. Can accept any number of argument.  Restricted to only a single expression.  Used only one-time. Lambda function is used when you need a function for a short period of time.  Basic syntax:  lambda arguments : expression Example: Map: Map is a built-in function that takes a function object and iterable list (list/dictionary) as its parameter. Basic syntax: map (function_object, iterable_1, iterable_2, ... ) Few examples of Map in python: Filter: It works similar way like map. The difference is it makes a new list from the element in the list that satisfy some condition . In case of of parameters, it takes a function and one iterable. Basic syntax: filter (function, iterable) Normally used with lambda functions. Example is given below:
2 comments
Read more

Difference between a Singly LinkedList and Doubly LinkedList

3 comments
Read more