
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

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

First, the code resources:
Page 237: rumbl_umbrella/apps/rumbl/mix.exs
Note: That this file is missing.
Page 238: rumbl_umbrella/app...
New

I am working on the “Your Turn” for chapter one and building out the restart button talked about on page 27. It recommends looking into ...
New

Dear Sophie.
I tried to do the “Authorization” exercise and have two questions:
When trying to plug in an email-service, I found the ...
New

Hello! Thanks for the great book.
I was attempting the Trie (chap 17) exercises and for number 4 the solution provided for the autocorre...
New

@noelrappin
Running the webpack dev server, I receive the following warning:
ERROR in tsconfig.json
TS18003: No inputs were found in c...
New

I’m a newbie to Rails 7 and have hit an issue with the bin/Dev script mentioned on pages 112-113.
Iteration A1 - Seeing the list of prod...
New

The allprojects block listed on page 245 produces the following error when syncing gradle:
“org.gradle.api.GradleScriptException: A prob...
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

@mfazio23
I’m following the indications of the book and arriver ad chapter 10, but the app cannot be compiled due to an error in the Bas...
New
Other popular topics

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

We have a thread about the keyboards we have, but what about nice keyboards we come across that we want? If you have seen any that look n...
New

If you are experiencing Rails console using 100% CPU on your dev machine, then updating your development and test gems might fix the issu...
New

Think Again 50% Off Sale »
The theme of this sale is new perspectives on familiar topics.
Enter coupon code ThinkAgain2021 at checkout t...
New

Build efficient applications that exploit the unique benefits of a pure functional language, learning from an engineer who uses Haskell t...
New

If you want a quick and easy way to block any website on your Mac using Little Snitch simply…
File > New Rule:
And select Deny, O...
New

Author Spotlight:
VM Brasseur
@vmbrasseur
We have a treat for you today! We turn the spotlight onto Open Source as we sit down with V...
New

Explore the power of Ash Framework by modeling and building the domain for a real-world web application.
Rebecca Le @sevenseacat and ...
New

This is a very quick guide, you just need to:
Download LM Studio: https://lmstudio.ai/
Click on search
Type DeepSeek, then select the o...
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
Latest in A Common-Sense Guide to Data Structures and Algorithms, Second Edition
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /ruby
- /wasm
- /erlang
- /phoenix
- /keyboards
- /rails
- /python
- /js
- /security
- /go
- /swift
- /vim
- /clojure
- /haskell
- /emacs
- /java
- /svelte
- /onivim
- /typescript
- /kotlin
- /crystal
- /c-plus-plus
- /tailwind
- /react
- /gleam
- /ocaml
- /flutter
- /elm
- /vscode
- /ash
- /html
- /opensuse
- /centos
- /php
- /deepseek
- /zig
- /scala
- /sublime-text
- /lisp
- /textmate
- /nixos
- /debian
- /react-native
- /agda
- /kubuntu
- /arch-linux
- /django
- /ubuntu
- /revery
- /spring
- /manjaro
- /deno
- /nodejs
- /diversity
- /lua
- /julia
- /c
- /slackware