DEV Community

Jenny Yang
Jenny Yang

Posted on

Learning Algorithms - Insertion Sort

Sorting

Sorting is one of the concepts of the basic algorithm as important as searching algorithms. There are tons of algorithms to sort items. Why do we need to sort elements? Because problems become easier once elements are sorted. For example, you can find a median in constant time when an array is sorted, meaning that you can use a binary search.

Insertion Sort

If you think of the way to sort most easily in your head, it might be similar to insertion sort. How it works is, basically, it swaps pairs of elements from left to right until they are sorted. We will have a pointer called key that is a point starting from 1.

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i
Enter fullscreen mode Exit fullscreen mode

1_nOcET066RQ_fT6qpud24sQ
The code above looks like this visually.

Key will traverse from 1 all the way up to the end (n), and j points to 0 (index). Key will move to the right once its left elements are sorted. This rule can be expressed as follows.

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i
        # as long as j is greater than or equals to 0 and left 
        # element(arr[j]) of key is bigger than key, 

        while j >= 0 and arr[j] > key:
           # swap: its left item will move to key
           arr[j + 1] = arr[j]
           # j moves down to the left
           j = j - 1
        # once all sorted, move elements 
        # where j stopped lastly
        arr[j + 1] = key
Enter fullscreen mode Exit fullscreen mode

1_Ksor4-KvDOox0P62yErqsg
We swapped 9 and 7 because they were unsorted. Because 7 and 9 are sorted, move the key to the right where there is 4. Then compare 9 and 4. 9 is greater than 4 but 4 is on the left-hand side, they should be swapped.

1_Sl6mo4V8_-cMU3aESjIHBQ
Move 4 down to the left until it is sorted. once a pair is swapped, j moves to the left. In this case, until 4 is placed in arr[0] (specifically on the code, when j becomes -1). Then move the key to the right where there is 5.

1_Bk8TZCDmJ4Ci4ip1f6vUcg
Now, key = 5, we need to sort 5 until it goes down to arr[1], let’s do that.

1_CvTKGj4hbE3tKQVAfNt3sw

1_HyQUytuClGP5_jh6ksvMMg
Because key (4) is sorted, move on to elements, the key becomes 1(arr[4]). Keep swapping until 1 is sorted. Then the result will be like below.

1_0V2AMej_19VWP8_8xN0lZA
Now key = 3, we will swap 9 and 3.

1_wPLIbvHiPPVn-Fl-ajPRvQ
The same process goes on until 3 is in arr[1]

1_4Ng8qzuUyahS4Iw9ZHjlvw
Finally, here we are! All elements in the array are sorted.

Time Complexity of Insertion Sort

Now, it is time to talk about the time complexity of the algorithms. As you might assume, it took so long time for us to get here. In a nutshell, the algorithm is O(n²). Let’s analyse why.

1_zvmD6Bgv792T2XEmxZGC6w

As you can see, (2)*O(1) and (2)*O(N) and (2)*O(N). We can actually ignore the coefficient. Therefore, the time complexity would be 1*N*N = N²

In conclusion, the time complexity of insertion is quadratic time, which is not very efficient. There is a faster way to sort elements though. I will introduce one later. Thanks for reading!

Top comments (3)

Collapse
 
icharle7 profile image
cmartín

Nice post! Good job on the other 2 too :D

For al those who want to start learning algorithms I really really recommend the book "Grokking Algorithms" for the first experience. It's just an amazing way to start.

Collapse
 
brucetushabe profile image
TUSHABE

Thanks 😊 for this

Collapse
 
israman30 profile image
Israel Manzo

Very nice, I love python and I like the approaching and explanations of the sorting algorithm.