COSC 2306: Data Programming - Partitioning Strategy
def partition(a_list, first, last):
pivot_value = a_list[first]
left_mark = first + 1
right_mark = last
done = False
while not done:
while left_mark <= right_mark and \
a_list[left_mark] <= pivot_value:
left_mark += 1
while a_list[right_mark] >= pivot_value and \
right_mark >= left_mark:
right_mark -= 1
if right_mark < left_mark:
done = True
else:
# swap left/right marks
a_list[left_mark], a_list[right_mark] = \
a_list[right_mark], a_list[left_mark]
# swap pivot and right_mark
a_list[first], a_list[right_mark] = \
a_list[right_mark], a_list[first]
return right_mark