Discussion Room : IDC101

A weird program doing something more weird

A weird program doing something more weird

by Mirudula E -
Number of replies: 5

Consider this piece of program.

def swaplist(a,i,j):
    t=a[i]
    a[i]=a[j]
    a[j]=t
    return a
def sortlist(b):
    for i in range(len(b)):
        for j in range(len(b)):
            if b[i] > b[j]:
                swaplist(b,i,j)           
    return b
l=[3,1,2,2,3,1,6,7,4,5,7,8,4,2,54,74,2,7,36,3]
sortlist(l)

And the output is:

[74, 54, 36, 8, 7, 7, 7, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1]
That's not what I was expecting. Rather, I was expecting the sorting in ascending order. Is there something wrong? However, if you replace (len(b)) by  (i,len(b)) in for j in range(len(b)) of def sortlist, the output is in ascending order.

Can someone state why we get this weird output?



(Edited by Dr. Amit Kulshrestha - original submission Tuesday, August 28, 2018, 6:27 PM)

In reply to Mirudula E

Re: A weird program doing something more weird

by Dr. Amit Kulshrestha -

Thanks Mirudula for posting this interesting piece of Python coding. That shows even small differences in programs may result into big difference in the output!

I will give some hint on why the output is not that weird.

Your (I,j) is varying over a "square grid" of points, isn't it? The diagonal of this grid splits the square into two parts : upper triangle and lower triangle. Now, which triangle do you think is dominating the code? Upper one or the lower one?

This is merely a hint. Now I invite everyone to make it explicit. I will be happy to receive explanations to this hint, or other explanations.

Keep Pythoning!

In reply to Mirudula E

Re: A weird program doing something more weird

by Abineet Parichha . -

I believe this to be a modified form of selection sort.

Case 1(original)-----

Everytime the inner loop ( j ) terminates, the smallest element gets placed at i th position by repeated swapping. Since you have iterated the inner loop from 0th index, the smallest one that had previously been placed at (i - 1)th position now moves to ith position, and finally lands up at the last value of i i.e. len(b)-1 index, after the termination of the outerloop( i ). Also, suppose the largest element was at kth position since the beginning. Once the i loop takes the value k, the largest element is compared with 0th index element and gets swapped and remains fixed there throughout all iterations. Similarly, the second largest element gets swapped-placed at 1th index and so on, thereby arranging them all in descending order......All of this because the inner loop started iterations from 0th index.

Therfore, once you you make the inner loop iterations start from ith position(although it will be better to start from i+1th index), all these problems are solved as you saw in case 2.

In reply to Mirudula E

Re: A weird program doing something more weird

by Bhavik . -

just switch the sign to b[i]<b[j] instead of '>'.you will get the ascending order.