[Python] Hoare Partition is not correct?

I'm using Python to implement Hoare Partition. The code is as follows, which is pretty straight-forward.

#!/usr/bin/env python
#-*- coding:utf-8 -*-

def partition(li,start,end):
print(li)
x=li[start]
i=start-1
j=end+1
while True:
while True:
j-=1
if x>=li[j]:
break

while True:
i+=1
if x<=li:
break
if i<j:
li,li[j] = li[j],li
print("i:", i)
print("j:", j)
print(li)
else:
return j

def main():
li=[13,19,9,5,12,8,7,4,11,2,6,21]
print(partition(li,0,11))


if __name__ == '__main__':
main()


but I do not get the right answer. The output is something like:[6, 2, 9, 5, 12, 8, 7, 4, 11, 19, 13, 21] and j=8, because li[j]=11, but there is still a 12 in the middle of the left part. When I manually run this program, I got the same result.

Have I missed something that make the partition function works wrong?

Continue reading...