comparisons = 0 # global

def quicksort(lst):
	global comparisons
	if len(lst) <= 1:
		return lst
	lst, store_index = partition(lst)
	comparisons += len(lst[:store_index-1])
	comparisons += len(lst[store_index:])
	return quicksort(lst[:store_index-1]) + [lst[store_index-1]] + quicksort(lst[store_index:])

def partition(lst):
	if len(lst) % 2 == 0:
		middle = int((len(lst) / 2) - 1)
	else:
		middle = int(len(lst) // 2)

	pivot_choice = get_median([lst[0], lst[middle], lst[len(lst)-1]])

	if pivot_choice == lst[0]:
		PIVOT_INDEX = 0
	elif pivot_choice == lst[middle]:
		PIVOT_INDEX = middle
	elif pivot_choice == lst[len(lst)-1]:
		PIVOT_INDEX = len(lst) - 1

	pivot = lst[PIVOT_INDEX]
	lst[0], lst[PIVOT_INDEX] = lst[PIVOT_INDEX], lst[0]
	i = 1
	for j in range(1, len(lst)):
		if lst[j] < pivot:
			lst[j], lst[i] = lst[i], lst[j]
			i += 1
	lst[0], lst[i-1] = lst[i-1], lst[0]
	return lst, i

def get_median(nums):
	values = sorted(nums)
	if len(values) % 2 == 1:
		return values[int((len(values)+1)/2-1)]
	else:
		lower = values[int(len(values)/2-1)]
		upper = values[int(len(values)/2)]
	return (lower+upper)/2

def quicksort_wrapper(lst):
	result = quicksort(lst)
	print(result, comparisons)

file = open('count_comparisons_data.txt', 'r')
a = []
for line in file.readlines():
    a.append(int(line))

num1 = quicksort_wrapper(a)

9458000b8152cfcb2f742ae31e40841d1de47a34
<mask token>


def partition(lst):
    if len(lst) % 2 == 0:
        middle = int(len(lst) / 2 - 1)
    else:
        middle = int(len(lst) // 2)
    pivot_choice = get_median([lst[0], lst[middle], lst[len(lst) - 1]])
    if pivot_choice == lst[0]:
        PIVOT_INDEX = 0
    elif pivot_choice == lst[middle]:
        PIVOT_INDEX = middle
    elif pivot_choice == lst[len(lst) - 1]:
        PIVOT_INDEX = len(lst) - 1
    pivot = lst[PIVOT_INDEX]
    lst[0], lst[PIVOT_INDEX] = lst[PIVOT_INDEX], lst[0]
    i = 1
    for j in range(1, len(lst)):
        if lst[j] < pivot:
            lst[j], lst[i] = lst[i], lst[j]
            i += 1
    lst[0], lst[i - 1] = lst[i - 1], lst[0]
    return lst, i


def get_median(nums):
    values = sorted(nums)
    if len(values) % 2 == 1:
        return values[int((len(values) + 1) / 2 - 1)]
    else:
        lower = values[int(len(values) / 2 - 1)]
        upper = values[int(len(values) / 2)]
    return (lower + upper) / 2


def quicksort_wrapper(lst):
    result = quicksort(lst)
    print(result, comparisons)


<mask token>

<mask token>


def quicksort(lst):
    global comparisons
    if len(lst) <= 1:
        return lst
    lst, store_index = partition(lst)
    comparisons += len(lst[:store_index - 1])
    comparisons += len(lst[store_index:])
    return quicksort(lst[:store_index - 1]) + [lst[store_index - 1]
        ] + quicksort(lst[store_index:])


def partition(lst):
    if len(lst) % 2 == 0:
        middle = int(len(lst) / 2 - 1)
    else:
        middle = int(len(lst) // 2)
    pivot_choice = get_median([lst[0], lst[middle], lst[len(lst) - 1]])
    if pivot_choice == lst[0]:
        PIVOT_INDEX = 0
    elif pivot_choice == lst[middle]:
        PIVOT_INDEX = middle
    elif pivot_choice == lst[len(lst) - 1]:
        PIVOT_INDEX = len(lst) - 1
    pivot = lst[PIVOT_INDEX]
    lst[0], lst[PIVOT_INDEX] = lst[PIVOT_INDEX], lst[0]
    i = 1
    for j in range(1, len(lst)):
        if lst[j] < pivot:
            lst[j], lst[i] = lst[i], lst[j]
            i += 1
    lst[0], lst[i - 1] = lst[i - 1], lst[0]
    return lst, i


def get_median(nums):
    values = sorted(nums)
    if len(values) % 2 == 1:
        return values[int((len(values) + 1) / 2 - 1)]
    else:
        lower = values[int(len(values) / 2 - 1)]
        upper = values[int(len(values) / 2)]
    return (lower + upper) / 2


def quicksort_wrapper(lst):
    result = quicksort(lst)
    print(result, comparisons)


<mask token>

<mask token>


def quicksort(lst):
    global comparisons
    if len(lst) <= 1:
        return lst
    lst, store_index = partition(lst)
    comparisons += len(lst[:store_index - 1])
    comparisons += len(lst[store_index:])
    return quicksort(lst[:store_index - 1]) + [lst[store_index - 1]
        ] + quicksort(lst[store_index:])


def partition(lst):
    if len(lst) % 2 == 0:
        middle = int(len(lst) / 2 - 1)
    else:
        middle = int(len(lst) // 2)
    pivot_choice = get_median([lst[0], lst[middle], lst[len(lst) - 1]])
    if pivot_choice == lst[0]:
        PIVOT_INDEX = 0
    elif pivot_choice == lst[middle]:
        PIVOT_INDEX = middle
    elif pivot_choice == lst[len(lst) - 1]:
        PIVOT_INDEX = len(lst) - 1
    pivot = lst[PIVOT_INDEX]
    lst[0], lst[PIVOT_INDEX] = lst[PIVOT_INDEX], lst[0]
    i = 1
    for j in range(1, len(lst)):
        if lst[j] < pivot:
            lst[j], lst[i] = lst[i], lst[j]
            i += 1
    lst[0], lst[i - 1] = lst[i - 1], lst[0]
    return lst, i


def get_median(nums):
    values = sorted(nums)
    if len(values) % 2 == 1:
        return values[int((len(values) + 1) / 2 - 1)]
    else:
        lower = values[int(len(values) / 2 - 1)]
        upper = values[int(len(values) / 2)]
    return (lower + upper) / 2


def quicksort_wrapper(lst):
    result = quicksort(lst)
    print(result, comparisons)


<mask token>
for line in file.readlines():
    a.append(int(line))
<mask token>

comparisons = 0


def quicksort(lst):
    global comparisons
    if len(lst) <= 1:
        return lst
    lst, store_index = partition(lst)
    comparisons += len(lst[:store_index - 1])
    comparisons += len(lst[store_index:])
    return quicksort(lst[:store_index - 1]) + [lst[store_index - 1]
        ] + quicksort(lst[store_index:])


def partition(lst):
    if len(lst) % 2 == 0:
        middle = int(len(lst) / 2 - 1)
    else:
        middle = int(len(lst) // 2)
    pivot_choice = get_median([lst[0], lst[middle], lst[len(lst) - 1]])
    if pivot_choice == lst[0]:
        PIVOT_INDEX = 0
    elif pivot_choice == lst[middle]:
        PIVOT_INDEX = middle
    elif pivot_choice == lst[len(lst) - 1]:
        PIVOT_INDEX = len(lst) - 1
    pivot = lst[PIVOT_INDEX]
    lst[0], lst[PIVOT_INDEX] = lst[PIVOT_INDEX], lst[0]
    i = 1
    for j in range(1, len(lst)):
        if lst[j] < pivot:
            lst[j], lst[i] = lst[i], lst[j]
            i += 1
    lst[0], lst[i - 1] = lst[i - 1], lst[0]
    return lst, i


def get_median(nums):
    values = sorted(nums)
    if len(values) % 2 == 1:
        return values[int((len(values) + 1) / 2 - 1)]
    else:
        lower = values[int(len(values) / 2 - 1)]
        upper = values[int(len(values) / 2)]
    return (lower + upper) / 2


def quicksort_wrapper(lst):
    result = quicksort(lst)
    print(result, comparisons)


file = open('count_comparisons_data.txt', 'r')
a = []
for line in file.readlines():
    a.append(int(line))
num1 = quicksort_wrapper(a)

comparisons = 0 # global

def quicksort(lst):
	global comparisons
	if len(lst) <= 1:
		return lst
	lst, store_index = partition(lst)
	comparisons += len(lst[:store_index-1])
	comparisons += len(lst[store_index:])
	return quicksort(lst[:store_index-1]) + [lst[store_index-1]] + quicksort(lst[store_index:])

def partition(lst):
	if len(lst) % 2 == 0:
		middle = int((len(lst) / 2) - 1)
	else:
		middle = int(len(lst) // 2)

	pivot_choice = get_median([lst[0], lst[middle], lst[len(lst)-1]])

	if pivot_choice == lst[0]:
		PIVOT_INDEX = 0
	elif pivot_choice == lst[middle]:
		PIVOT_INDEX = middle
	elif pivot_choice == lst[len(lst)-1]:
		PIVOT_INDEX = len(lst) - 1

	pivot = lst[PIVOT_INDEX]
	lst[0], lst[PIVOT_INDEX] = lst[PIVOT_INDEX], lst[0]
	i = 1
	for j in range(1, len(lst)):
		if lst[j] < pivot:
			lst[j], lst[i] = lst[i], lst[j]
			i += 1
	lst[0], lst[i-1] = lst[i-1], lst[0]
	return lst, i

def get_median(nums):
	values = sorted(nums)
	if len(values) % 2 == 1:
		return values[int((len(values)+1)/2-1)]
	else:
		lower = values[int(len(values)/2-1)]
		upper = values[int(len(values)/2)]
	return (lower+upper)/2

def quicksort_wrapper(lst):
	result = quicksort(lst)
	print(result, comparisons)

file = open('count_comparisons_data.txt', 'r')
a = []
for line in file.readlines():
    a.append(int(line))

num1 = quicksort_wrapper(a)
