Python

**I need to make a quicksort algorithm but so that it uses only one list and does swaps inside of it. I managed to make it “sort” or position the first element but now i don’t know how to implement the recursion. The biggest problem I’m having is how to recursively work on a part of the list instead of making the new one. Here is my code: ——————————————————————————-** New code, same problem.

Here is my code. It does the job but gets stuck in the loop.

def qsort(n,l,g):
if l is None:
    l=0
if g is None:
    g=len(n)
if g-l<=1:
    return n
print g-l
p=n[l]
i=1+l
j=1+l
for x in n[l+1:g]:
    if x<p:
        n[i],n[j]=n[j],n[i]
        i+=1
    j+=1
n[l],n[i-1]=n[i-1],n[l]
ls=0
le=i-1
gs=i
ge=j
print n
qsort(n,ls,le)
qsort(n,gs,ge)

Can someone give me any suggestions, I’m lost. Can’t find whats wrong or how to fix it. Know its messy but cant do better atm :D

Answer

Write it like this:

def qsort(li, lo=None, hi=None):
    if lo is None:
        lo = 0
    if hi is None:
        hi = len(li) - 1
    ...
    ...
    if hi - lo > 1:
        qsort(## left half ##)
        qsort(## right half ##)

lo and hi are the smallest and largest indexes you should look at in li, respectively.

Advertisement

Answer