paolotormon

paolotormon

A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Quickselect In Python (page 221)

Hi, I am trying to convert the ruby code of Quickselect into python and I noticed that I have to add return statements in the if else conditions 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)

In the book version written in Ruby, there “return” is only in “return @array[pivot_index]”, so I think we either remove the return or also put returns on the statements after the other conditionals. Unedited code below:

    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:
            return 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:
            return 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!(5, 0, array.length - 1)

First Post!

jaywengrow

jaywengrow

Author of A Common-Sense Guide to Data Structures and Algorithms

Good point, thank you! This will be modified in a future version of the book.

Where Next?

Popular Pragmatic Bookshelf topics Top

jeffmcompsci
Title: Design and Build Great Web APIs - typo “https://company-atk.herokuapp.com/2258ie4t68jv” (page 19, third bullet in URL list) Typo:...
New
jesse050717
Title: Web Development with Clojure, Third Edition, pg 116 Hi - I just started chapter 5 and I am stuck on page 116 while trying to star...
New
Mmm
Hi, build fails on: bracket-lib = “~0.8.1” when running on Mac Mini M1 Rust version 1.5.0: Compiling winit v0.22.2 error[E0308]: mi...
New
New
leonW
I ran this command after installing the sample application: $ cards add do something --owner Brian And got a file not found error: Fil...
New
oaklandgit
Hi, I completed chapter 6 but am getting the following error when running: thread 'main' panicked at 'Failed to load texture: IoError(O...
New
jonmac
The allprojects block listed on page 245 produces the following error when syncing gradle: “org.gradle.api.GradleScriptException: A prob...
New
creminology
Skimming ahead, much of the following is explained in Chapter 3, but new readers (like me!) will hit a roadblock in Chapter 2 with their ...
New
rainforest
Hi, I’ve got a question about the implementation of PubSub when using a Phoenix.Socket.Transport behaviour rather than channels. Before ...
New
jwandekoken
Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below: d...
New

Other popular topics Top

AstonJ
SpaceVim seems to be gaining in features and popularity and I just wondered how it compares with SpaceMacs in 2020 - anyone have any thou...
New
DevotionGeo
I know that -t flag is used along with -i flag for getting an interactive shell. But I cannot digest what the man page for docker run com...
New
AstonJ
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
New
AstonJ
poll poll Be sure to check out @Dusty’s article posted here: An Introduction to Alternative Keyboard Layouts It’s one of the best write-...
New
PragmaticBookshelf
Learn different ways of writing concurrent code in Elixir and increase your application's performance, without sacrificing scalability or...
New
AstonJ
Biggest jackpot ever apparently! :upside_down_face: I don’t (usually) gamble/play the lottery, but working on a program to predict the...
New
Maartz
Hi folks, I don’t know if I saw this here but, here’s a new programming language, called Roc Reminds me a bit of Elm and thus Haskell. ...
New
PragmaticBookshelf
Author Spotlight: Sophie DeBenedetto @SophieDeBenedetto The days of the traditional request-response web application are long gone, b...
New
New
AstonJ
Curious what kind of results others are getting, I think actually prefer the 7B model to the 32B model, not only is it faster but the qua...
New

Sub Categories: