2018-2019
2018-2019 copied to clipboard
comp-think
Lecture "Divide and conquer algorithm", exercise 2
Develop the divide and conquer algorithm def quicksort(input_list, start, end) that takes a list and the positions of the first and last elements in the list to consider as inputs, and that calls partition(input_list, start, end, start) (defined in the previous exercise) to partition the input list into two slices, and then applies itself recursively on the two partitions (neither of which includes the pivot value since it has been already correctly positioned by means of the execution of partition). In addition, define appropriately the base case of the algorithm so as to stop if needed before to run the partition algorithm.
Accompany the implementation of the function with the appropriate test cases.
def test_quicksort(input_list,start,end,expected):
result = quicksort(input_list,start,end)
if result == expected:
return True
else:
return False
def quicksort(input_list,start,end):
start = partition(input_list, start, end, start)
if start != len(input_list):
start +=1
if(start<len(input_list)):
partition(input_list, start, end, start)
return input_list
else:
return input_list
#partition function
def partition(input_list, start, end, pivot_position):
pivot_value = input_list[pivot_position]
for position, item in enumerate(input_list):
if start <= position <= end:
if item in input_list[start:pivot_position+1]:
if item > pivot_value:
new_value = item
input_list.pop(position)
input_list.insert(end,new_value)
pivot_position = position
elif item in input_list[pivot_position+1:end+1]:
if item < pivot_value:
new_value = item
input_list.pop(position)
input_list.insert(start,new_value)
pivot_position = position
for position, item in enumerate(input_list):
if start <= position <= end:
if item in input_list[start:pivot_position+1]:
if item > pivot_value:
for position, item in enumerate(input_list):
if item == pivot_value:
pivot_position = position
partition(input_list, start, end, pivot_position)
elif item in input_list[pivot_position+1:end+1]:
if item < pivot_value:
for position, item in enumerate(input_list):
if item == pivot_value:
pivot_position = position
partition(input_list, start, end, pivot_position)
for position, item in enumerate(input_list):
if item == pivot_value:
return position
#Since lists are mutable, we have used different names for each list while running the test.
my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list2 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list2 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list3 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
print(test_quicksort(my_list, 1, 4,["The Graveyard Book", "American Gods","Coraline", "Good Omens","Neverwhere"])) #True
print(test_quicksort(my_list2, 2, 4,["The Graveyard Book", "Coraline", "American Gods","Good Omens","Neverwhere",])) #True
print(test_quicksort(my_list2, 3, 4,["The Graveyard Book", "Coraline", "American Gods" , "Good Omens","Neverwhere"])) #True
This recursive quicksort algorithm should work with any kind of input.
Note: Against what I wrote in the other thread, I have not yet optimised the partition algorithm. However, the following partition algorithm was adjusted to work with quicksort. If I have time, I would still like to eliminate the unnecessary "excerpt_list workaround" in the partition algorithm.
+++ Quicksort. +++
def quicksort(input_list, start, end):
if 0 <= start <= end <= len(input_list):
if len(input_list[start:end]) <= 1:
if input_list[start] > input_list[end]:
input_list[end], input_list[start] = input_list[start], input_list[end]
return input_list
else:
pivot_position = partition(input_list, start, end, start)
quicksort(input_list, pivot_position + 1, end)
quicksort(input_list, start, pivot_position)
return input_list
else:
print("Input values without effect.")
return input_list
+++ Quicksort, Partition, and Testing Sets. +++
def test_quicksort(input_list, start, end, expected):
return expected == quicksort(input_list, start, end)
def partition(input_list, start, end, pivot_position):
pivot_object = input_list[pivot_position]
excerpt_list = input_list[start:end + 1]
excerpt_list.remove(pivot_object)
ordered_list = [pivot_object]
def conductor(input):
input_len = len(input)
if input_len == 1:
return assistant(input)
else:
mid = input_len // 2
conductor(input[0:mid])
conductor(input[mid:input_len])
def assistant(value):
if value[0] > pivot_object:
ordered_list.insert(len(ordered_list), value[0])
else:
ordered_list.insert(0, value[0])
conductor(excerpt_list)
input_list[start:end + 1] = ordered_list
print(input_list.index(pivot_object))
return input_list.index(pivot_object)
def quicksort(input_list, start, end):
if 0 <= start <= end <= len(input_list):
if len(input_list[start:end]) <= 1:
if input_list[start] > input_list[end]:
input_list[end], input_list[start] = input_list[start], input_list[end]
return input_list
else:
pivot_position = partition(input_list, start, end, start)
quicksort(input_list, pivot_position + 1, end)
quicksort(input_list, start, pivot_position)
return input_list
else:
print("Input values without effect.")
return input_list
print(test_quicksort([3, 1, 6, 4, 7, 9, 2, 5, 8, 0], 0, 9, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))
print(test_quicksort(["Rory", "Lorelai", "Luke", "Lane"], 1, 3, ["Rory", "Lane", "Lorelai", "Luke"]))
print(test_quicksort(["Tristan", "Logan", "Jess", "Dean"], 5, 3, ["Tristan", "Logan", "Jess", "Dean"]))
I haven't yet correctly separated the code between quicksort() and partition(), but this quicksort() that contains my partition() code does the job. Will continue trying to separate tomorrow.
def test_quicksort(input_list, s, e, pp, expected):
result = quicksort(input_list, s, e, pp)
if result == expected:
return True
else:
return False
def quicksort(input_list, s, e, pp):
len_input_list = len(input_list)
if len_input_list <= 2: # base case: list with only 2 items
input_list = sorted(input_list) # make sure the two items are in order
return input_list
else: # recursive step
pv = input_list[pp] #pivot value is the item at pivot position in input lsit
for item in input_list[s:(e +1)]:
if item == pv:
pass
elif item < pv:
input_list.remove(item)
input_list.insert(s, item)
elif item > pv:
input_list.remove(item)
input_list.insert(e, item)
new_pp = input_list.index(pv)
left = input_list[s:new_pp]
right = input_list[(new_pp + 1): e + 1]
left = quicksort(left, s, new_pp, pp)
right = quicksort(right, new_pp, len(right), pp)
input_list = input_list[0:s]
input_list.extend(left)
input_list.append(pv)
input_list.extend(right)
return input_list
my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
print(test_quicksort(my_list, 1, 4, 1, ["The Graveyard Book", "American Gods","Coraline", "Good Omens","Neverwhere"]))
print(test_quicksort(["Rory", "Lorelai", "Luke", "Lane"], 1, 3, 1, ["Rory", "Lane", "Lorelai", "Luke"]))
#True
#True
Version of partition() and quicksort() separated:
def test_quicksort(input_list, s, e, expected):
result = quicksort(input_list, s, e)
if result == expected:
return True
else:
return False
# partition algorithm
def partition(input_list, s, e, pp):
pv = input_list[pp]
for item in input_list[s:(e +1)]:
if item == pv:
pass
elif item < pv:
input_list.remove(item)
input_list.insert(s, item)
elif item > pv:
input_list.remove(item)
input_list.insert(e, item)
new_pp = input_list.index(pv)
return new_pp, input_list
# quicksort algorithm
def quicksort(input_list, s, e):
left_behind = input_list[0:s]
len_input_list = len(input_list)
if len_input_list <= 2: # base case: list with only 2 items
input_list = sorted(input_list) # make sure the two items are in order
return input_list
else: # recursive step
pp = s
pv = input_list[pp]
new_pp = input_list.index(pv)
partition_tuple = partition(input_list, s, e, pp)
new_pp = partition_tuple[0]
input_list = partition_tuple[1]
left = input_list[s:new_pp]
right = input_list[(new_pp + 1): e + 1]
left = quicksort(left, s, new_pp)
right = quicksort(right, new_pp, len(right))
input_list = left_behind
input_list.extend(left)
input_list.append(pv)
input_list.extend(right)
return input_list
my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
print(test_quicksort(my_list, 1, 4, ["The Graveyard Book", "American Gods","Coraline", "Good Omens","Neverwhere"]))
print(test_quicksort(["Rory", "Lorelai", "Luke", "Lane"], 1, 3, ["Rory", "Lane", "Lorelai", "Luke"]))
#True
#True
Hi guys,
(As in the previous exercise)
That has been the most interesting discussion we had so far in the entire course. I really thank you for all you effort in solving it, providing an incredible number of different perspectives and angles to look at this problem. It has been great.
Here my solution to the problem - I hope you can find it clear but I'm happy to discuss it in the next lecture. The source code is available online as usual.
from partition import partition
# Test case for the algorithm
def test_quicksort(input_list, start, end, expected):
result = quicksort(input_list, start, end)
if expected == result:
return True
else:
return False
# Code of the algorithm
def quicksort(input_list, start, end):
if start < end:
pivot_position = partition(input_list, start, end, start)
quicksort(input_list, start, pivot_position - 1)
quicksort(input_list, pivot_position + 1, end)
return input_list
# Run tests
print(test_quicksort([1], 0, 0, [1]))
print(test_quicksort([1, 2, 3, 4, 5, 6, 7], 0, 6, [1, 2, 3, 4, 5, 6, 7]))
print(test_quicksort([3, 4, 1, 2, 9, 8, 2], 0, 6, [1, 2, 2, 3, 4, 8, 9]))
print(test_quicksort(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"], 0, 4,
["American Gods", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book"]))