I am trying to convert a quickselect from Ruby to Python. The Ruby code is as follows:
class SortableArray
attr_reader :array
def initialize(array)
@array = array
end
def quickselect!(kth_lowest_value, left_index, right_index)
# If we reach a base case - that is, that the subarray has one cell,
# we know we've found the value we're looking for:
if right_index - left_index <= 0
return @array[left_index]
end
# Partition the array and grab the index of the pivot:
pivot_index = partition!(left_index, right_index)
# If what we're looking for is to the left of the pivot:
if kth_lowest_value < pivot_index
# Recursively perform quickselect on the subarray to
# the left of the pivot:
quickselect!(kth_lowest_value, left_index, pivot_index - 1)
# If what we're looking for is to the right of the pivot:
elsif kth_lowest_value > pivot_index
# Recursively perform quickselect on the subarray to
# the right of the pivot:
quickselect!(kth_lowest_value, pivot_index + 1, right_index)
else # if kth_lowest_value == pivot_index
# if after the partition, the pivot position is in the same spot
# as the kth lowest value, we've found the value we're looking for
return @array[pivot_index]
end
end
def partition!(left_pointer, right_pointer)
# We always choose the right-most element as the pivot.
# We keep the index of the pivot for later use:
pivot_index = right_pointer
# We grab the pivot value itself:
pivot = @array[pivot_index]
# We start the right pointer immediately to the left of the pivot
right_pointer -= 1
while true
# Move the left pointer to the right as long as it
# points to value that is less than the pivot:
while @array[left_pointer] < pivot do
left_pointer += 1
end
# Move the right pointer to the left as long as it
# points to a value that is greater than the pivot:
while @array[right_pointer] > pivot do
right_pointer -= 1
end
# We've now reached the point where we've stopped
# moving both the left and right pointers.
# We check whether the left pointer has reached
# or gone beyond the right pointer. If it has,
# we break out of the loop so we can swap the pivot later
# on in our code:
if left_pointer >= right_pointer
break
# If the left pointer is still to the left of the right
# pointer, we swap the values of the left and right pointers:
else
@array[left_pointer], @array[right_pointer] = @array[right_pointer], @array[left_pointer]
# We move the left pointer over to the right, gearing up
# for the next round of left and right pointer movements:
left_pointer += 1
end
end
# As the final step of the partition, we swap the value
# of the left pointer with the pivot:
@array[left_pointer], @array[pivot_index] = @array[pivot_index], @array[left_pointer]
# We return the left_pointer for the sake of the quicksort method
# which will appear later in this chapter:
return left_pointer
end
end
array = [0, 50, 20, 10, 60, 30]
sortable_array = SortableArray.new(array)
p sortable_array.quickselect!(1, 0, array.length - 1)
When I converted it into python it only worked when I put a return after the if and elif conditions (lines 28 and 30) like so:
def partition(left_p, right_p, arr=[]):
pivot_index = right_p
pivot = arr[pivot_index]
right_p -= 1
while True:
while arr[left_p] < pivot:
left_p += 1
while arr[right_p] > pivot:
right_p -= 1
if left_p >= right_p:
break
else:
arr[left_p], arr[right_p] = arr[right_p], arr[left_p]
left_p += 1
arr[left_p], arr[pivot_index] = arr[pivot_index], arr[left_p]
return left_p
def quickselect(kth_lowest_value, left_index, right_index, arr=[]):
print(arr)
if right_index - left_index <= 0:
return arr[left_index]
pivot_index = partition(left_index, right_index, arr)
if kth_lowest_value < pivot_index:
return quickselect(kth_lowest_value, left_index, pivot_index-1, arr)
elif kth_lowest_value > pivot_index:
return quickselect(kth_lowest_value, pivot_index+1, right_index, arr)
else:
print(f"item = {arr[pivot_index]}")
return arr[pivot_index]
array = [200, 97, 100, 101, 211, 107, 63, 123, 11, 34]
index = quickselect(6, 0, len(array)-1, array)
print(index)
Why does it work in Ruby without the return? Is it because it is inside a class?
The Ruby code isn't very idiomatic. The last return in the if-elsif-else branch is a red herring and inconsistent with the other branches in the conditional chain. There's an implicit return on the other branches in the if-elsif-else chain as well.
To generalize the above idea, in all Ruby functions and methods, if control reaches the end of the function without encountering a return, the return value is that of the last expression evaluated. In a conditional chain, that'd be whichever branch was taken.
A minimal example is:
def foo(n)
if n == 0
"zero"
elsif n == 1
"one"
else
"something else"
end
end
puts foo(0) # => zero
puts foo(1) # => one
puts foo(2) # => something else
Adding returns to any or all of the above branches does nothing to change the behavior, and is normally omitted.
Python's implicit return, on the other hand, is always None. Returning a non-None value involves using an explicit return ("explicit is better than implicit" I guess?).
def foo(n):
if n == 0:
return "zero"
elif n == 1:
return "one"
else:
return "something else"
print(foo(0)) # => zero
print(foo(1)) # => one
print(foo(2)) # => something else
Another note about the Ruby code: usually ! after a function/method name is used for in-place algorithms, that is, ones that modify the input, or otherwise more dangerous versions of non-bang methods. Since quickselect! doesn't modify any class state, it's confusing that it has a bang.