pythonsortinginsertion-sort

After not swapping an item in an insertion sort, do we move on or does that item still get compared to the others?


In an insertion sort, for example, for the list [20.51, 18.59, 19.21, 17.33, 19.88, 20.09], After comparing 20.51 (item[0]) with itself, and then item[1] and item[0] to get [18.59, 20.51, 19.21, 17.33, 19.88, 20.09], and this goes on and on until we have to sort item[4], which is 19.88, and that's where my question comes in...

[17.33, 18.89, 19.21, 20.51, 19.88, 20.09]

So we compare item[4] with item[3], and we swap them because 19.88 < 20.51, [17.33, 18.89, 19.21, 19.88, 20.51, 20.09]

And then we compare 19.88 with 19.21, which we don't swap because 19.88 > 19.21. After this, does 19.88 still get compared with the other values or do we stop and just start comparing item[5]?


Solution

  • We stop and just start comparing item[5].

    So the current state of the list is: [17.33, 18.89, 19.21, 19.88, 20.51, 20.09]

    And here as item[3] > item [2], i.e 19.88 > 19.21 there is no need to compare 19.88 with the previous elements of the list because they are obviously smaller than 19.88 (as the left part of the list is always sorted in insertion sort).

    Let's look at the code here:-

    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
    

    In the above code, the while loop runs only when key < arr[j].

    So, as in this case, 19.88 > 19.21 (19.88 being the "key" in program), the while loop is exited and the program moves on to item[5]