CODEWITHSUNDEEP
pythonalgorithmsorting
Shams Ansari
Shams Ansari

Reputation: 820

Insertion sort algorithm runtime

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/

Upvotes: 1

Views: 401

Answers (1)

vaeng
vaeng

Reputation: 140

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.

Upvotes: 3

Related Questions