Quicksort Algorithm (In Place) and returns the number of comparisons done.

quicksort.rb

def quicksort arr,startpos,endpos

  def choose_pivot arr,startpos,endpos

    #THis is for selecting median of three , you can return a random number as well. 

    if ((arr[startpos] < arr[endpos]) and (arr[startpos] > arr[startpos+ (endpos-startpos)/2])) or ((arr[startpos] > arr[endpos]) and (arr[startpos] < arr[startpos+ (endpos-startpos)/2]))      
      return startpos
    elsif ((arr[endpos] < arr[startpos]) and (arr[endpos] > arr[startpos+ (endpos-startpos)/2])) or ((arr[endpos] > arr[startpos]) and (arr[endpos] < arr[startpos+ (endpos-startpos)/2]))
      return endpos
    else
      return startpos+ (endpos-startpos)/2
    end

  end

  num_comp = endpos - startpos

  pivot = choose_pivot(arr,startpos,endpos)
  arr[startpos],arr[pivot] = arr[pivot],arr[startpos]
  part_pos = startpos + 1
  for i in startpos+1..endpos
    if arr[startpos] > arr[i]
      arr[part_pos],arr[i] = arr[i],arr[part_pos]
      part_pos += 1
    end
  end

  arr[startpos],arr[part_pos-1] = arr[part_pos-1],arr[startpos]
  if endpos-startpos > 0
    num_comp += quicksort(arr,startpos,part_pos-2) if (part_pos - startpos - 2) > 0
    num_comp += quicksort(arr,part_pos,endpos) if endpos-part_pos > 0
  end
  
  num_comp
  
end