CODEWITHSUNDEEP
pythonalgorithmrecursionquicksort
Jason Lobell
Jason Lobell

Reputation: 1

Recursive Quicksort using Lambdas

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")

Upvotes: 0

Views: 124

Answers (2)

Mulan
Mulan

Reputation: 135415

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.

Upvotes: 0

trincot
trincot

Reputation: 351384

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.

Upvotes: 1

Related Questions