Why this code for sorting in python falls into an infinite loop?

Question

I want to take a list for sorting and sort it using python random library. The strategy to do this:

First, take any two random index in the list we take as input
Then swap those two elements.
check if the list is sorted or not.
if not sorted , repeat the steps again.

I am new in python. So not well acquainted with all the techniques . Please help with explanation. I cant figure out what is going wrong.

from random import randint

n=int(input())
l=[int(input()) for x in range(0,n)]

p=1

while (1):
  if(p==1):
    ransort(n)
  else:
    break

for x in l:
  print (x)


def ransort(n):
  i=randint(0,n-1)
  j=randint(0,n-1)
  l[i],l[j]=l[j],l[i]

  if l== l.sort():
    p=0
  else:
    p=1
  return p

This algorithm may just be _very_ inefficient. Does it still run infinitely on small lists (of length 2 or 3?) — Ben Jones, Aug 27 '18 at 14:07
Because `p` has no opportunity to change value inside the `while` loop. The `p` inside the function is not the same as the global `p` — roganjosh, Aug 27 '18 at 14:07
Which, BTW, is only sane (`p`'s scope). You can look at `while (p==1): ransort(n)` and *see* whether and how `p` may or may not change. If `ransort` could/would change it from inside the function, that'd be spaghetti code. — deceze, Aug 27 '18 at 14:10
This algorithm makes little to no sense.. `sort` already sorts the list in-place. Calling in in order to check if the list is already sorted is.. weird. — DeepSpace, Aug 27 '18 at 14:10
Well, now you've made it worse. `while (1)` will ***never end***. (Without a `break`, of which there's none.) — deceze, Aug 27 '18 at 14:11
This is just an exercise program. So efficiency is not an issue but comprehension is. I still cant figure out what should be p's position. I have used built in sort method to check if the list is sorted or not. — Sandipan Manna, Aug 27 '18 at 14:12
If it is required I can check the sorting without using sort() method. But I don't think the problem is due to that part. — Sandipan Manna, Aug 27 '18 at 14:16

Norman · Accepted Answer · 2018-09-06T19:21:42.643

0

There are 2 problems:

l.sort() makes an inplace sort so at the second iteration the list will be sorted
the "p" value in the script scope not changing, so the script goes in a loop

to avoid the infinite loop you can do 2 things:

check the returned value

while (p==1):
    p = ransort(n)

or in the ransort function edit the global variable value:

def ransort(n):
   i=randint(0,n-1)
   j=randint(0,n-1)
   l[i],l[j]=l[j],l[i]
   global p
   if l== l.sort():
       p=0
   else:
       p=1

This works:

def ransort(n):
  i=randint(0,n-1)
  j=randint(0,n-1)
  l[i],l[j]=l[j],l[i]
  global p
  if l== l.sort():
    p=0
  else:
    p=1
  return p #here it is

while p == 1:
  p =  ransort(n)

edited Sep 06 '18 at 19:21

answered Aug 27 '18 at 14:16

Norman

435
6
10

But it shows syntax error at global. Error code is File "test.py", line 10\n global p=0\n ^\n SyntaxError: invalid syntax – Sandipan Manna Aug 29 '18 at 14:24
you're right, look at the edit, the variable p is declared as global – Norman Aug 29 '18 at 16:34
Thank you for your help. It really worked. – Sandipan Manna Sep 04 '18 at 13:48
But I had to declare p as global before function definition and also initialize it with 1. If I declare it only in function then it shows Nameerror at the line while (p==1). Please can you explain. My code is here: https://repl.it/@sandipanman/SvelteInsidiousLogin – Sandipan Manna Sep 04 '18 at 14:03
Sorry in the copy paste i miss a row, the ransort function has a "return p" , i'm going to edit the answer so you can understand – Norman Sep 06 '18 at 19:20

Why this code for sorting in python falls into an infinite loop?

1 Answers1