What happens in the last loop of insertion sort(Python)?

Question

code :

def isort(list):
    for j in range(1,len(list)):
        key=list[j]
        i=j-1
        while i>=0:
            if key>=list[i]:
                list[i+1]=list[i]
                list[i]=key
                i=i-1
            else:
                break
a=[8,5,12]
isort(a)
print (a)

The problem I have is , see here for loop runs 2 times so in first time we get a=[8,5,12] and in second time we get a=[8,12,5] What about 12 & 8 ???

You seem to be missing that the `while` loop runs more than 1 time. In the second iteration of the `for` loop, the `while` loop runs twice, so you get `[12, 8, 5]`. — Barmar, Aug 05 '17 at 18:15

score 1 · Answer 1 · answered Aug 05 '17 at 17:46

1

If you want to know what is going on during your program at the variable level I suggest you use something like Python Visualizer http://www.pythontutor.com/visualize.html#mode=edit

answered Aug 05 '17 at 17:46

Marko

142
2
12

Or just write down the variables on a piece of paper and execute the code by hand. – Barmar Aug 05 '17 at 17:56
@Barmar that can get quite confusing for some people – Marko Aug 05 '17 at 18:04
Perhaps, but IMHO it's the best way to learn. You get a real feel for what's going on in the computer's mind by pretending to be the computer. – Barmar Aug 05 '17 at 18:07

arshovon · Answer 2 · 2017-08-05T19:35:47.717

0

To understand the algorithm correctly, I would suggest to read this tutorial: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/insertionSort.htm

Modified version of your code:

def isort(list):
    for j in range(1,len(list)):
        key=list[j]
        i=j-1
        while i>=0 and key<list[i]:
            list[i+1]=list[i]
            i=i-1
        list[i+1] = key
a=[54,26,93,17,77,31,44,55,20]
isort(a)
print(a)

Output:

[17, 20, 26, 31, 44, 54, 55, 77, 93]

edited Aug 05 '17 at 19:35

answered Aug 05 '17 at 17:01

arshovon

13,270
9
51
69

What did you modify and why? How does this answer his question about how the original code works? – Barmar Aug 05 '17 at 17:58
The original code has not set the list[i+1] to key value. I have modified that. – arshovon Aug 05 '17 at 19:33
It looks like you've reversed the sort. The original code sorts descending, you're sorting ascending. – Barmar Aug 05 '17 at 19:41
That's the reason why your assignments to `list[i]` and `list[i+1]` are different. – Barmar Aug 05 '17 at 19:42

score -2 · Answer 3 · answered Aug 05 '17 at 16:46

-2

I'm not sure that I understand your question, but it seems like you want to order a list of numbers by magnitude. Python makes this easy. Try this:

array = [12, 5, 8]
array.sort()
print(array)  #->[5, 8, 12]

answered Aug 05 '17 at 16:46

Alek Westover

244
1
9

He's trying to understand how insertion sort works, not just sort the data. – Barmar Aug 05 '17 at 17:55

What happens in the last loop of insertion sort(Python)?

3 Answers3