CODEWITHSUNDEEP
pythoninsertion-sort
TeachAble
TeachAble

Reputation: 17

Insertion Sort: Incorrect output

I am trying to learn more about the insertion sort algorithm by writing a little script, however I got stuck.

Everything works great, except one number is being displayed multiple times.

My Code:

#
# Insertion Sort
#

def _ord(l):
 lst=[]
 for k in l:
  if not lst:
   lst.append(k)
   continue

  for a,b in enumerate(reversed(lst)):
   if k <= lst[a]:
    lst.insert(a,k)

   if a == len(lst)-1:
    lst.append(k)

 return lst

if __name__ == '__main__':
 l = [3,2,4,6,5,1]
 print _ord(l)

Output:

[1, 1, 1, 1, 1, 2, 3, 4, 5, 6]

Upvotes: 1

Views: 77

Answers (3)

Hironsan
Hironsan

Reputation: 685

def _old(l):
    for i in range(1, len(l)):
        tmp = l[i]
        for j in reversed(range(i)):
            if l[j] > tmp:
                l[j+1] = l[j]
                l[j] = tmp
            else:
                break
    return l

if __name__ == '__main__':
    l = [3,2,4,6,5,1]
    print(_old(l))

Upvotes: 0

SSSINISTER
SSSINISTER

Reputation: 66

The issue here is when k=1, k <= lst[a] is True for every other integers in the list, so it inserted five times.

A quick fix to the fragment is to introduce break point:

def _ord(l):
 lst=[]
 for k in l:
  if not lst:
   lst.append(k)
   continue

  for a,b in enumerate(reversed(lst)):
   if k <= lst[a]:
    lst.insert(a,k)
    break
   if a == len(lst)-1:
    lst.append(k)

 return lst

if __name__ == '__main__':
 l = [3,2,4,6,5,1]
 print _ord(l)

EDIT: Have a look at this link in order to check out the execution of your fragment.

Upvotes: 2

caimaoy
caimaoy

Reputation: 1228

def _ord(l):
    lst=[]
    for k in l:
        print k
        if not lst:
            lst.append(k)
            continue

        for a,b in enumerate(reversed(lst)):
            print a, b
            if k <= lst[a]:
                lst.insert(a,k)
                break  # <-- add this

            if a == len(lst)-1:
                lst.append(k)
        print lst
        print '-' * 80

    return lst


l = [3,2,4,6,5,1]
print _ord(l)

You can use print or pdb to debug your code.

Upvotes: 2

Related Questions