
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

Title: Design and Build Great Web APIs - typo “https://company-atk.herokuapp.com/2258ie4t68jv” (page 19, third bullet in URL list)
Typo:...
New

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

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

A Common-Sense Guide to Data Structures and Algorithms, Second Edition by Jay Wengrow @jaywengrow
Hi,
I have the paperback version of t...
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 allprojects block listed on page 245 produces the following error when syncing gradle:
“org.gradle.api.GradleScriptException: A prob...
New

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

Hi, I’ve got a question about the implementation of PubSub when using a Phoenix.Socket.Transport behaviour rather than channels.
Before ...
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
Other popular topics

SpaceVim seems to be gaining in features and popularity and I just wondered how it compares with SpaceMacs in 2020 - anyone have any thou...
New

I know that -t flag is used along with -i flag for getting an interactive shell. But I cannot digest what the man page for docker run com...
New

Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face:
Perhaps if there’s enough peop...
New

poll
poll
Be sure to check out @Dusty’s article posted here: An Introduction to Alternative Keyboard Layouts It’s one of the best write-...
New

Learn different ways of writing concurrent code in Elixir and increase your application's performance, without sacrificing scalability or...
New

Biggest jackpot ever apparently! :upside_down_face:
I don’t (usually) gamble/play the lottery, but working on a program to predict the...
New

Hi folks,
I don’t know if I saw this here but, here’s a new programming language, called Roc
Reminds me a bit of Elm and thus Haskell. ...
New

Author Spotlight:
Sophie DeBenedetto
@SophieDeBenedetto
The days of the traditional request-response web application are long gone, b...
New

Will Swifties’ war on AI fakes spark a deepfake porn reckoning?
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
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
- /rails
- /js
- /python
- /security
- /go
- /swift
- /vim
- /clojure
- /java
- /haskell
- /emacs
- /svelte
- /onivim
- /typescript
- /crystal
- /c-plus-plus
- /tailwind
- /kotlin
- /gleam
- /react
- /flutter
- /elm
- /ocaml
- /ash
- /vscode
- /opensuse
- /centos
- /php
- /deepseek
- /html
- /scala
- /zig
- /debian
- /textmate
- /nixos
- /sublime-text
- /lisp
- /agda
- /react-native
- /kubuntu
- /arch-linux
- /revery
- /ubuntu
- /manjaro
- /spring
- /django
- /diversity
- /lua
- /nodejs
- /c
- /slackware
- /julia
- /neovim