Advanced Quick Sort - Ruby

advanced_quicksort.rb

# 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])