Inplace Quicksort in Ruby

Inplace quicksort algorithum implemented in Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def quicksort(array, first, last)
  if array.length > 1
    return if first > last

    pivot = array[(first + last) * 0.5]
    left = first
    right = last

    while left <= right
      while(array[left] < pivot) do
        left += 1
      end
      while(array[right] > pivot) do
        right -= 1
      end

      if left <= right
        tmp = array[left]
        array[left] = array[right]
        array[right] = tmp

        left += 1
        right -= 1
      end
    end

    quicksort(array, first, right)
    quicksort(array, left, last)
  end
end

Comments