Recursive Quicksort using Lambdas-CodePudding

I'm trying to implement a recursive quicksort algorithm using two methods (swap, partition) while running the main algorithm using recursion in a lambda expression. I'm getting an infinite recursion error and honestly I can't find the syntax error. Can someone help me out? Thanks :)

def swap(array, a, b):
        array[a], array[b] = array[b], array[a]
def partition(array, high, low):
    pivot = array[high]
    i = low
    for x in range(low, high-1):
        if array[x] < pivot:
            i =1
            swap(array, array[x], array[high])
    return i
g = lambda array, low, high: g(array,low,partition(array,high,low)-1) g(array,partition(array,high,low) 1,high) if low < high else print("not sorted")

CodePudding user response：

There are several issues in partition:

The call to swap is passing values from your list, instead of indices.
Even when the previous mistake is corrected, it will either move the pivot value to the low 1 index, or it will not move at all.
The returned index i, should be the one where the pivot was moved. In a correct implementation that means i is the last index to which a value was moved, which was the value at index high. This is not what is happening, as already with the first swap the pivot value is moved.
The swap should be of the current value with the value at i, so that all values up to the one at index i are less or equal to the pivot value.

Here is the corrected partition function:

def partition(array, high, low):
    pivot = array[high]
    i = low - 1
    for x in range(low, high 1):
        if array[x] <= pivot:
            i =1
            swap(array, x, i)
    return i

These are the issues in the function g:

It is supposed to perform the sort in-place, so the operator for lists should not occur here, as that would create a new list. Moreover, the base case (in else) does not return anything, so the operator will fail with an error
partition(array,high,low) is called twice, which is not only a waste, but the second call will in most cases return a different result, because the pivot can be different. This means the second call of g will potentially not work with an adjacent partition, but will either leave an (unsorted) gap, or work on an overlapping partition.

Here is a correction for the function g:

def g(array, low, high):
    if low < high:
        i = partition(array, high, low)
        g(array, low, i-1)
        g(array, i 1, high)

You should also consider using a better name than g, and change the order of the high/low parameters for partition: that reversed order is a good way to confuse the readers of your code.

CodePudding user response：

Here is Hoare's quicksort algorithm implemented in Python -

def quicksort(A, lo, hi):
  if lo >= 0 and hi >= 0 and lo < hi:
    p = partition(A, lo, hi)
    quicksort(A, lo, p)
    quicksort(A, p   1, hi)

def partition(A, lo, hi):
  pivot = A[(hi   lo) // 2]
  i = lo
  j = hi
  while True:
    while A[i] < pivot:
      i  = 1
    while A[j] > pivot:
      j -= 1
    if i >= j:
      return j
    swap(A, i, j)

def swap(A, i, j):
  A[i], A[j] = A[j], A[i]

You can write g using lambda if you wish, but I would recommend to define an ordinary function instead -

g = lambda a: quicksort(a, 0, len(a) - 1)

Given a sample input, x -

x = [5,0,9,7,4,2,8,3,1,6]
g(x)
print(x)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

See this related Q&A if you would like to count the number of comparisons and swaps used.