Lecture "Divide and conquer algorithms", exercise 3

[essepuntato]

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.

[RebeccaJillianBeattie]

[Sebastiano-G]

The code is longer than expected, but it seems to work properly.

def test(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_value = input_list[pivot_position]
    right_list= []
    left_list= []
    rest_list1=[]
    rest_list2= []
    for el in input_list[start:end+1]:
        if el > pivot_value:
            right_list.append(el)
        elif el < pivot_value:
            left_list.append(el)
        else: 
            right_list.insert(0, pivot_value)
    for el in input_list[0:start]:
        rest_list1.insert(-1, el)
    for el in input_list[end+1: len(input_list)]:
        rest_list2.append(el)
    updated_list = rest_list1+left_list+right_list+rest_list2
    return updated_list.index(pivot_value) 

def quicksort(input_list, start, end):
    rest_list1=input_list[0:start]
    rest_list2=input_list[end+1:len(input_list)]
    if len(input_list)<=1:
        return input_list
    else:
        pivot_index = partition(input_list, start, end, start)
        temporary_pivot_index = pivot_index +1
        input_list.insert(temporary_pivot_index, input_list[start])
        input_list.remove(input_list[start])
        pivot_value = input_list[pivot_index]
        pivot_list = [pivot_value]
        quicksort_left_list = input_list[start:pivot_index]
        quicksort_right_list= input_list[pivot_index+1:end+1]
        for el in quicksort_left_list:
            if el > pivot_value:
                    quicksort_right_list.append(el)
        for el in quicksort_right_list:
            if el in quicksort_left_list:
                quicksort_left_list.remove(el)
        for el in quicksort_right_list:
            if el < pivot_value:
                quicksort_left_list.append(el)
        for el in quicksort_left_list:
            if el in quicksort_right_list:
                quicksort_right_list.remove(el)
        if len(quicksort_right_list) ==2:
            if quicksort_right_list[0] < quicksort_right_list[1]:
                quicksort_right_list = quicksort_right_list
            else:
                quicksort_right_list = [quicksort_right_list[1], quicksort_right_list[0]]
        else: 
            quicksort_right_list = quicksort(quicksort_right_list, 0, (len(quicksort_right_list)-1))
        if len(quicksort_left_list) ==2:
            if quicksort_left_list[0]<quicksort_left_list[1]:
                quicksort_left_list = quicksort_left_list 
            else:
                quicksort_left_list = [quicksort_left_list[1], quicksort_left_list[0]]
        else: 
            quicksort_left_list = quicksort(quicksort_left_list, 0, (len(quicksort_left_list)-1))
        return rest_list1+quicksort_left_list+pivot_list+quicksort_right_list+rest_list2

print(test(["Rice", "Chickpeas", "Pulses", "Bread", "Meat","Milk", "Bacon", "Eggs", "Rice Cooker", "Sauce","Chicken Pie", "Apple Pie", "Pudding"],0,12, ['Apple Pie', 'Bacon', 'Bread', 'Chicken Pie', 'Chickpeas', 'Eggs', 'Meat', 'Milk', 'Pudding', 'Pulses', 'Rice', 'Rice Cooker', 'Sauce']))
print(test(["Recovery", "The Eminem Show", "Relapse", "Curtains Call", "The Real Slim Shady", "Lose yourself", "Not Afraid", "Love The Way You Lie", "Venom", "Rap God", "When I'm Gone", "Beautiful"], 0, 9, ['Curtains Call', 'Lose yourself', 'Love The Way You Lie', 'Not Afraid', 'Rap God', 'Recovery', 'Relapse', 'The Eminem Show', 'The Real Slim Shady', 'Venom', "When I'm Gone", 'Beautiful']))
print(test(["S", "V", "Z", "O", "A", "B", "C", "H", "N", "Q", "E", "D"], 2, 11, ["S", "V", "A", "B", "C", "D", "E", "H", "N", "O", "Q", "Z"]))

[angstigone]

[AmeliaLamargese]

def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    if result == expected:
        return True
    else:
        return False

def quicksort(input_list, start, end):
    if start < end:
        pivot = partition(input_list, start, end, start)
        quicksort(input_list, start, pivot-1)
        quicksort(input_list, pivot+1, end)

    return input_list              

print(test_quicksort([2, 5, 0, 3, 6], 0, 4, [0, 2, 3, 5, 6]))
print(test_quicksort([2, 5, 0, 3, 6], 4, 0, [2, 5, 0, 3, 6]))
print(test_quicksort([2, 5, 0, 3, 6], 1, 4, [2, 0, 3, 5, 6]))

[Bianca-LM]

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
    j = start
    input_list[pivot_position], input_list[end] = input_list[end], input_list[pivot_position]
    pivot_position = end
    for item in input_list[start:end]: 
        if item > input_list[pivot_position]: 
            j += 1
        if item < input_list[pivot_position]: 
            i += 1
            input_list[i], input_list[j] = input_list[j], input_list[i]
            j += 1
    input_list[pivot_position], input_list[i+1] = input_list[i+1], input_list[pivot_position]
    pivot_position = i+1
    return pivot_position

def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end) 
    if result == expected: 
        return True
    else: 
        return False 

def quicksort(input_list, start, end): 
    if len(input_list) > 1:
        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
    else: 
        return input_list

print(test_quicksort([1, 5, 20, 8, 15, 10, 19, 16, 18, 6], 0, 9, [1, 5, 6, 8, 10, 15, 16, 18, 19, 20]))
print(test_quicksort([], 2, 5, []))
print(test_quicksort([1,5,8,20], 0, 3, [1,5,8,20]))
print(test_quicksort(["e", "d", "c", "b", "a"], 0, 3, ["b", "c", "d","e","a"]))

[CarmenSantaniello]

def test_quicksort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    if result == expected:
        return True
    else:
        return False

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

print(test_quicksort([7,5,3,2,6,1,8,4],0,7,[1, 2, 3, 4, 5, 6, 7, 8]))
print(test_quicksort(["The Graveyard Book", "Coraline", "Coraline", "Neverwhere", "The Graveyard Book", "Good Omens", "Coraline", "American Gods"],1,7,['The Graveyard Book', 'American Gods', 'Coraline', 'Coraline', 'Coraline', 'Good Omens', 'Neverwhere', 'The Graveyard Book']))
print(quicksort([7,5,3,2,6,1,8,4],0,7))
print(quicksort(["The Graveyard Book", "Coraline", "Coraline", "Neverwhere", "The Graveyard Book", "Good Omens", "Coraline", "American Gods"],1,7))

[ManueleVeggi]

The output of the five test cases is always True: hopefully I managed to write the correct code.

Here is the script:

def test_qSort(input_list, start, end, expected):
    result = quicksort(input_list, start, end)
    if result == expected:
        return True
    else:
        return False

def swap(list, i1, i2):
    list[i1], list[i2] = list[i2], list[i1]
    return list

def partition(input_list, start, end, pivot_position):
    if start <= end:
        pivot_value = input_list[pivot_position]

        swap(input_list, pivot_position, end)
        i = start - 1
        for j in range(start, end):
            if input_list[j] <= pivot_value:
                i = i + 1
                swap(input_list, i, j) 
        input_list = swap(input_list, i+1, end)
        return input_list.index(pivot_value)
    else:
        return False

def quicksort(input_list, start, end):
    if len(input_list) == 1:
        return input_list
    elif 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
    else: 
        return False

l_case1 = [0,8,4,6,2]
l_case2 = ["Bologna", "Venezia", "Alessandria", "Firenze"]
l_case3 = [9799]
l_case4 = [1,2,3,4,5]

print(test_qSort(l_case1, 0, 4, [0,2,4,6,8]))   
print(test_qSort(l_case2, 0, 3, ["Alessandria", "Bologna", "Firenze", "Venezia"]))   
print(test_qSort(l_case3, 0, 0, [9799]))   
print(test_qSort(l_case4, 0, 4, [1,2,3,4,5]))   
print(test_qSort(l_case4, 4, 0, False))   

[essepuntato]

Just a simple note: as explained in the previous lecture, quicksort is an algorithm that modifies the input list in place, meaning that you should not create sublists from the input list but rather directly modify the input list. Try to run it with Python Tutor and see what is happening.

[teragramgius]

def partition(input_list, start, end, pivot_position):
    if not isinstance(input_list, list):
     print("please insert a list")
     return None

    pivot = input_list[pivot_position]

    i_index = start - 1
    for cup_index in range (start, end + 1):            
        if input_list[cup_index] < pivot:
            i_index += 1 
        if i_index == pivot_position:
            pivot_position == cup_index
        swap(input_list, i_index, cup_index)

    new_pivot_position = i_index + 1
    swap(input_list, pivot_position, new_pivot_position)
    return new_pivot_position

def swap(input_list, prev_index, new_index):
    stillvalue = input_list[prev_index]
    input_list[prev_index] = input_list[new_index]
    input_list[new_index] = stillvalue              #I rewrite the current position after the swap

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