Lecture "Divide and conquer algorithms", exercise 3

[essepuntato]

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 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 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.

[arcangelo7]

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

[sntcristian]

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

[FrancescoFernicola]

def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    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)

def quicksort(input_list, start, end):
    pivot = partition(input_list, start, end, start)
    if len(input_list[start:pivot]) > 1:
        quicksort(input_list, start, pivot-1)
    if len(input_list[pivot:end]) > 1:
        quicksort(input_list, pivot+1, end)
    return input_list

num_list = [128, 2, 32, 4, 8, 64, 16]
print(test_quicksort(num_list, 0, 6, [2, 4, 8, 16, 32, 64, 128]))
FF_list = [ "Terra", "Vivi", "Cid", "Auron", "Sephirot", "Kefka", "Zidane", "Squall"]
print(test_quicksort(FF_list, 0, 7, ["Auron", "Cid", "Kefka", "Sephirot", "Squall", "Terra", "Vivi", "Zidane"]))

[essepuntato]

Hi all,

please find attached my personal solution – also available online:

# Test case for the function
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 function
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"]))