-
Notifications
You must be signed in to change notification settings - Fork 3
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Lecture "Divide and conquer algorithms", exercise 3 #29
Labels
Comments
def test_quicksort(input_list, start, end, expected):
if quicksort(input_list, start, end) == expected:
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
def quicksort(input_list, start, end):
if start < end: # It means: if there is more than one item to be sorted
middle_position = (start + end) // 2
pivot_position = partition(input_list, start, end, middle_position) # The pivot position could be the end, the start, the middle, I think that it doesn't matter
quicksort(input_list, start, pivot_position - 1) # For all the items left to the pivot, call quicksort recursively
quicksort(input_list, pivot_position + 1, end) # For all the items right to the pivot, call quicksort recursively
return input_list
numbers_list = [0, 9, 5, 6, 7, 3, 2, 4, 8, 1]
print(test_quicksort(numbers_list, 0, 9, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))# True
books_list = ["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]
print(test_quicksort(books_list, 0, 4, ["American Gods", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book"])) # True
print(test_quicksort(["l"], 0, 0, ["l"])) # True |
from partition import partition
# Import the function 'partition' from the module 'partition' (file 'partition.py')
def test_quicksort(input_list, start, end, expected):
result = quicksort(input_list, start, end)
if expected == result:
return True
else:
return False
def quicksort(input_list, start, end):
pivot_pos = partition(input_list, start, end, start)
if len(input_list[start:pivot_pos]) > 1:
#while there's still an item to order at the left of the pivot_position
quicksort(input_list, start, pivot_pos-1)
if len(input_list[pivot_pos:end]) > 1:
#while there's still an item to order at the right of the pivot_position
quicksort(input_list, pivot_pos+1, end)
return input_list
print(test_quicksort(["l"], 0, 0, ["l"])) # True
print(test_quicksort([1], 0, 0, [1])) #True
print(test_quicksort([3, 4, 1, 2, 9, 8, 2], 0, 6, [1, 2, 2, 3, 4, 8, 9])) #True
print(test_quicksort(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"], 0, 4,
["American Gods", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book"])) #True |
|
Hi all, please find attached my personal solution – also available online:
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Implement in Python the divide and conquer quicksort algorithm – i.e. the recursive
def quicksort(input_list, start, end)
. It takes a list and the positions of the first and last elements in the list to consider as inputs. Then, it callspartition(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 of which includes the pivot value since it has been already correctly positioned through the execution of partition). In addition, define the base case of the algorithm appropriately to stop if needed before to run 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 which is useful to understand the rationale of the binary search steps.The text was updated successfully, but these errors were encountered: