Question

Can someone tell me why my program is working weird. I am trying to sort list1 in ascending order. This code is part of my quick sort program I am trying to write. As per my logic which I am applying in this code, and I checked manually too, the output should be [1,2,3,4,5]. However the output is coming out to be [1,2,2,4,5]. Can you tell what's going wrong?

list1=[3,2,1,5,4]
n_list1=len(list1)
count=0

for position1, item1 in enumerate(list1[0:n_list1]):
    temp=item1
    count=count+1
    for position2 in range(count,n_list1):
        if list1[position1]>list1[position2]:
            list1[position1]=list1[position2]
            list1[position2]=temp
            temp=list1[position1]
print list1

EDIT: What I am trying to do is like this:

I start comparing the first element with the following (n-1) elements and swap the smallest element with the first one. Now I go to 2nd element and compare it with the following (n-2) elements and swap with the smallest element among those (n-2) elements. Like this I move forward.

Note: This is part of my quicksort program and it is not in itself quicksort. This part is for the list1 to which I assign numbers less than pivot. Another code will be for list2 where I will assign numbers greater than pivot.

Was it helpful?

Solution

The answer provided by rbp is absolutely correct!

Also, I guess you could simplify the above by remove count itself, also directly enumerate the list and use the python idiom - a, b = b, a to swap the values

list1=[3,2,1,6,5,4]
n_list1 = len(list1)
for position1, item1 in enumerate(list1):
    for position2 in range(position1,n_list1):
        if list1[position1]>list1[position2]:
            list1[position1] , list1[position2] = list1[position2], list1[position1]
print list1

Output:

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

[Edit: About the idiom]

>>> a = 4
>>> b = 5
>>> a , b  = b, a
>>> a
5
>>> b
4
>>> c  = 5
>>> d = 6
>>> t = c
>>> c = d
>>> d = t 
>>> c
6
>>> d
5
>>> 

OTHER TIPS

Since you do count = count + 1 right before the innermost for, you never get to reach the first position of list1 (list1[0]), which is the element "3".

[Edit] Looking more carefully at your code, there seems to be a lot of confusion. For instance, on

        list1[position1]=list1[position2]
        list1[position2]=temp
        temp=list1[position1]

You're losing list1[position1]: you're overwriting it with list[position2], before trying to save it at the temp variable. Try moving temp=list1[position1] to the first line after the if.

And, honestly, your implementation is overly complicated. I suggest you try writing it in pseudo-code, try to actually understand what's going on, and then re-implement it.

A small improvement to pyfunc's correct answer... This line

for position2 in range(position1,n_list1) 

can be

for position2 in range(position1+1,n_list1)

and will save you a little time.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top