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
In Chapter 3, the source for index introduces Config on page 31, followed by more code including tests; Config isn’t introduced until pag...
New
As per the title, thanks.
New
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks”
While running the smoke tests in Chapter 2, I get these...
New
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
The generated iex result below should list products instead of product for the metadata. (page 67)
iex> product = %Product{}
%Pento....
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
Hi,
I completed chapter 6 but am getting the following error when running:
thread 'main' panicked at 'Failed to load texture: IoError(O...
New
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error.
lib/pento_web/live/product_l...
New
Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below:
d...
New
Disclaimer: I hope all of this is accurate, and not the result of some stupid typo I failed to notice. Anyways…
This post comprises 2 is...
New
Other popular topics
If it’s a mechanical keyboard, which switches do you have?
Would you recommend it? Why?
What will your next keyboard be?
Pics always w...
New
Ruby, Io, Prolog, Scala, Erlang, Clojure, Haskell. With Seven Languages in Seven Weeks, by Bruce A. Tate, you’ll go beyond the syntax—and...
New
Bought the Moonlander mechanical keyboard. Cherry Brown MX switches. Arms and wrists have been hurting enough that it’s time I did someth...
New
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
New
Small essay with thoughts on macOS vs. Linux:
I know @Exadra37 is just waiting around the corner to scream at me “I TOLD YOU SO!!!” but I...
New
A few weeks ago I started using Warp a terminal written in rust. Though in it’s current state of development there are a few caveats (tab...
New
A Brief Review of the Minisforum V3 AMD Tablet.
Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
New
Hello,
I’m a beginner in Android development and I’m facing an issue with my project setup. In my build.gradle.kts file, I have the foll...
New
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
Open-source implementation of the classic GTA engine now running directly in your browser. Experience the reVC technology demo on DOS.Zon...
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
- /react
- /c-plus-plus
- /crystal
- /tailwind
- /gleam
- /ocaml
- /elm
- /vscode
- /flutter
- /html
- /ash
- /deepseek
- /zig
- /opensuse
- /centos
- /php
- /scala
- /react-native
- /lisp
- /sublime-text
- /textmate
- /nixos
- /debian
- /agda
- /deno
- /django
- /kubuntu
- /nodejs
- /arch-linux
- /spring
- /ubuntu
- /revery
- /manjaro
- /julia
- /quarkus
- /diversity
- /lua
- /markdown









