Lecture "Divide and conquer algorithms", exercise 3
Opened this issue · 6 comments
essepuntato commented
Implement the divide and conquer quicksort algorithm in Python – i.e. the recursive def quicksort(input_list, start, end). First, it takes a list and the positions of the first and last elements to consider as inputs. Then, it calls partition(input_list, start, end, start) (defined in the previous exercise) to partition the input list into two slices. Finally, it executes itself recursively on the two partitions (neither includes the pivot value since it has already been correctly positioned through the partition execution). In addition, define the base case of the algorithm appropriately to stop if needed before running the partition algorithm. Accompany the implementation of the function with the appropriate test cases. As supporting material, Fekete and Morr released a nonverbal definition of the algorithm [Fekete, Morr, 2018c], which is helpful to understand the rationale of the binary search steps.
delete4ever commented
Currently it only works when the element used as pivot is unique in the list...
# Test case for the algorithm
def test_quicksort(input_list, start, end, expected):
quicksort(input_list, start, end)
result = input_list
if result == expected:
return True
else:
return False
# Code for partition algorithm in 2nd exercise
def partition(input_list, start, end, pivot_position):
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)
# Code for quicksort algorithm
def quicksort(input_list, start, end):
if start <= end:
new_pivot= partition(input_list, start, end, start)
quicksort(input_list, start, new_pivot-1)
quicksort(input_list, new_pivot+1, end)
# Three test runs
print(test_quicksort([5, 4, 3, 2, 1], 0, 4, [1, 2, 3, 4, 5])) #True
print(test_quicksort([5, 4, 3, 2, 1], 1, 3, [5, 2, 3, 4, 1])) #True
print(test_quicksort([1], 0, 0, [1])) #Trueleonardozilli commented
def test_quicksort(input_list, start, end, expected_result):
result = quicksort(input_list, start, end)
return result == expected_result
def quicksort_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 pivot_new_position
else:
return None
def quicksort(input_list, start, end):
if end > start:
pivot_position = quicksort_partition(input_list, start, end, start)
quicksort(input_list, start, pivot_position - 1)
quicksort(input_list, pivot_position + 1, end)
return input_list
print(test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, ["The Graveyard Book", "American Gods", "Coraline", "Good Omens", "Neverwhere"]))
print(test_quicksort([7, 2, 1, 8, 6, 3, 5, 4], 0, 7, [1, 2, 3, 4, 5, 6, 7, 8]))
print(test_quicksort([7, 2, 1, 8, 6, 3, 5, 4], 1, 6, [7, 1, 2, 3, 5, 6, 8, 4]))
print(test_quicksort([3, 2, 4, 1, 5], 0, 4, [1, 2, 3, 4, 5]))
print(test_quicksort([5, 4, 3, 2, 1], 1, 3, [5, 2, 3, 4, 1]))
print(test_quicksort([0], 0, 0, [0]))ranacoskun commented
def test_quicksort(input_list, start, end, expected):
if expected == quicksort(input_list, start, end):
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
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
print(test_quicksort(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, ['The Graveyard Book', 'American Gods', 'Coraline', 'Good Omens', 'Neverwhere'])) # True
print(test_quicksort(["d", "e", "a", "c"], 0, 3, ['a', 'c', 'd', 'e'])) # True
print(test_quicksort([7, 6, 3, 9, 12, 1], 0, 5, [1, 3, 6, 7, 9, 12])) # True
print(test_quicksort([7, 6, 3, 9, 12, 1], 2, 4, [7, 6, 3, 9, 12, 1])) # Truen1kg0r commented
def test_quicksort(input_list, start, end, expected):
result = quicksort(input_list, start, end)
if expected == result:
return True
else:
return False
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
def quicksort(input_list, start, end):
if end > start:
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
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"]))
lucia1299 commented
def test_quicksort(input_list, start, end, expected):
result = quicksort(input_list, start, end)
return result == expected
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 += 1
input_list[j], input_list[i] = input_list[i], input_list[j]
input_list[i+1], input_list[end] = input_list[end], input_list[i+1]
return i+1
def quicksort(input_list, start, end):
if start < end:
pivot_new = partition(input_list, start, end, end)
quicksort(input_list, start, pivot_new-1)
quicksort(input_list, pivot_new+1, end)
return input_list
print(test_quicksort([0, 3, 5, 6, 2, 9, 10], 0, 6, [0, 2, 3, 5, 6, 9, 10])) #True
print(test_quicksort(['Bologna', 'Milano', 'Napoli', 'Palermo', 'Firenze', 'Venezia'], 0, 5, ['Bologna', 'Firenze', 'Milano', 'Napoli', 'Palermo', 'Venezia'])) #True
print(test_quicksort([56, 34, 901, 2, 3, 6, 345], 0, 6, [2, 3, 6, 34, 56, 345, 901])) #Truealka2696 commented
def test_quicksort(input_list, start, end, expected):
result = quicksort(input_list, start, end)
quicksort(input_list, start, end)
if input_list == 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
def quicksort(my_list, start, end):
if start >= end:
return my_list
pivot_position = end
store_index = partition(my_list, start, end, pivot_position)
quicksort(my_list, start, store_index-1)
quicksort(my_list, store_index+1, end)
return my_list
print(test_quicksort([5, 4, 3, 2, 1], 0, 4,[1, 2, 3, 4, 5])) #True
print(test_quicksort([1, 2, 3, 4, 5, 6, 7], 0, 6, [1, 2, 3, 4, 5, 6, 7])) #True