-1

The principle of this sorting algorithm is simple: starting from a float list inlist to be sorted, the elements of inlist will be extracted one at a time, and placed into a new list outlist (originally empty) such that outlist always remain a sorted list.

This algorithm is supposed to go through every element in the list. However, it just stops half way.

def insertion_sort(inlist):
  outlist = []
  for i in inlist:
    x = inlist.pop(0)
    outlist.append(x)
  return sorted(outlist)

print(insertion_sort([1,2,6,3,5,4]))

The output is [1,2,6] but i want the output to be [1,2,3,4,5,6] What is wrong with my code? Thank you so much for helping.

Seah Jia Hui
  • 21
  • 3
  • Does this answer your question? [How to remove items from a list while iterating?](https://stackoverflow.com/questions/1207406/how-to-remove-items-from-a-list-while-iterating) – Yevhen Kuzmovych Mar 29 '21 at 09:37
  • you are changin the size of `inlist` at every iteration and that explains the output with only 3 elements, that's already not good. But why don't you jut `return sorted(inlist)` – Ivan Mar 29 '21 at 09:40
  • There's no reason to remove items from `inlist` in the loop. All you're doing is making `outlist` a copy of `inlist` and clearing `inlist` (which has no extra effect here). As @Ivan said, you can just return `sorted(inlist)` to get the same effect. – Kemp Mar 29 '21 at 09:50
  • "such that outlist always remain a sorted list" It's definitely not doing that now, and you don't need to `pop` from `inlist` to achieve that. – Jasmijn Mar 29 '21 at 09:55
  • @Jasmijn what do i replace pop with? – Seah Jia Hui Mar 29 '21 at 10:16
  • @SeahJiaHui You're already looping over `inlist`, simply use `i` instead of `x`. You will need to loop over `outlist` as well to figure out where to insert `i`, though, you can't simply `append` it, or it won't be _insertion_ sort. – Jasmijn Mar 29 '21 at 12:35

2 Answers2

0

The correct way of insertion sort is below:

def insertion_sort(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
    return arr

arr = [12, 11, 13, 5, 6]
print(insertion_sort(arr))

However if you to correct you code then change for i in inlist: with for i in range(len(inlist)): Now this i traverse complete inlist, while in you case it is running only half.

Student
  • 102
  • 2
  • 14
  • Hmm but i represents the element right? Within the first for loop, wouldn’t arr[i] be arr[12] and there is no element in the index 12 position? – Seah Jia Hui Mar 29 '21 at 11:29
  • No, `i` is running from 1 to 5 `(len(arr) = 5)` so it will not a problem. – Student Mar 29 '21 at 11:40
-1

I don't understand what you want to achieve but try this:

def insertion_sort(inlist):
    outlist = []
    for i in range(len(inlist)):
        x = inlist.pop(0)
        outlist.append(x)
    return sorted(outlist)

print(insertion_sort([1,2,6,3,5,4]))

Anyway i think the foreach cycle dynamically checks the list lengths but with range-len you get a fix number on the start of the cycle.

Machavity
  • 30,841
  • 27
  • 92
  • 100
rezoThePriest
  • 29
  • 5