These Sorting algorithm videos are the best thing to happen ever. I can't thank you enough for your clear and concise explanations. My favourite thing about these explanations is that you don't overcomplicate them, like literally every other tutorial on algorithms ever. Thank you again! You are a fantastic teacher.
If all that meta-programming and splat got you confused, here's a standalone function that does the same thing without adding on to the Array class: def quicksort(arr) return [] if arr.empty? pivot = arr.delete_at(rand(arr.length)) left, right = arr.partition { |o| o < pivot } return [quicksort(left), pivot, quicksort(right)].flatten end puts quicksort([34, 2, 1, 5, 3]).to_s
There is 1 issue with this code... It alters the initial array deleting the value. Quick fix would be to duplicate initial array and work with the new one. def quicksort(arr) return [] if arr.empty? temp_arr = arr.dup pivot = temp_arr.delete_at(rand(temp_arr.length)) left, right = temp_arr.partition { |o| o < pivot } return [quicksort(left), pivot, quicksort(right)].flatten end
It would be almost the same, as follows: def quicksort(array) return [] if array.empty? pivot = array.delete_at(rand(array.size)) left, right = array.partition(&pivot.method(:>)) return *quicksort(left), pivot, *quicksort(right) end arr = [34, 2, 1, 5, 3] p quicksort(arr)
I think this is ingenious code for sorting and I'm going to take it to use it in some of the exercises I'm working on now but I don't think the code in the video follows the wikipedia graphic shown at the beginning for quicksort. What I'm saying is I'm not sure it meets the definition for quicksort IF the definition does indeed state that it's supposed to take the pivot and sort everything to the right and then sort everything to the left (of the pivot). If you change your code to this, look at the output for left and right... def quicksort(arr) return [] if arr.empty? # Could be considered a base case. # Picking a random number and assigning to pivot pivot = arr.delete_at(rand(arr.size)) puts pivot.to_s # Using partition method, pass in pivot variable left, right = arr.partition(&pivot.method(:>)) puts left.to_s puts right.to_s # return *quicksort(left), pivot, *quicksort(right) end arr = [3, 7, 8, 5, 2, 1, 9, 5, 4] # arr = [34,2,1,5,3] p quicksort(arr) What I'm seeing is, for example, if the pivot does equal 4, left is going to be [3, 2, 1] and right is going to be [7, 8, 5, 9, 5]. The impression I got from the video was that left would be [3, 7, 8, 5, 2, 1, 9, 5] and right would be []....again if 4 was chosen as the pivot based on the random selection. Because I'm new I am going to ask, does this still meet the definition of a quick sort? Again, I really want to thank you for this video. It taught me about how to use the Ruby partition method, passing in a block of code and I did some more research on method(:>). One note is if you change method(:>) to method(:
Never mind, the code does look like it meets the quicksort graphic/definition....but in the video, if 1 is the pivot, left does not equal [34, 2] and right does not equal [5, 3]. Left would actually be and empty array and right would be [34, 2, 5, 3]. Sorry about the newbie question.
your right, the impression given is that the partition will separate the first half and second half based on where the pivot index is, but ''&pivot.method(:>)" will actually do what you said. It will give you two arrays with first half being elements less than pivot and second half being greater than. So the video made a little mistake in explaining that part, but like you said the code itself is sound.
Not sure why yet, but I believe this has a bug. If run more than once on an array, it deletes one item each time, reducing the size by one. Code below # quicksort.rb # reference source: th-cam.com/video/-9oC_XAVLBQ/w-d-xo.html class Array def quicksort return [] if empty? pivot = delete_at(rand(size)) left, right = partition(&pivot.method(:>)) return *left.quicksort, pivot, *right.quicksort end end test = Array.new(10) { rand(100) } p test.quicksort.count # => 10 p test.quicksort.count # => 9 p test.quicksort.count # => 8
I think the bug is from using delete_at which alters the input array. If you still want to use it in a class, this isn't destructive: class Array def quicksort return [] if empty? left, right = partition{|v| v < last} pivot = right.pop left.quicksort + [pivot] + right.quicksort end end
These Sorting algorithm videos are the best thing to happen ever. I can't thank you enough for your clear and concise explanations. My favourite thing about these explanations is that you don't overcomplicate them, like literally every other tutorial on algorithms ever. Thank you again! You are a fantastic teacher.
I'm glad that you are finding them helpful!
If all that meta-programming and splat got you confused, here's a standalone function that does the same thing without adding on to the Array class:
def quicksort(arr)
return [] if arr.empty?
pivot = arr.delete_at(rand(arr.length))
left, right = arr.partition { |o| o < pivot }
return [quicksort(left), pivot, quicksort(right)].flatten
end
puts quicksort([34, 2, 1, 5, 3]).to_s
There is 1 issue with this code... It alters the initial array deleting the value. Quick fix would be to duplicate initial array and work with the new one.
def quicksort(arr)
return [] if arr.empty?
temp_arr = arr.dup
pivot = temp_arr.delete_at(rand(temp_arr.length))
left, right = temp_arr.partition { |o| o < pivot }
return [quicksort(left), pivot, quicksort(right)].flatten
end
Pretty cool implementation! Pretty confusing syntax for newbies like myself. Maybe down the road!
if I don't want to use class Array how would the code change? I need it in it's own class
It would be almost the same, as follows:
def quicksort(array)
return [] if array.empty?
pivot = array.delete_at(rand(array.size))
left, right = array.partition(&pivot.method(:>))
return *quicksort(left), pivot, *quicksort(right)
end
arr = [34, 2, 1, 5, 3]
p quicksort(arr)
I think this is ingenious code for sorting and I'm going to take it to use it in some of the exercises I'm working on now but I don't think the code in the video follows the wikipedia graphic shown at the beginning for quicksort. What I'm saying is I'm not sure it meets the definition for quicksort IF the definition does indeed state that it's supposed to take the pivot and sort everything to the right and then sort everything to the left (of the pivot). If you change your code to this, look at the output for left and right...
def quicksort(arr)
return [] if arr.empty? # Could be considered a base case.
# Picking a random number and assigning to pivot
pivot = arr.delete_at(rand(arr.size))
puts pivot.to_s
# Using partition method, pass in pivot variable
left, right = arr.partition(&pivot.method(:>))
puts left.to_s
puts right.to_s
# return *quicksort(left), pivot, *quicksort(right)
end
arr = [3, 7, 8, 5, 2, 1, 9, 5, 4]
# arr = [34,2,1,5,3]
p quicksort(arr)
What I'm seeing is, for example, if the pivot does equal 4, left is going to be [3, 2, 1] and right is going to be [7, 8, 5, 9, 5]. The impression I got from the video was that left would be [3, 7, 8, 5, 2, 1, 9, 5] and right would be []....again if 4 was chosen as the pivot based on the random selection. Because I'm new I am going to ask, does this still meet the definition of a quick sort?
Again, I really want to thank you for this video. It taught me about how to use the Ruby partition method, passing in a block of code and I did some more research on method(:>). One note is if you change method(:>) to method(:
Never mind, the code does look like it meets the quicksort graphic/definition....but in the video, if 1 is the pivot, left does not equal [34, 2] and right does not equal [5, 3]. Left would actually be and empty array and right would be [34, 2, 5, 3]. Sorry about the newbie question.
your right, the impression given is that the partition will separate the first half and second half based on where the pivot index is, but ''&pivot.method(:>)" will actually do what you said. It will give you two arrays with first half being elements less than pivot and second half being greater than.
So the video made a little mistake in explaining that part, but like you said the code itself is sound.
thnku sir for this explanation
Not sure why yet, but I believe this has a bug. If run more than once on an array, it deletes one item each time, reducing the size by one. Code below
# quicksort.rb
# reference source: th-cam.com/video/-9oC_XAVLBQ/w-d-xo.html
class Array
def quicksort
return [] if empty?
pivot = delete_at(rand(size))
left, right = partition(&pivot.method(:>))
return *left.quicksort, pivot, *right.quicksort
end
end
test = Array.new(10) { rand(100) }
p test.quicksort.count # => 10
p test.quicksort.count # => 9
p test.quicksort.count # => 8
I think the bug is from using delete_at which alters the input array. If you still want to use it in a class, this isn't destructive:
class Array
def quicksort
return [] if empty?
left, right = partition{|v| v < last}
pivot = right.pop
left.quicksort + [pivot] + right.quicksort
end
end