Instantly share code, notes, and snippets.

# lysu/sort.rb Last active Dec 15, 2015

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