Implementing nonrecursive quicksort iterations

Question

Quick sort is often expressed recursively, but I want to solve it with a stack (empty list) iteration

And I want to write a qsort function using the function of partition1.

I don't know how to proceed. Could you help me with a hint?

def partition1(pivot,xs): 
  if xs != []:
    ls, rs = partition1(pivot,xs[1:])
    if xs[0] <= pivot:
      ls.append(xs[0])
    else:
      rs.append(xs[0])
    return ls, rs
  else:
    return [], []

def qsort(xs):
  pass #Create Content

#Example of partition1 operation
partition1(5,[7,2,1,9,4])
=> ls, rs = partition1(5[2,1,9,4])
        =>ls, rs = partition1([5,1,9,4])
.
.
.
        =>ls, rs = partition1(5,[])
           =[],[]
         =[4]. []
       =[4],[9]
.
.
.
  =[4,1,2],[9]                  
=[4,1,2],[9,7]

The desired result value

qsort([3,6,4,7,1,2,5])

->[1,2,3,4,5,6,7]

Answer 1

You'll want to simulate a callstack, in essence.

def quicksort(arr):
    stack = [(0, len(arr))]
    while stack:
        l, r = stack.pop()
        if r - l <= 1:
            continue
        a_l, a_r = partition(arr[l:r], get_pivot(arr[l:r]))
        for i, x in enumerate(a_l + a_r):
            arr[l + i] = x  # write the result of the partitioning process back to arr
        stack.append((l, l + len(a_l)))  # sort the left side of partition
        stack.append((l + len(a_l), r))  # sort the right side of partition

Of course, you have to write your own pivot method here, but there are various choices on how to do so