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

abtin
page 20: … protoc command… I had to additionally run the following go get commands in order to be able to compile protobuf code using go...
New
GilWright
Working through the steps (checking that the Info,plist matches exactly), run the demo game and what appears is grey but does not fill th...
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
jdufour
Hello! On page xix of the preface, it says there is a community forum "… for help if your’re stuck on one of the exercises in this book… ...
New
patoncrispy
I’m new to Rust and am using this book to learn more as well as to feed my interest in game dev. I’ve just finished the flappy dragon exa...
New
jskubick
I’m under the impression that when the reader gets to page 136 (“View Data with the Database Inspector”), the code SHOULD be able to buil...
New
Charles
In general, the book isn’t yet updated for Phoenix version 1.6. On page 18 of the book, the authors indicate that an auto generated of ro...
New
jonmac
The allprojects block listed on page 245 produces the following error when syncing gradle: “org.gradle.api.GradleScriptException: A prob...
New
redconfetti
Docker-Machine became part of the Docker Toolbox, which was deprecated in 2020, long after Docker Desktop supported Docker Engine nativel...
New
gorkaio
root_layout: {PentoWeb.LayoutView, :root}, This results in the following following error: no “root” html template defined for PentoWeb...
New

Other popular topics Top

PragmaticBookshelf
Brace yourself for a fun challenge: build a photorealistic 3D renderer from scratch! In just a couple of weeks, build a ray tracer that r...
New
AstonJ
Or looking forward to? :nerd_face:
503 15149 280
New
PragmaticBookshelf
From finance to artificial intelligence, genetic algorithms are a powerful tool with a wide array of applications. But you don't need an ...
New
AstonJ
I’ve been hearing quite a lot of comments relating to the sound of a keyboard, with one of the most desirable of these called ‘thock’, he...
New
AstonJ
This looks like a stunning keycap set :orange_heart: A LEGENDARY KEYBOARD LIVES ON When you bought an Apple Macintosh computer in the e...
New
AstonJ
If you get Can't find emacs in your PATH when trying to install Doom Emacs on your Mac you… just… need to install Emacs first! :lol: bre...
New
PragmaticBookshelf
Get the comprehensive, insider information you need for Rails 8 with the new edition of this award-winning classic. Sam Ruby @rubys ...
New
PragmaticBookshelf
Explore the power of Ash Framework by modeling and building the domain for a real-world web application. Rebecca Le @sevenseacat and ...
New
RobertRichards
Hair Salon Games for Girls Fun Girls Hair Saloon game is mainly developed for kids. This game allows users to select virtual avatars to ...
New
PragmaticBookshelf
Escape callback hell and ship fast, clean code that reads as smoothly as it runs. Squash bugs and stamp out memory leaks with an intuitiv...
New

Sub Categories: