Skip to content

Instantly share code, notes, and snippets.

@damdafayton
Last active August 9, 2022 09:27
Show Gist options
  • Save damdafayton/c9ad357751d0d78dc0254dfdcdd13cc8 to your computer and use it in GitHub Desktop.
Save damdafayton/c9ad357751d0d78dc0254dfdcdd13cc8 to your computer and use it in GitHub Desktop.
Advanced Quick Sort - Ruby
# Instead of copying the array into multiple sub-arrays, use indices to keep track of the different sub-arrays.
# You can pass the indices to a modified partition method.
# The partition method should partition the sub-array and then return the index location where the pivot gets placed, so you can then call partition on each side of the pivot.
# Since you cannot just create new sub-arrays for the elements, Partition will need to use another trick to keep track of which elements are greater and which are smaller than the pivot.
def partition(array, start_pointer, end_pointer)
# print [start_pointer, end_pointer], "\n"
# return array if array.length==1
pivot_pointer = start_pointer
counter = start_pointer
while counter < end_pointer do
# print([array[counter], array[end_pointer], pivot_pointer],"\n")
if array[counter] < array[end_pointer] then
unless counter == pivot_pointer
temp = array[pivot_pointer]
array[pivot_pointer] = array[counter]
array[counter] = temp
end
pivot_pointer += 1
end
if (array[counter] == array[end_pointer]) and (end_pointer-counter>1) then
array[end_pointer] = array[counter+1]
array[counter+1] = array[counter]
counter = pivot_pointer = start_pointer
else
counter += 1
end
end
temp = array[pivot_pointer]
array[pivot_pointer] = array[end_pointer]
array[end_pointer] = temp
# puts "#{array}"
puts array.join(' ')
return array, pivot_pointer
end
def advanced_quicksort(array)
# write your code here
start_pointer, pivot_pointer, end_pointer = 0, 0, array.length - 1
pivot_checked = Hash.new{|k,v| pivot_checked[v] = false}
while start_pointer < end_pointer do
(array, pivot_pointer) = partition(array, start_pointer, end_pointer) unless pivot_checked[end_pointer]
pivot_checked[pivot_pointer] = true
_end_pointer = pivot_pointer - 1
while start_pointer < _end_pointer do
(array, pivot_pointer) = partition(array, start_pointer, _end_pointer) unless pivot_checked[_end_pointer]
pivot_checked[pivot_pointer] = true
_end_pointer = _end_pointer-=1
end
start_pointer = pivot_pointer + 1
puts start_pointer
end
end
# advanced_quicksort([1, 3, 9, 8, 2, 7, 5])
# => 1 3 2 5 9 7 8
# 1 2 3 5 9 7 8
# 1 2 3 5 7 8 9
advanced_quicksort([1, 3, 9, 8, 2, 7, 5,23,1,245,46,12,34])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment