On Jun 23, 11:52 am, python_newbie <[EMAIL PROTECTED]> wrote: > I don't know this list is the right place for newbie questions. I try > to implement insertion sort in pyhton. At first code there is no > problem. But the second one ( i code it in the same pattern i think ) > doesn't work. Any ideas ? > > ------------------------------------------------------------ > def insertion_sort(aList): > > for i in range(len(aList)): > for j in range(i): > if aList[i] < aList[j]: > aList.insert(j,aList[i]) > del aList[i+1] > > if __name__ == "__main__": > > MyList = [7,3,5,19,8,2,9,4,15,6,8,3,19] > insertion_sort(MyList) > print MyList > ------------------------------------------------------------- > > def insertion_sort(aList): > > for iterator in aList: > for number in range(aList.index(iterator)): > if iterator < number: > aList.insert(aList.index(number),iterator) > del aList[aList.index(iterator)+1] > > if __name__ == "__main__": > > MyList = [7,3,5,19,8,2,9,4,15,6,8,3,19] > insertion_sort(MyList) > print MyList
In your second attempt `number` is still essentially the same thing as `j` was in the first one. In the following line however, you treat `number` as if it is the actual value. It _should_ be `if iterator < aList[number]`. Also, you are missing a `break` after you do an insertion (this goes for both versions). The bigger question is why did the first one work? I think it works because in this statement `if aList[i] < aList[j]:` the value of `aList[i]` changes after the insertion to a different value. Because of the way this algorithm works, that _new_ value is guaranteed to be >= `aList[j]` so the insertion is never performed again. In the second version `iterator` stays as the original value even after it makes an insertion. This will cause it to perform the insertion multiple times. May I suggest you look into using `enumerate`: >>> for i, val in enumerate([4,5,6]): ... print i, val ... 0 4 1 5 2 6 It allows you to get the index and the value at the same time, which should eliminate the need for `aList.index`. Matt -- http://mail.python.org/mailman/listinfo/python-list
