Lecture "Divide and conquer algorithms", exercise 2
Opened this issue · 8 comments
essepuntato commented
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 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 – note: pivot_position must be a value between start and end (included). 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 that is useful to understand the rationale of the partition steps.
delete4ever commented
It's not beautiful enough and works strangely I think I should try again.
# Test case for the algorithm
def test_partition(input_list, start, end, pivot_position, expected):
result= partition(input_list, start, end, pivot_position)
if expected == result:
return True
else:
return False
# Code for the algorithm
def partition(input_list, start, end, pivot_position):
if len(input_list) <= 1:
return 0
else:
left_list= list()
right_list= list()
wanted_list= input_list[start:(end+1)]
if pivot_position >= start:
for i in wanted_list:
if i < input_list[pivot_position]:
left_list.append(i)
if i > (input_list[pivot_position]):
right_list.append(i)
input_list[:] = list(input_list[0:start] + left_list + [input_list[pivot_position]] + right_list + input_list[end+1:len(input_list)])
return len(input_list[0:start]) + len(left_list)
# Three test runs
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2)) #True
print(test_partition([3, 2, 4, 1, 5], 0, 4, 3, 0)) #True
print(test_partition([0], 0, 0, 0, 0)) #Trueleonardozilli commented
def partition(input_list, start, end, pivot_position):
pivot_item = input_list[pivot_position]
i = start - 1
if pivot_position >= start and pivot_position <= end:
for item in input_list[start:end + 1]:
if item < input_list[pivot_position]:
i += 1
if pivot_position == i:
pivot_position = input_list.index(item)
input_list[input_list.index(item)], input_list[i] = input_list[i], input_list[input_list.index(item)]
input_list.insert(i + 1, input_list[pivot_position])
input_list.pop(pivot_position + 1)
pivot_new_position = input_list.index(pivot_item)
return input_list, pivot_new_position
else:
return None
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, (["The Graveyard Book", "American Gods", "Coraline", "Neverwhere", "Good Omens"], 2)))
print(test_partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7, 7, ([2, 1, 3, 4, 8, 6, 7, 5], 3)))
print(test_partition([7, 2, 1, 8, 6, 3, 5, 4], 1, 6, 7, None))
print(test_partition([3, 2, 4, 1, 5], 0, 4, 3, ([1, 3, 2, 4, 5], 0)))
print(test_partition([0], 0, 0, 0, ([0], 0)))ranacoskun commented
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
for position in range(start, end + 1):
if input_list[position] < input_list[pivot_position]:
i = i + 1
if i == pivot_position:
pivot_position = position
temp = input_list[position]
input_list[position] = input_list[i]
input_list[i] = temp
temp = input_list[pivot_position]
input_list[pivot_position] = input_list[i + 1]
input_list[i + 1] = temp
return i + 1
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2)) # True
print(test_partition(["d", "e", "a", "c"], 0, 3, 3, 1)) # True
print(test_partition([7, 6, 3, 9, 12, 1], 0, 5, 5, 0)) # True
print(test_partition([7, 6, 3, 9, 12, 1], 2, 5, 4, 5)) # TrueEricaAndreose commented
Solution
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):
i = start - 1
for j in range(start, end+1):
if input_list[j] < input_list[pivot_position]:
i = i+1
temp=input_list[j]
input_list[j]=input_list[i]
input_list[i]=temp
return i+1
print(test_partition(["a", "c", "b", "f"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 3, 3))
print(test_partition(["a", "c", "b", "f"], 0, 2, 1, 2))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 1, 4, 1, 1))
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 0, 4, 3, 4)) Second try
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: list, start, end, pivot_position):
i= start-1
item_pivot=input_list[pivot_position]
for item in input_list[start:end+1]:
if item < item_pivot:
i = i+1
input_list.remove(item)
input_list.append(item)
item == item_pivot
pivot_position = i+1
return pivot_position
print(test_partition(["a", "c", "b", "f"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 3, 3))
print(test_partition(["a", "c", "b", "f"], 0, 2, 1, 2))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 1, 4, 1, 1))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 0, 4, 3, 4)) First try
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: list, start, end, pivot_position):
i= start-1
item_pivot=input_list[pivot_position]
left_list = list()
right_list = list()
for item in input_list[start:end+1]:
if item > item_pivot:
right_list.append(item)
elif item < item_pivot:
left_list.append(item)
i = i+1
pivot_position = i+1
left_list + [pivot_position] + right_list
return pivot_position
print(test_partition(["1", "3", "2", "7"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 2, 1))
print(test_partition(["1", "3", "2", "7"], 1, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 3, 3))
print(test_partition(["a", "c", "b", "f"], 0, 2, 1, 2))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 1, 4, 1, 1))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 0, 4, 3, 4))
print(test_partition(["mela", "banana", "pera", "uva", "arancia"], 2, 4, 4, 2))
print(test_partition(["1", "3", "2", "7"], 0, 3, 2, 1))
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))
print(test_partition(["d", "e", "a", "c"], 0, 3, 3, 1))
lucia1299 commented
Solution
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
return result == expected
def partition(input_list, start, end, pivot_position):
i = start-1
for j in range(len(input_list)-1):
if input_list[j] < input_list[pivot_position]:
i += 1
input_list[j], input_list[i] = input_list[i], input_list[j]
return i+1
print(test_partition([0, 3, 5, 6, 2, 9, 10], 0, 6, 2, 3)) #True
print(test_partition(["Bologna", "Milano", "Napoli", "Parlemo", "Firenze", "Venezia"], 0, 5, 3, 4)) #True
print(test_partition([56, 34, 901, 2, 3, 6, 345], 0, 6, 4, 1)) #TruePrevious solution
def test_partition(input_list, start, end, pivot_position, expected):
result = partition(input_list, start, end, pivot_position)
return result == expected
def partition(input_list, start, end, pivot_position):
left_list = list()
right_list = list()
pivot_item = input_list[pivot_position]
for item in input_list[start:]:
if item < input_list[pivot_position]:
left_list.append(item)
elif item > input_list[pivot_position]:
right_list.append(item)
elif item == input_list[pivot_position]:
right_list.append(pivot_item)
pivot_item = right_list[0]
new_list = list(left_list + right_list)
return new_list.index(pivot_item)
print(test_partition([0, 3, 5, 6, 2, 9, 10], 0, 6, 2, 3)) #True
print(test_partition(["Bologna", "Milano", "Napoli", "Palermo", "Firenze", "Venezia"], 0, 5, 3, 4)) #True
print(test_partition([56, 34, 901, 2, 3, 6, 345], 0, 6, 4, 1)) #Truen1kg0r commented
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
def partition(input_list, start, end, pivot_position):
i = start - 1
t = input_list[pivot_position]
input_list[pivot_position] = input_list[end]
input_list[end] = t
for j in range(start, end):
if input_list[j] < input_list[end]:
i += 1
t = input_list[i]
input_list[i] = input_list[j]
input_list[j] = t
t = input_list[i+1]
input_list[i+1] = input_list[end]
input_list[end] = t
return i+1
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))
ChiaraParravicini commented
# considering the end item as pivot
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_position >= start and pivot_position <= end
i = start - 1
j = start
for j in range(len(input_list[start:end+1])):
if input_list[j] <= input_list[pivot_position]:
i += 1
temp = input_list[j]
input_list[j] = input_list[i]
input_list[i] = temp
return i
print(test_partition([4, 2, 5, 0, 9, 3], 0, 5, 5, ([2, 0, 3, 4, 9, 5], 2)))
print(test_partition([0, 5, 7, 1, 2], 0, 3, 3, ([0, 1, 7, 5, 2], 1)))
print(test_partition(["c", "a", "b", "d", "b"], 0, 4, 4, (["a", "b", "b", "d", "c"], 2)))
print(test_partition([''], 0, 0, 0, ([''], 0)))alka2696 commented
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(my_list, start, end, pivot_position):
pivot_value = my_list[pivot_position]
store_index = start
for i in range(start, end+1):
if my_list[i] < pivot_value:
my_list[store_index], my_list[i] = my_list[i], my_list[store_index]
store_index += 1
my_list[store_index], my_list[pivot_position] = my_list[pivot_position], my_list[store_index]
return store_index
print(test_partition(["Alka","Prabha","Neelam","Madan"],0,3,3,1)) #True
print(test_partition(["a","e","j","i","d"],1,4,3,3)) #True