Quicksort Python

Question

I just simply don't know where it goes wrong with my code. I'm trying to use Quicksort method to sort an array in ascending order, doesn't seem to work.

def quicksort(array, left, right):
    if left < right: 
        pivot = partition(array, left, right)
        quicksort(array, left, pivot - 1)
        quicksort(array, pivot + 1, right)
        return array

def partition(array, left, right): #left and right are indices
    #pick the pivot as the middle element
    pivot = array[round((left + right)/2)]
    while left < right:
        while array[left] < pivot:
            left += 1
        while array[right] > pivot:
            right -= 1
    if left < right:
        # swap the 2 elements
        array[left], array[right] = array[right], array[left]
        left += 1
        right -= 1

    # swap the pivot and the last element (where the 2 pointers meet each other)
    array[left], array[array.index(pivot)] = array[array.index(pivot)], array[left]
    return left

so when

print(quicksort([4, 6, 8, 1, 3], 0, 4))

the result is

[3, 4, 6, 1, 8]

Answer 1

I don't like using partition(). I just always choose the middle of the list as pivot. This runs pretty fast. It also only goes through the list once per recursion. Numbers are dropped into the Left, Right or Pivot buckets by the ternary if...else(if...else). Then we are called again to sort the smaller buckets. It will do a reverse sort if called with rev=True.

def quicksort(arr,rev=False):
   r = -1 if rev else 1 # Reverse by -1*p and -1*x 
   if len(arr) <= 1: return arr # stop recursing
   else:
      L, P, R = [],[],[] # Left,Pivot and Right
      p = arr[len(arr)//2] # or L[0] or L[-1] 
      for x in arr: # Drop into buckets. 
         (L if x*r<p*r else (P if x==p else R)).append(x)
      return quicksort(L,rev) + P + quicksort(R,rev)

Here is a partition that will work for you. Your choice of pivot made the last swap wrong. Also index() of pivot may find an earlier duplicate of your pivot which will fail. 'right' changes meaning, 'high' stays the end of the range. Here this will let you use your algorithm and still works for any pivot:

def partition(arr, low, high):
    x = (low+(high-1))//2 # or random or arr[0] 
    arr[high], arr[x] = arr[x], arr[high]
    pivot = arr[high]  # mid as pivot
    left = low
    right = high - 1
    
    while left < right: # are we done yet? 
        while left < high and arr[left] <= pivot: 
            left += 1 # one to the right intil we get to pivot 
        while right > low and arr[right] >= pivot:
            right -= 1 # one to the left until we get to pivot 
        if left < right: # swap and try again 
            arr[left], arr[right] = arr[right], arr[left]
            
    if arr[left] > pivot: # swap pivot if needed
        arr[left], arr[high] = arr[high], arr[left]
    return left

I ran the two methods against each other using:

if __name__ == '__main__': 
    # make some random numbers 
    samp_size = 10_000_000
    test_array = [rand(100_000) - 1_000   for i in range(samp_size )] 
    #print (f"test_array = \n{test_array}") 
    # do a quick sort 
    start = time.time()
    new = quicksort(test_array) 
    # print the sorted list 
    #print(f"test_array sorted by quick sort =\n{new}") 
    print(f"Sort of {samp_size:,} elements took {time.time()-start}")

The recursive one uses about twice as much memory but runs way faster.

$ python cursed_quick.py 
Sort of 10,000,000 elements took 37.32265114784241

$ python qsort_partition.py 
Sort of 10,000,000 completed in 303.2601065635681

Answer 2

it is in your partition function, This is not exactly the same partition algorithm but it works and I couldn't find the one you were using.

def partition(array, l, r): #left and right are indices
    #pick the pivot as the middle element
    m = round((l + r)/2)
    array[l], array[m] = array[m], array[l]
    pivot = array[l]
    #place holders
    i = l + 1
    j = r
    while  i <= j:
        while array[j] > pivot:  #do while array[j] is greater than pivot  
            j = j - 1
        while i <= j and array[i] < pivot: #do while array[i] is less than pivot  
            i += 1 
        if i <= j:
            array[i], array[j] = array[j], array[i]
            i += 1
            j -= 1

    array[l], array[j] = array[j], array[l] # swap the pivot and last elements
    return j

If you need to use the algorithm you tried post the psuedo code and it will help no what logic your trying to follow (sorry if this is a comment I don't have the reputation to make them)

Final answer: again

def partition(array, l, r): #left and right are indices
    #pick the pivot as the middle element
    m = round((l + r)/2)'
    array[l], array[m] = array[m], array[l] #move pivot to right side
    pivot = array[l]
    #place holders
    i = l + 1
    j = r
    while  i <= j:
        while array[j] > pivot:  #do while array[j] is greater than pivot  
            j = j - 1
        while i <= j and array[i] < pivot: #do while array[i] is less than pivot  
            i += 1 
        if i <= j:
            array[i], array[j] = array[j], array[i]
            i += 1
            j -= 1

    array[l], array[j] = array[j], array[l] # if swap the pivot and last element
    return j return partition