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
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.
Popular Pragmatic Bookshelf topics
Following the steps described in Chapter 6 of the book, I’m stuck with running the migration as described on page 84:
bundle exec sequel...
New
Hi! I know not the intentions behind this narrative when called, on page XI:
mount() |> handle_event() |> render()
but the correc...
New
The book has the same “Problem space/Solution space” diagram on page 18 as is on page 17. The correct Problem/Solution space diagrams ar...
New
I ran this command after installing the sample application:
$ cards add do something --owner Brian
And got a file not found error:
Fil...
New
I think I might have found a problem involving SwitchCompat, thumbTint, and trackTint.
As entered, the SwitchCompat changes color to hol...
New
I’m not quite sure what’s going on here, but I’m unable to have to containers successfully complete the Readiness/Liveness checks. I’m im...
New
Is there any place where we can discuss the solutions to some of the exercises? I can figure most of them out, but am having trouble with...
New
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error.
lib/pento_web/live/product_l...
New
The allprojects block listed on page 245 produces the following error when syncing gradle:
“org.gradle.api.GradleScriptException: A prob...
New
Is there any plan for volume 2? :slight_smile:
New
Other popular topics
Free and open source software is the default choice for the technologies that run our world, and it’s built and maintained by people like...
New
Write Elixir tests that you can be proud of. Dive into Elixir’s test philosophy and gain mastery over the terminology and concepts that u...
New
Tailwind CSS is an exciting new CSS framework that allows you to design your site by composing simple utility classes to create complex e...
New
Hello everyone! This thread is to tell you about what authors from The Pragmatic Bookshelf are writing on Medium.
New
Build efficient applications that exploit the unique benefits of a pure functional language, learning from an engineer who uses Haskell t...
New
Author Spotlight:
Bruce Tate
@redrapids
Programming languages always emerge out of need, and if that’s not always true, they’re defin...
New
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
Background
Lately I am in a quest to find a good quality TTS ai generation tool to run locally in order to create audio for some videos I...
New
Ok, well here are some thoughts and opinions on some of the ergonomic keyboards I have, I guess like mini review of each that I use enoug...
New
Write elegant Ruby code—not just correct, but idiomatic. Go beyond the vocabulary and syntax and learn to express yourself with eloquence...
New
Latest in A Common-Sense Guide to Data Structures and Algorithms, Second Edition
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /wasm
- /ruby
- /erlang
- /phoenix
- /keyboards
- /python
- /js
- /rails
- /security
- /go
- /swift
- /vim
- /java
- /clojure
- /typescript
- /emacs
- /haskell
- /svelte
- /onivim
- /kotlin
- /c-plus-plus
- /react
- /crystal
- /tailwind
- /gleam
- /ocaml
- /elm
- /vscode
- /flutter
- /html
- /ash
- /deepseek
- /zig
- /opensuse
- /php
- /centos
- /react-native
- /scala
- /lisp
- /sublime-text
- /textmate
- /nixos
- /debian
- /agda
- /deno
- /django
- /kubuntu
- /nodejs
- /arch-linux
- /ubuntu
- /spring
- /revery
- /manjaro
- /quarkus
- /julia
- /diversity
- /lua
- /laravel









