public
Last active

quick sort

  • Download Gist
sort.rb
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
def partition(list, low, high)
i = low
j = high + 1
base_num = list[low]
 
while true
i += 1
while list[i] < base_num
if i == high
break
end
i += 1
end
 
j -= 1
while list[j] > base_num
if j == low
break
end
j -= 1
end
 
if i >= j
break
end
 
temp = list[i]
list[i] = list[j]
list[j] = temp
 
end
 
temp = list[low]
list[low] = list[j]
list[j] = temp
 
j
 
end
 
def quick_sort(list, left, right)
 
if left >= right
return
end
 
base_index = partition(list, left, right)
 
quick_sort(list, left, base_index - 1)
 
quick_sort(list, base_index + 1, right)
 
list
 
end
 
def quick_sort_3way(list, low, high)
 
if high <= low
return
end
 
less_to = low
great_to = high
i = low + 1
 
base_num = list[low]
 
while i <= great_to
if list[i] < base_num
temp = list[i]
list[i] = list[less_to]
list[less_to] = temp
 
i += 1
less_to += 1
elsif list[i] > base_num
temp = list[i]
list[i] = list[great_to]
list[great_to] = temp
 
great_to -= 1
else
i += 1
end
end
 
quick_sort_3way(list, low, less_to - 1)
quick_sort_3way(list, great_to + 1, high)
 
list
 
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.