quick sort swaps count
def _partition(input_list, begin, end):
# For counting the number of swaps
count = 0
# Picks the last number in the list as the pivot
pivot = input_list[end]
i = begin
j = begin
while j < end:
if input_list[j] < pivot:
count += 1
input_list[i], input_list[j] = input_list[j], input_list[i]
i += 1
j += 1
count += 1
input_list[i], input_list[end] = input_list[end], input_list[i]
return i, count
def _quickSort(input_list, begin, end):
count = 0
if begin < end:
pivot, count = _partition(input_list, begin, end)
count += _quickSort(input_list, begin, pivot-1)
count += _quickSort(input_list, pivot + 1, end)
return count
def quickSort(input_list, begin=None, end=None):
if begin == None:
begin = 0
if end == None:
end = len(input_list) - 1
return _quickSort(input_list, begin, end)
test = [1, 3, 5, 2, 4, 6, 7]
counter = quickSort(test)
print(counter)
print(test)
test2 = [3, 7, 6, 9, 1, 8, 10, 4, 2, 5]
counter1 = quickSort(test2)
print(counter1)
print(test2)