Insertion sort algorithm runtime

Question

I was trying to see the difference in runtime for different sorting algorithms when I found that I was getting consistently faster runtime for one version of Insertion sort than another version of insertion sort. The versions of the algorithms seem nearly Identical (only a 1 off the difference). I am not sure why. One version (slower one) is from w3resource and the other one (faster one) is from geeksforgeeks. I am doing the comparison in python.

Geeks for Geeks

def insertion_sort_geeks(a):
    """
    https://www.geeksforgeeks.org/insertion-sort/
    :param a: Array
    :return:  time to sort
    """
    start = time.time()
    for i in range(1, len(a)):
        current_val = a[i]
        j = i - 1
        while j >= 0 and a[j] > current_val:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = current_val
    end = time.time()
    return end - start

W3Resource Algorithm

def insertion_sort_w3(a):
    """
    https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-6.php
    :param a: array
    :return: time to sort
    """
    start = time.time()
    for i in range(1, len(a)):
        current_val = a[i]
        j = i
        while j > 0 and a[j - 1] > current_val:
            a[j] = a[j - 1]
            j -= 1
        a[j] = current_val
    end = time.time()
    return end - start

When I run these algorithms, I consistently find that the geeksforgeeks algorithm is faster but cannot figure out why?

-- Sort on a list of 10,000 ints (randomized)

Insertion Sort Geek     Insertion Sort W3
4.727362155914307       5.441751718521118
4.595118761062622       5.537100791931152
4.742804050445557       5.453729867935181
4.684415102005005       5.44006609916687
4.790072202682495       5.50256085395813
4.789106845855713       5.894493818283081
5.104598045349121       6.107465982437134
5.100121021270752       5.738892078399658
4.825102090835571       5.55505895614624
4.877285003662109       5.7944769859313965

https://github.com/ShamsAnsari/Algorithms

https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-6.php https://www.geeksforgeeks.org/insertion-sort/

vaeng · Accepted Answer · 2020-02-24 09:05:31Z

3

The top one defines j once per outer loop. 10.000 times. In the bottom one you have to decrease j in every inner loop control for testing. That's (10.000 * 10.000 - 10.000)/2 as an upper limit (thanks to @trincot for correcting this) operations more.

Slower Version:

j = i
       while j > 0 and a[j - 1] > current_val:

Faster Version:

j = i - 1
        while j >= 0 and a[j] > current_val:

I think the a[j - 1] is the main difference.

edited Feb 24, 2020 at 9:05

answered Feb 24, 2020 at 7:57

vaeng

1501 silver badge15 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Shams Ansari Over a year ago

I decrease j in both Algorithms (inside while statement)

vaeng Over a year ago

Yes, the body of the loop is pretty much the same, the control part is not. I edited my post for clarification @ShamsAnsari

trincot Over a year ago

This is the right answer. However, "That's 10.0000 * 10.000 - 10.000" should be "That's up to (10.000 * 10.000 - 10.000) / 2" (one zero removed, division added, and it's an upper limit)

Shams Ansari Over a year ago

I added a counter inside the while loop for both algorithms and both while loops execute the same number of times @vaegn

vaeng Over a year ago

That's how it should be. The difference is, that you do the "j - 1" outside of the loop or in the loop control. If you do it in the loop control it is calculated for the numbers the loop body is run + 1 for the final check that would not enter the loop body. When you calculate the j-1 before you enter the loop control, you save that tiny calculation time.

Collectives™ on Stack Overflow

Insertion sort algorithm runtime

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related