CODEWITHSUNDEEP
arrayspython-3.xalgorithmsortinginsertion-sort
DeadManProp
DeadManProp

Reputation: 89

Trouble understanding one line in Insertion Sort (Python 3)

I was looking through the other threads concerning the Insertion Sort but didn't find the answer that relates to the specific part of it which I do not understand.

My full Insertion Sort algorithm can be seen below. It works as intended, but I cannot figure out the purpose of that last line.

array[position] = value

Let me explain through an example:

When the 'for' loop starts, index = 1.

=> value = array[1] = 3

=> position = 1

=> Since 4 > 3, the item at index 1, is swapped with the item at index 0.

=> position -= 1

=> position = 0

We now get to the line which confuses me:

array[0] = value

=> value = array[index] = array[0] = 3

However, when the 'for' loop goes through its second iteration, index = 2.

And so immediately value = array[2] and position = 2 ?

Even though I know that this last line of code is necessary I just cannot see what purpose it serves.

Could someone please explain to me this final logical step?

Thank you in advance for your time and help.

array = [4,3,5,6,12,9,8,6]

for index in range (1, len(array)):

   value = array[index]
   position = index

   while position > 0 and array[position - 1] > value:

       array[position] = array[position - 1]
       position -= 1

   array[position] = value

Upvotes: 0

Views: 142

Answers (3)

Subhanshuja
Subhanshuja

Reputation: 418

I think is not really needed at start in for loop, because it was used to index inside the loop. Looks the picture

show process insertion sort

Upvotes: 0

code_vader
code_vader

Reputation: 256

The position variable represents (at the end) where you will eventually insert the number. Without the last line, you are not inserting the number at 'position' at the correct place (it will result in the 1 index after). Below is my code for insertion sort.

def insertionSort(arr):
    length = len(arr)
    for i in range(1, length):
        currNum = arr[i]
        j = i - 1
        while j >= 0 and currNum < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
       arr[j+1] = currNum

   return arr

Upvotes: 4

navneethc
navneethc

Reputation: 1466

You wouldn't have really swapped the numbers without that line, would you?

index 1: 
-> [4,3,5,6,12,9,8,6] (enters while loop)
 -> [4,4,5,6,12,9,8,6]  ("pushes" 4 to position 1)
 -> <waits for while loop to finish>
 -> [3,4,5,6,12,9,8,6] (assigns 3 to position 0 since there are no other elements > 3)

index 2:
...

Upvotes: 1

Related Questions