Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
48 lines (41 sloc) 1.06 KB
def quick_sort(array, from=0, to=nil)
if to == nil
# Sort the whole array, by default
to = array.count - 1
end
if from >= to
# Done sorting
return
end
# Take a pivot value, at the far left
pivot = array[from]
# Min and Max pointers
min = from
max = to
# Current free slot
free = min
while min < max
if free == min # Evaluate array[max]
if array[max] <= pivot # Smaller than pivot, must move
array[free] = array[max]
min += 1
free = max
else
max -= 1
end
elsif free == max # Evaluate array[min]
if array[min] >= pivot # Bigger than pivot, must move
array[free] = array[min]
max -= 1
free = min
else
min += 1
end
else
raise "Inconsistent state"
end
end
array[free] = pivot
quick_sort(array, from, free - 1)
quick_sort(array, free + 1, to)
end
You can’t perform that action at this time.