CODEWITHSUNDEEP
pythonalgorithmsortinginsertion-sort
Moritz Wolff
Moritz Wolff

Reputation: 508

Efficiency Analysis of Two Different Implementations of Insertion Sort

I came up with two implementations for a simple insertion sort algorithm in Python. My question: Is the second implementation more efficient than the first? Because it seems like that in the first implementation, for every iteration of the while loop, the program has to perform two assignments: list[i] gets assigned to list[i-1] and vice versa (apart from decrementing i by 1). 

def insertion1(list):

    for i in range(1,len(list)):     

        while i >= 1 and list[i] < list[i-1]:
            list[i],list[i-1] = list[i-1],list[i]
            i -= 1

But in the second implementation the program has to make only one assignment for every iteration of the while loop: list[index + 1] = list[index] (again apart from decrementing index by 1 and one additional assignment after the termination of the while loop: list[index + 1] = temp). 

def insertion2(list):

    for i in range(1,len(list)):
        temp = list[i]
        index = i - 1

        while index >= 0 and list[index] > temp:
            list[index + 1] = list[index]
            index -= 1
        list[index + 1] = temp

Does this mean that insertion1 roughly has to make twice as many assignment statements compared to insertion2, making insertion2 the more accurate implementation of insertion sort?

Upvotes: 3

Views: 67

Answers (1)

user58697
user58697

Reputation: 7923

Your reasoning is correct. However, even the insertion2 is suboptimal. The inner loop does 2 comparisons per iteration (index >= 0 and list[index] > temp). It is possible to reduce it to (almost) one comparison:

    if temp < list[0]:
        # We don't care about values anymore. Every element shall be shifted.
        while index >= 0:
            list[index + 1] = list[index]
            index -= 1
    else:
        # We don't care about indices anymore. list[0] is a natural sentinel
        while temp < list[index]:
            list[index + 1] = list[index]
            index -= 1
    list[index] = temp

Upvotes: 1

Related Questions