Last active
August 9, 2022 09:27
-
-
Save damdafayton/c9ad357751d0d78dc0254dfdcdd13cc8 to your computer and use it in GitHub Desktop.
Advanced Quick Sort - Ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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