I'm learning about Sorting Algorithm and now is Insertion Sort. I want to write the code base on my understanding of the algorithm first before copying code on the internet.

My understanding of Insertion Sort is: to sort list a, first create a list containing sorted elements (called a_sorted), and the first element is a[0]. Then I will try to fit each element of a into a_sorted (hope that I understand the idea right). So I implement the idea as below:

a = [4, 3, 1, 5, 7, 9, 6, 2]
n = len(a)

def insertion_sort(a, n):
    a_sorted = [a[0]] # Create a list contain sorted elements, first ele is a[0] => [4]
    for i in range(1,n): # Iterate through original list, from 1th ele (start from 3)

        if a[i] <= a_sorted[0]: 

# First check if the ith ele is smaller than the first ele in the sorted list (smallest). If so insert it to the start of a_sorted
# For example, a_sorted is [3,4], ith ele is 1, 1<3 so add 1 to the start of a_sorted => [1,3,4]
# Then continue to the next ith element
            a_sorted.insert(0, a[i])
            continue

        for j in range(len(a_sorted)-1,-1,-1):

# Compare ith ele to each ele of a_sorted, from largest to the smallest (right to left)
# If ith ele > jth ele in a_sorted, insert ith ele right after the position of jth ele in a_sorted
# For example ith ele is 6, a_sorted is [1, 3, 4, 5, 7, 9], then compare 6 to 9,7,5; 6>5 so insert 6 right after 5 => [1, 3, 4, 5, 6, 7, 9]
# Continue to next ith

            if a[i] > a_sorted[j]:
                a_sorted.insert(j 1, a[i])
                break

       
print(insertion_sort(a, n))

Everything was fine, I got the right output. I just try to stick with the insert idea. But when I searched the code for the Insertion Sort algorithm on google. The code looks completely different from mine (it appears everywhere so I think this is the standard optimized code for Insertion Sort). Below is the code:

def insertionSort(arr):
  
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
  
        key = arr[i]
  
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j 1] = arr[j]
                j -= 1
        arr[j 1] = key
  
  

It's shorter. But I don't understand how it works at all. Still, it's not my question, my question is:

1. Is my code still consider Insertion Sort?
2. Is my code as efficient as the optimal code on the internet (time complexity O(n^2) average, space complexity,...)

I just want to make sure that I can use my code in an interview or an exam when they ask for Insertion Sort. I prefer my code since I understand it and write it myself so it's easier to remember.

CodePudding user response：

Yes, your code is insertion sort with O(n²) time complexity: It maintains a sorted list and subsequently inserts items at the right position in linear time by shifting elements.

The common implementation you have found works in-place (using only swaps). This means it has a better space complexity: It only requires constant auxiliary storage O(1) while you require linear auxiliary storage O(n) to store the sorted list a_sorted.

It does so by "partitioning" the list into a "sorted" and "unsorted" part, constantly growing the "sorted" part by one in each step. I've added comments to the implementation you found to explain this.

def insertionSort(arr):
    # after this loop has run len(arr) - 1 times, the sorted part starting from the first index will have grown to the full array length and the unsorted part will be empty
    for i in range(1, len(arr)):
        # at this point, arr[:i] is sorted; you can verify this by doing
        # print(arr[:i]) here

        key = arr[i] # this element has to be inserted at the correct pos in arr[:i 1]
  
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position: These elements
        # have to be shifted "up" in order to allow inserting
        # the key at the right position; this step is responsible
        # for the quadratic complexity as it requires linear time
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j 1] = arr[j]
                j -= 1
        # the index to insert the key at is j, because arr[j] < key holds
        arr[j 1] = key
        # after this step, the sorted part has grown by one, from arr[:i] to arr[:i 1]