Method: Algorithms::Sort.quicksort

Defined in:
lib/algorithms/sort.rb

.quicksort(container) ⇒ Object

def self.quicksort(container, left = 0, right = container.size - 1)

if left < right 
  middle = partition(container, left, right)
  quicksort(container, left, middle - 1)
  quicksort(container, middle + 1, right)
end

end



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/algorithms/sort.rb', line 180

def self.quicksort(container)
  bottom, top = [], []
  top[0] = 0
  bottom[0] = container.size
  i = 0
  while i >= 0 do
    l = top[i]
    r = bottom[i] - 1;
    if l < r
      pivot = container[l]
      while l < r do
        r -= 1 while (container[r] >= pivot  && l < r)
        if (l < r)
          container[l] = container[r]
          l += 1
        end
        l += 1 while (container[l] <= pivot  && l < r)
        if (l < r)
          container[r] = container[l]
          r -= 1
        end
      end
      container[l] = pivot
      top[i+1] = l + 1
      bottom[i+1] = bottom[i]
      bottom[i] = l
      i += 1
    else
      i -= 1
    end
  end
  container    
end