InsertionSort Problems

Python Help
1

Hi! I am a new python user that is working on the function InsertionSort.
The pathway that I have found looks as such:

Given a boolean order function ord and an orderable list s of data items,

  1. if s is the empty list, return the empty list; otherwise
  2. set up an accumulator and initialize it to the empty list.
  3. Then recursively work through the input list s, inserting the items one by one into the accumulator at the highest possible index in such a way that, at all times, the accumulator is ordered in accordance with the order ord.
  4. Continue in this way until all the elements of s have been dealt with. Then return the accumulator.

I found a way to code it like this, which I believe conceptually works.
def insertionSort(ord,s):
if s == :
return
final =
for i in len(s):
index = 0
while index < len(final) and not ord(s[i], final[index]):
index += 1
final += [i]

return final

When I tested it on this example inserttionSort(lambda p,q: p[1] < q[1], [(‘X’,3),(‘P’,3),(‘P’,4),(‘X’,5),(‘B’,6)]), it failed but I am not sure where to start debugging it because all my loops and actions are correct, to me. Could I have some advice on where to continue? Thanks!

2

Welcome, but please follow the advice here so that your code may be read.

And in the post about merge sort.

3

needs to be something like

final.insert(index, s[i])

to represent insertion. You can insert at the end (or use final.append(s[i]), but at the moment you loop seems not to do anything when index reaches len(s). It’s a bit hard to tell without the indenting.

Printing s[i], index and final in the inner loop should help you debug it.

4

I agree with @jeff5 regarding entering your script to make it appear as it does on your terminal:

format_code
format_code454×506 32 KB

Then your script will appear as shown here (as an example):

if s == 4:
    print('Yes, this is the number four!')

def sample_mult(x, y):
    return x * y
5

hi sorry about the code, I believe this is better.

def insertionSort(ord,s):
    if s == []:
        return []
    final = []
    for i in len(s):
        index = 0
        while index < len(final) and not ord(s[i], final[index]):
            index += 1
        final += s[i]
   
    return final

Thank you for your advice, but I have a query about it. My aim in the last line “final += [i]” would be to add the appropriate item in s, so I changed it to “final += s[i]” as shown. But when I trying testing it, I am getting an “int object is not iterable” error. Do you have any idea why I am getting that?

1 Like
6

This line doesn’t do what you expect:
for i in len(s):

2 Likes
7

Hi. Could you please clarify on what you mean exactly by this as I am not getting what is wrong?

I use that for loop to iterate through s. I mentioned i again in the while loop because I want to make sure that s[i] < final[index]. When the while loop breaks, I then add s[i] (the new highest in my list final), and repeat the process.

Is there something wrong with the implementation based on my ideas above? Thanks!

8

Python’s for statement iterates over a sequence, so you need to either add range() or iterate directly on s, without the len(). See 4. More Control Flow Tools — Python 3.13.3 documentation.

9

Thank you for your response. Just another silly mistake. I added the range bit, and I have uploaded my code. I’m still getting the int object is not iterable error. Why is that so? I can iterate over the int object in the for loop, right?

def insertionSort(ord,s):
    if s == []:
        return []
    final = []
    for i in range(len(s)):
        index = 0
        while (index < len(final)) and (not ord(s[i], final[index])):
            index += 1
        final += i
   
    return final
10

You have the same error message but on a different line, so it’s actually a different error. When your program doesn’t work, you go through an iterative process squashing the bugs one by one. The error message tells you the line number and quotes the context, this time it’s final += i.
If you print the values for final and i, you will see that final is a list and i is a number, and you can’t perform addition on a list and a number. You’ll want to use something else, perhaps append.

3 Likes
11

What @htamas wrote, mostly. Except not append. Don’t lose sight of what this bit is doing, which I assume you wrote:

indexstarts at zero, then it moves along the list you are building, until it finds the place s[i] belongs, when we drop out of the loop.

So the next action should be to insert s[i] in final at position index. (Insert, not overwrite.) Lists have a method for that.

I recommend printing final, index and s[i] just before you do that, so you can see it working.