Lecture "Divide and conquer algorithms", exercise 2
essepuntato opened this issue · 7 comments
Implement in Python the partition algorithm – i.e. the non-recursive function def partition(input_list, start, end, pivot_position). It takes a list and the positions of the first and last elements in the list to consider as inputs. It redistributes all the elements of a list having position included between start and end on the right of the pivot value input_list[pivot_position] if they are greater than it, and on its left otherwise. Also, the algorithm returns the new position where the pivot value is now stored. For instance, considering my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]), the execution of partition(my_list, 1, 4, 1) changes my_list as follows: list(["The Graveyard Book", "American Gods", "Coraline", "Neverwhere", "Good Omens"]) and 2 will be returned (i.e. the new position of "Coraline"). Note that "The Graveyard Book" has not changed its position in the previous execution since it was not included between the specified start and end positions (i.e. 1 and 4 respectively). Accompany the implementation of the function with the appropriate test cases. As supporting material, Ang recorded a video which is useful to understand the rationale of the partition steps.
The algorithm should work, but it is not a divide and conquer algorithm. The delivery says it doesn't have to be a recursive algorithm. So maybe that's okay. Anyway, if someone can improve it I would be very grateful. Let's say that it's a temporary solution.
def test_partition(input_list, start, end, pivot_position, expected):
if expected == partition(input_list, start, end, pivot_position):
return True
else:
return False
def partition(input_list, start, end, pivot_position):
divided_list = input_list[start:end+1]
pivot_value = input_list[pivot_position]
for item in divided_list:
if item < pivot_value:
input_list.remove(item)
input_list.insert(start, item)
elif item > pivot_value:
input_list.remove(item)
input_list.insert(end, item)
new_pivot_position = input_list.index(pivot_value)
return new_pivot_position
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 4, 1, 1)) # True
# The algorithm messes up the list every time, so I instantiate it again each time
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 1, 4, 1, 2)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 0, 1, 1)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 5, 5, 1, 1)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 2, 4, 4, 2)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 3, 0, 3)) # TrueThis is instead the solution by Ang sensei, the video teacher, which is still not a divide and conquer algorithm. Any suggestions?
def test_partition(input_list, start, end, pivot_position, expected):
if expected == partition(input_list, start, end, pivot_position):
return True
else:
return False
def partition(input_list, start, end, pivot_position):
i = start - 1
pivot_item = input_list[pivot_position]
for item in input_list[start:end+1]:
if item < pivot_item:
i += 1
current_element = item
input_list[input_list.index(item)] = input_list[i]
input_list[i] = current_element
input_list.remove(pivot_item)
input_list.insert(i + 1, pivot_item)
return i + 1
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 4, 1, 1)) # True
# The algorithm messes up the list every time, so I instantiate it again each time
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 1, 4, 1, 2)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 2, 4, 4, 2)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 3, 0, 3)) # TrueReading the third issue I realized that this is probably the ancillary algorithm for that one. So I don't think this should be a divide and conquer algorithm.
def test_partition(input_list, start, end, pivot_position, expected):
if expected == partition(input_list, start, end, pivot_position):
return True
else:
return False
def partition(input_list, start, end, pivot_position):
pivot = input_list[pivot_position]
for position, item in enumerate(input_list):
if start <= position and end >= position:
if item > pivot:
input_list.insert(pivot_position + 1, input_list.pop(position))
elif item < pivot:
input_list.insert(pivot_position, input_list.pop(position))
pivot_position = input_list.index(pivot)
return pivot_position
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 4, 0, 4)) #TrueThis one is my solution:
This is the solution reached following the video's suggestions:
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
if result == expected:
return True
else:
return False
def partition(input_list, start, end, pivot_position):
pivot = input_list[pivot_position]
partitioned_list = input_list[start:end+1]
i = start - 1
for j in partitioned_list:
if j < pivot:
j_index = input_list.index(j)
i += 1
input_list[j_index], input_list[i] = input_list[i], input_list[j_index]
input_list.remove(pivot)
input_list.insert((i+1), pivot)
return input_list.index(pivot)
num_list = [2, 4, 42, 20, 16]
print(test_partition(num_list, 1, 4, 4, 2))
num_list = [2, 4, 42, 20, 16]
print(test_partition(num_list, 0, 4, 2, 4))
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 1, 4, 1, 2))
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 2, 4, 0, 4))
FF_list = [ "Terra", "Vivi", "Cid", "Auron", "Sephirot", "Kefka", "Zidane", "Squall"]
print(test_partition(FF_list, 2, 6, 4, 5))
Hi all,
please find attached my personal solution – also available online:
# Test case for the function
def test_partition(input_list, start, end, pivot_position, expected):
p_value = input_list[pivot_position]
result = partition(input_list, start, end, pivot_position)
output = expected == result and p_value == input_list[result]
for item in input_list[0:result]:
output = output and item <= p_value
for item in input_list[result + 1:len(input_list)]:
output = output and item >= p_value
return output
# Code of the function
def partition(input_list, start, end, pivot_position):
pivot_value = input_list[pivot_position]
swap_index = start - 1
for index in range(start, end + 1):
if input_list[index] < pivot_value:
swap_index += 1
if swap_index == pivot_position:
pivot_position = index
swap(input_list, swap_index, index)
new_pivot_position = swap_index + 1
swap(input_list, pivot_position, new_pivot_position)
return new_pivot_position
def swap(input_list, old_index, new_index):
cur_value = input_list[old_index]
input_list[old_index] = input_list[new_index]
input_list[new_index] = cur_value
# Run tests
print(test_partition([1, 2, 3, 4, 5], 0, 4, 0, 0))
print(test_partition([4, 5, 3, 1, 7], 0, 4, 0, 2))
print(test_partition([4, 5, 3, 1, 7], 0, 4, 2, 1))
print(test_partition([7, 5, 3, 1, 4], 0, 4, 4, 2))
print(test_partition([1, 9, 7, 5, 9, 3, 1, 4, 2, 3], 0, 9, 1, 8))
print(test_partition([1, 9, 7, 5, 9, 3, 1, 4, 2, 3], 0, 9, 0, 0))
print(test_partition([1, 9, 7, 5, 9, 3, 1, 4, 2, 3], 0, 9, 3, 6))
print(test_partition([1, 2, 2, 3, 9, 8, 4], 1, 2, 1, 1))