
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

Working through the steps (checking that the Info,plist matches exactly), run the demo game and what appears is grey but does not fill th...
New

your book suggests to use Image.toByteData() to convert image to bytes, however I get the following error: "the getter ‘toByteData’ isn’t...
New

Hi everyone!
There is an error on the page 71 in the book “Programming machine learning from coding to depp learning” P. Perrotta. You c...
New

Hi Travis! Thank you for the cool book! :slight_smile:
I made a list of issues and thought I could post them chapter by chapter. I’m rev...
New

Hi @venkats,
It has been mentioned in the description of ‘Supervisory Job’ title that 2 things as mentioned below result in the same eff...
New

This isn’t directly about the book contents so maybe not the right forum…but in some of the code apps (e.g. turbo/06) it sends a TURBO_ST...
New

I’m under the impression that when the reader gets to page 136 (“View Data with the Database Inspector”), the code SHOULD be able to buil...
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

When installing Cards as an editable package, I get the following error:
ERROR: File “setup.py” not found. Directory cannot be installe...
New

Getting an error when installing the dependencies at the start of this chapter:
could not compile dependency :exla, "mix compile" failed...
New
Other popular topics

Bought the Moonlander mechanical keyboard. Cherry Brown MX switches. Arms and wrists have been hurting enough that it’s time I did someth...
New
New

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

I ended up cancelling my Moonlander order as I think it’s just going to be a bit too bulky for me.
I think the Planck and the Preonic (o...
New

Do the test and post your score :nerd_face:
:keyboard:
If possible, please add info such as the keyboard you’re using, the layout (Qw...
New

Seems like a lot of people caught it - just wondered whether any of you did?
As far as I know I didn’t, but it wouldn’t surprise me if I...
New

The File System Access API with Origin Private File System.
WebKit supports new API that makes it possible for web apps to create, open,...
New

There appears to have been an update that has changed the terminology for what has previously been known as the Taskbar Overflow - this h...
New

zig/http.zig at 7cf2cbb33ef34c1d211135f56d30fe23b6cacd42 · ziglang/zig.
General-purpose programming language and toolchain for maintaini...
New

Author Spotlight:
Bruce Tate
@redrapids
Programming languages always emerge out of need, and if that’s not always true, they’re defin...
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
- /emacs
- /haskell
- /java
- /onivim
- /typescript
- /svelte
- /kotlin
- /crystal
- /c-plus-plus
- /tailwind
- /react
- /gleam
- /ocaml
- /elm
- /flutter
- /vscode
- /ash
- /html
- /opensuse
- /centos
- /php
- /deepseek
- /zig
- /scala
- /sublime-text
- /textmate
- /lisp
- /nixos
- /debian
- /react-native
- /agda
- /kubuntu
- /arch-linux
- /django
- /revery
- /ubuntu
- /spring
- /manjaro
- /nodejs
- /diversity
- /lua
- /julia
- /c
- /slackware
- /markdown