Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
quick sort
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.