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

ianwillie
Hello Brian, I have some problems with running the code in your book. I like the style of the book very much and I have learnt a lot as...
New
jeremyhuiskamp
Title: Web Development with Clojure, Third Edition, vB17.0 (p9) The create table guestbook syntax suggested doesn’t seem to be accepted ...
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
AndyDavis3416
@noelrappin Running the webpack dev server, I receive the following warning: ERROR in tsconfig.json TS18003: No inputs were found in c...
New
brunogirin
When running tox for the first time, I got the following error: ERROR: InterpreterNotFound: python3.10 I realised that I was running ...
New
dsmith42
Hey there, I’m enjoying this book and have learned a few things alredayd. However, in Chapter 4 I believe we are meant to see the “&gt;...
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
Henrai
Hi, I’m working on the Chapter 8 of the book. After I add add the point_offset, I’m still able to see acne: In the image above, I re...
New
tkhobbes
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New
EdBorn
Title: Agile Web Development with Rails 7: (page 70) I am running windows 11 pro with rails 7.0.3 and ruby 3.1.2p20 (2022-04-12 revision...
New

Other popular topics Top

PragmaticBookshelf
Andy and Dave wrote this influential, classic book to help their clients create better software and rediscover the joy of coding. Almost ...
New
Exadra37
I am thinking in building or buy a desktop computer for programing, both professionally and on my free time, and my choice of OS is Linux...
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
There’s a whole world of custom keycaps out there that I didn’t know existed! Check out all of our Keycaps threads here: https://forum....
New
AstonJ
Just done a fresh install of macOS Big Sur and on installing Erlang I am getting: asdf install erlang 23.1.2 Configure failed. checking ...
New
PragmaticBookshelf
Author Spotlight Mike Riley @mriley This month, we turn the spotlight on Mike Riley, author of Portable Python Projects. Mike’s book ...
New
New
PragmaticBookshelf
Build modern server-driven web applications using htmx. Whatever programming language you use, you’ll write less (and cleaner) code. ...
New
PragmaticBookshelf
Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
New
PragmaticBookshelf
A concise guide to MySQL 9 database administration, covering fundamental concepts, techniques, and best practices. Neil Smyth MySQL...
New

Sub Categories: