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

johnp
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’. In particula...
New
jeffmcompsci
Title: Design and Build Great Web APIs - typo “https://company-atk.herokuapp.com/2258ie4t68jv” (page 19, third bullet in URL list) Typo:...
New
jskubick
I found an issue in Chapter 7 regarding android:backgroundTint vs app:backgroundTint. How to replicate: load chapter-7 from zipfile i...
New
digitalbias
Title: Build a Weather Station with Elixir and Nerves: Problem connecting to Postgres with Grafana on (page 64) If you follow the defau...
New
brunogirin
When I run the coverage example to report on missing lines, I get: pytest --cov=cards --report=term-missing ch7 ERROR: usage: pytest [op...
New
New
taguniversalmachine
Hi, I am getting an error I cannot figure out on my test. I have what I think is the exact code from the book, other than I changed “us...
New
s2k
Hi all, currently I wonder how the Tailwind colours work (or don’t work). For example, in app/views/layouts/application.html.erb I have...
New
a.zampa
@mfazio23 I’m following the indications of the book and arriver ad chapter 10, but the app cannot be compiled due to an error in the Bas...
New
roadbike
From page 13: On Python 3.7, you can install the libraries with pip by running these commands inside a Python venv using Visual Studio ...
New

Other popular topics Top

AstonJ
What chair do you have while working… and why? Is there a ‘best’ type of chair or working position for developers?
New
New
AstonJ
Thanks to @foxtrottwist’s and @Tomas’s posts in this thread: Poll: Which code editor do you use? I bought Onivim! :nerd_face: https://on...
New
AstonJ
Inspired by this post from @Carter, which languages, frameworks or other tech or tools do you think is killing it right now? :upside_down...
New
AstonJ
I have seen the keycaps I want - they are due for a group-buy this week but won’t be delivered until October next year!!! :rofl: The Ser...
New
AstonJ
In case anyone else is wondering why Ruby 3 doesn’t show when you do asdf list-all ruby :man_facepalming: do this first: asdf plugin-upd...
New
wmnnd
Here’s the story how one of the world’s first production deployments of LiveView came to be - and how trying to improve it almost caused ...
New
mafinar
This is going to be a long an frequently posted thread. While talking to a friend of mine who has taken data structure and algorithm cou...
New
PragmaticBookshelf
Author Spotlight: Sophie DeBenedetto @SophieDeBenedetto The days of the traditional request-response web application are long gone, b...
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: