467,146 Members | 1,021 Online

# insertion sorts...

 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 Jun 27 '08 #1
• viewed: 1757
Share:
9 Replies
 python_newbie wrote: I don't know this list is the right place for newbie questions. It is. We get them all the time. There is also a tutor mailing list. I try to implement insertion sort in pyhton. python At first code there is no problem. It is pretty straightforward. >But the second one ( i code it in the same pattern i think ) Same pattern, but different algorithm as written. doesn't work. Any ideas ? When something 'doesn't work', you should post how and some details. If an exception is raised, *cut and paste* the full traceback and error message after examining it yourself. If bad output is produced, *cut and paste* that. Here is it obvious what good output would be. When it is not, say what you expected that is different. In this case, I am not sure why you think the new algorithm will work. But I suspect you were not trying to write a different algorithm ;-) see below. ------------------------------------------------------------ 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] The last two lines could be replaced with aList[j:i+1] = [aList[i]]+aList[j:i] which directly replace a slice of the list with a rotated version You could also lookup aList[i] just once by adding item = aList[i] before the j loop. This also makes the code slightly easier to read. 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: The members of aList are 'items' or whatever, but not iterators. for number in range(aList.index(iterator)): if iterator < number: aList.insert(aList.index(number),iterator) del aList[aList.index(iterator)+1] Calculating alist.index(item) twice is bad. Do it once before the inner loop. if __name__ == "__main__": MyList = [7,3,5,19,8,2,9,4,15,6,8,3,19] insertion_sort(MyList) print MyList Here is the error message you omitted Traceback (most recent call last): File "C:\Program Files\Python30\misc\temp", line 12, in insertion_sort(MyList) File "C:\Program Files\Python30\misc\temp", line 6, in insertion_sort aList.insert(aList.index(number),iterator) ValueError: list.index(x): x not in list I believe you meant to insert at number, which is a position, not index(position), which only accidentally works. With that corrected, I believe you were trying to write for item in aList: i = aList.index(item) for number in range(i): if item < aList[number]: aList.insert(number,item) del aList[i+1] which looks parallel to the first code, which runs, but which does not sort. The difference is iterating through items instead of positions. The problem is that aList is being modified inside the loop. That usually is a bad idea. If you want to sort the list in place without either copying the list or building a new sorted list, you have to use indexes. Terry Jan Reedy Jun 27 '08 #2
 On Jun 23, 11:52*am, python_newbie = `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 Jun 27 '08 #3
 Matimus wrote: 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`. I thought of suggesting that, but indirectly iterating over a list that is being modified with enumerate has the same problem as directly interating over the same changing list. Jun 27 '08 #4
 On 24 Haziran, 04:33, Terry Reedy >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`. I thought of suggesting that, but indirectly iterating over a list that is being modified with enumerate has the same problem as directly interating over the same changing list. Thanks for all answers. At the end i ve only one point. If a decide to copy list to iterate when will i have to do this ? Before the iteration ? And then iterate through one list and change value of the other ? Jun 27 '08 #5
 On 2008-06-25, python_newbie
 On Jun 25, 11:37*am, "A.T.Hofkamp"
 On 25 Haziran, 17:44, MRAB
 Le Monday 30 June 2008 16:29:11 python_newbie, vous avez ιcrit*: On 25 Haziran, 17:44, MRAB Before starting the iteration would be a good point.... > I usually do in such cases: > for x in mylist[:]: * *... > making a copy just before the for loop starts. > Lately, I have started avoiding in-place modification of lists. Instead, I construct a new list from scratch inside the for-loop, and replace the old list with the newly constructed list afterwards like: > new_list = [] for x in mylist: * *.... * *new_list.append(x) > mylist = new_list > by appending a different value than the original or by not appending, you can influence the contents of the new list. > I find this solution nicer than in-place modification of an existing list. > Sincerely, Albert And if you were originally doing in-place modification because there were also other references to the list then you could just do: mylist[:] = new_list Thanks again. I see that you use two different syntax for lists "mylist = new_list" and "mylist[:] = new_list" these are same i think ? Not at all, try to figure out what happen with the following : >>>[3]: l=[] >>>[4]: g=[] >>>[5]: l == g ...[5]: True >>>[6]: l is g ...[6]: False >>>[7]: l = [4] >>>[8]: l is g ...[8]: False >>>[9]: l == g ...[9]: False >>>[10]: l = g >>>[11]: l is g ...[11]: True >>>[12]: l[:] = [4] >>>[13]: l == g ...[13]: True >>>[14]: l is g ...[14]: True >>>[15]: g ...[15]: [4] -- _____________ Maric Michaud Jun 30 '08 #9
 On Jun 30, 3:29Β*pm, python_newbie

### This discussion thread is closed

Replies have been disabled for this discussion.