CODEWITHSUNDEEP
python
martinbshp
martinbshp

Reputation: 1163

sort list with negative numbers

I'm trying to sort a list without modifying the existing list or by using built in functions like sort or sorted. I am having trouble when encountering negative numbers. For example sorting the list

[7,1,-5,18]

produces

[1, -5, 7, 18]

instead of

[-5, 1, 7, 18]

My code:

lst = [7,1,-5,18]
b = list()
init = lst[0]
for i in range(len(lst)):
    b.append(lst[i])
    if b[i]<init:
        tmp = init
        b[i-1] = b[i]
        b[i] = tmp

print b

Upvotes: 0

Views: 4132

Answers (2)

Aran-Fey
Aran-Fey

Reputation: 43196

The problem here is that you're appending values to the end of the list, then moving them one position to the left if they're smaller than the previous element. After changing the position of an element in the list, you would have to check if it needs to be moved again.

Step by step, this is what happens:

remaining elements to sort | "sorted" list | what happens
7,1,-5,18                    []              
1,-5,18                      [7]             first element enters the sorted list
-5,18                        [7,1]           2nd element enters the sorted list
-5,18                        [1,7]           7>1, so last element changes location
18                           [1,7,-5]        3rd element enters sorted list
18                           [1,-5,7]        7>-5, last element changes location
[]                           [1,-5,7,18]     instead of checking whether 1>-5, the 4th
                                             element enters the list

This can easily be fixed by changing the if to a loop like so:

lst = [7,1,-5,18]
b = list()
for i in range(len(lst)):
    b.append(lst[i])
    while i>0 and b[i]<b[i-1]:
        b[i], b[i-1] = b[i-1], b[i]
        i-= 1

print b

Upvotes: 0

riteshtch
riteshtch

Reputation: 8769

You can use this selection sort logic: 

>>> l=[7,1,-5,18]
>>> for i in range(len(l)):
...     for j in range(i+1, len(l)):
...         if l[j]<l[i]:
...             l[i],l[j]=l[j], l[i]
... 
>>> l
[-5, 1, 7, 18]

Upvotes: 1

Related Questions