CODEWITHSUNDEEP
pythonarraysalgorithmruntime
moritz.burmester
moritz.burmester

Reputation: 1

What makes this specific implementation of Insertionsort so much faster than others?

I have implemented three different versions of Insertionsort in Python. After timing how long each on takes to sort a large list, I noticed how the third one is much faster than the others. Why is that? Aren't they all essentially doing the same and have the same time complexity of O(n^2)?

def insertionsort1(array):

    n = len(array)

    for i in range(n):

        index = 0
        while array[i] > array[index]:
            index +=1

        element = array.pop(i)
        array[index:index] = [element]

    return array


def insertionsort2(arr):

    n = len(arr)

    for i in range(1, n):

        for j in range(i):

            if arr[i] <= arr[j]:

                cache = arr.pop(i)
                arr[j:j] = [cache]

    return arr

def insertionsort3(arr):

    n = len(arr)
    for i in range(n-1):
        pos = i+1

        while pos > 0 and arr[pos] < arr[pos-1]:
            arr[pos], arr[pos-1] = arr[pos-1], arr[pos]
            pos -= 1
    return arr

def timeit(func, arr, n_runs):
    times = []
    for i in range(n_runs):
        start = time.time()
        _ = func(arr)
        end = time.time()
        times.append(end - start)
    avg_time = sum(times) / len(times)
    print(f'Function finished in {round(avg_time, 4)} second(s)')

array = list(np.random.randint(1, 10000, size=10000))

timeit(insertionsort1, array, 1)
timeit(insertionsort2, array, 1)
timeit(insertionsort3, array, 1)

Output of the program:

Function finished in 2.2218 second(s)

Function finished in 3.4489 second(s)

Function finished in 0.0 second(s)

Upvotes: 0

Views: 51

Answers (1)

MBo
MBo

Reputation: 80187

You are sorting already sorted array.

In this case insertion sort takes linear time, so works very fast (it is so-called adaptive sort).

If you put call timeit(insertionsort3, array, 1) at the first place, you'll see close time for insertionsort3

Note that there are too much exchanges in the third function, nevertheless it is close to canonic implementation (while exploiting Python specific might give some gain for other variants)

   for i in range(n-1):
        pos = i+1
        t = arr[pos]
        while pos > 0 and t < arr[pos-1]:
            arr[pos] = arr[pos-1]
            pos -= 1
        arr[pos] = t

Upvotes: 4

Related Questions