Lecture "Divide and conquer algorithms", exercise 2

[essepuntato]

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.

[RebeccaJillianBeattie]

I suspect there is a more efficient and less messy way to do this! (the 2 else blocks were basically trying to deal with the case of there being more than one instance of the same element in the input list)

[Postitisnt]

For simplicity, I've defined two additional functions to make the partition function more clean. The exchange function has the purpose of changing the position of two elements within a list.

def exchange(listToChange, pos1, pos2):
    temp = listToChange[pos1]
    listToChange[pos1] = listToChange[pos2]
    listToChange[pos2] = temp
    return listToChange

The killDuplicates function is useful to remove any duplicate from an input list.

def killDuplicates(listToClean):
    listOfPositions = []
    for el1 in range(len(listToClean)):
        for el2 in range(len(listToClean)):
            if el1 != el2 and listToClean[el1] == listToClean[el2] and el1 not in listOfPositions:
                listOfPositions.append(el2)
    listOfPositions.sort()
    listOfPositions.reverse()
    for posToRemove in listOfPositions:        
        listToClean.pop(posToRemove)

Here the partition algorithm.

def partition(myList, start, end, pivot_position):
    if myList[pivot_position] not in myList[start:end+1]:
        return None
    else:
        killDuplicates(myList)
        i = start
        pivIndex = start
        exchange(myList, pivot_position, end)  
        while i <= end:
            if i == end:
                exchange(myList, pivIndex, end)
                i += 1
            elif myList[i] < myList[end]:
                exchange(myList, i, pivIndex)  
                pivIndex += 1
                i += 1
            else: 
                i += 1
        return pivIndex

def test (inputList, start, end, pivotPos, expectedPivPos):
    if partition(inputList, start, end, pivotPos) == expectedPivPos:
        return True
    else:
        return False

In these examples, must be considered the fact that I'm looking at the lists as if there are no duplicates: in fact I take a list without any duplicate as input.

testList1 = ["The Graveyard Book", "Coraline", "Coraline", "Neverwhere", "The Graveyard Book", "Good Omens", "Coraline", "American Gods"]
testList1Bis = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
testList2 = [3, 5, 5, 7, 4, 2, 9, 6, 1, 8]
testList2Bis = [3, 5, 7, 4, 2, 9, 9, 1, 9, 6, 1, 8]
testList3 = ["a", "c", "e", "d", "b"]
testList3Bis = ["a", "c", "e", "d", "b"]

print("test 1:", test(testList1, 1, 4, 1, 2))
print("test 2:", test(testList1Bis, 1, 4, 4, 1))
print("test 3:", test(testList2, 0, 8, 2, 6))
print("test 4:", test(testList2Bis, 3, 7, 3, 5))
print("test 5:", test(testList3, 0, 0, 0, 0))
print("test 6:", test(testList3Bis, 1, 4, 0, None))

[Sebastiano-G]

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_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)    

print(test_partition(["ciao", "vanto", "cantare", "sorpresa", "chiavistello"], 0, 4, 2, 0))
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))
print(test_partition(["key", "value", "case", "python", "function", "boolean"], 2, 4, 3, 4))

[MaddaGh]

I understood the process in Ang's video but I was stuck at the end of the function since the pivot position shifted in the list if it was not at the end. Here is a flowchart I made:

I couldn't find out a way to "save" the value separated from the initial pivot position in order to re-insert it at the new pivot position later, so I came up with a more mechanical solution:

def test_partition(input_list, start, end, pivot_position, expected_pivot):
    result = partition(input_list, start, end, pivot_position)
    if expected_pivot == result:
        return True
    else: 
        return False

def partition(input_list, start, end, pivot_position):
    left_list=[]
    right_list=[]    
    final_list=[]
    pivot_item=input_list[pivot_position]
    for item in input_list[start:pivot_position]:
        if item<=pivot_item:
            left_list.append(item)
        else:
            right_list.append(item)
    for item in input_list[pivot_position+1:end+1]:
        if item<= pivot_item:
            left_list.append(item)
        else:
            right_list.append(item)
    final_list.extend(input_list[0:start])
    final_list.extend(left_list)
    final_list.extend(right_list)
    final_list.extend(input_list[end+1:len(input_list)])
    pivot_value_new_position = len(input_list[0:start])+len(left_list)
    final_list.insert(pivot_value_new_position, pivot_item)

    print(final_list)
    print(pivot_value_new_position)
    return pivot_value_new_position

print(test_partition(["The Handmaiden", "Oldboy", "Lady Vengeance", "Snowpiercer", "Stoker", "Sympathy for Mr. Vengeance", "Boy goes to heaven"], 3, 6, 3, 4))           
print(test_partition([7, 2, 8, 5, 12, 6, 1, 4, 0, 3, 9, 32, 15], 1, 10, 5, 7))   
print(test_partition(["americano", "long island", "gin tonic", "bellini", "moscow, mule", "dry martini", "mojito"], 1, 5, 3, 1))
print(test_partition(["Bigelow", "Zhao", "Sciamma", "Gerwig", "Ducournau", "Rohrwacher", "Coppola", "Campion", "Akerman", "Cavani"], 2, 7, 5, 6))

[federicabonifazi]

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

test_1=[0, 1, 2, 3, 4, 5, 6, 7]
test_2=["mela", "kiwi", "ciliegia", "cocco", "arancia", "albicocca"]
test_3=["a", "b", "h", "c", "g", "d", "e", "a"]
test_4=["a", "h", "c", "g", "d", "d", "e", "a"]

def partition(input_list, start, end, pivot_position):
    pivot_item=input_list[pivot_position]
    output_list=[]
    if not start<pivot_position<end:
        return "pivot_position must be a value between start and end. Try again!"
    else:
        right_list=[]
        left_list=[]
        for item in input_list[:start]:
            left_list.append(item)
        for item in input_list[start:end+1]:
            if item==pivot_item:
                right_list.insert(0, item)
            elif item>pivot_item:
                right_list.append(item)
            else:
                left_list.append(item)
        for item in input_list[end+1:len(input_list)]:
            right_list.append(item)
        input_list.clear()
        input_list.extend(left_list)
        input_list.extend(right_list)
    return(input_list.index(pivot_item))

print(test_partition(test_1, 2, 5, 3, 3))
print(test_partition(test_2, 1, 4, 2, 2))
print(test_partition(test_3, 3, 5, 2, "pivot_position must be a value between start and end. Try again!"))
print(test_partition(test_4, 2, 6, 3, 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):
    for item in input_list[start:pivot_position]: 
        if item > input_list[pivot_position]:
            input_list.insert(pivot_position+1, item)
            input_list.remove(item)
            position = pivot_position-1
            pivot_position = position
    for item in input_list[pivot_position:end+1]:
        if item < input_list[pivot_position]:
            input_list.insert(pivot_position-1, item)
            input_list.remove(item)
            position = pivot_position+1
            pivot_position = position
        return pivot_position

print(test_partition([1, 5, 20, 8, 15, 10, 19, 16, 18, 6], 2, 7, 5, 3))
print(test_partition([1, 5, 20, 8, 9, 10, 19, 16, 18, 6], 3, 6, 4, 4))

[angstigone]

[olgagolgan]

[AmeliaLamargese]

def test_partition(input_list, start, end, pivot_position, expected):
    pivot_value = input_list[pivot_position]
    result = partition(input_list, start, end, pivot_position)
    output = result == expected and pivot_value == input_list[result]

    for item in input_list[start:result]:
        output = output and item <= pivot_value
    for item in input_list[result:end+1]:
        output = output and item >= pivot_value    

    return output

def partition (input_list, start, end, pivot_position):
    pivot_value = input_list[pivot_position]
    swap_index = start - 1

    for item in range[start:end+1]:
        if input_list[item] < pivot_value:
            swap_index += 1
            if swap_index == pivot_position:
                pivot_position = item
                swap(input_list, swap_index, pivot_position)    

    new_pivot_position = swap_index +1
    swap(input_list, pivot_position, new_pivot_position)

    return new_pivot_position

def swap(input_list, old_index, new_index):
    temporary_var = input_list[old_index]
    input_list[old_index] = input_list[new_index]
    input_list[new_index] = temporary_var                

print(test_partition([5, 9, 4, 3, 7, 0, 2], 0, 6, 3, 2))
print(test_partition([5, 9, 4, 3, 7, 0, 2], 2, 5, 3, 3)) 

[CarmenSantaniello]

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):
    start_list = input_list[0:start]
    end_list = input_list[end + 1:len(input_list)]
    left_list = input_list[start:pivot_position]
    right_list = input_list[pivot_position + 1:end + 1]
    pivot = input_list[pivot_position]
    right_add = list()
    left_add = list()
    for el in left_list:
        if el > pivot:
            right_add.append(el)
        else:
            start_list.append(el)
    end_add = 0
    for el in right_list:
        if el <= pivot:
            left_add.append(el)
        else:
            end_list.insert(end_add, el)  
            end_add += 1

    input_list.clear()
    input_list.extend(start_list)
    input_list.extend(left_add)
    pivot_position = len(input_list)
    input_list.append(pivot)
    input_list.extend(right_add)
    input_list.extend(end_list)
    return pivot_position

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

[ManueleVeggi]

Following the instructions given during the last lessons, I wrote a new version of the code. I think that there seem to be four main cases: 1) Base case 2) Pivot coincides with start 3) Pivot coincides with end 4) More than one occurrence of pivot 5) Start greater than the end: this is the sole case, in which partition should return False

The output of this test cases is always True. I hope it is correct.

Here is the script:

def test_part(input_list, start, end, pivot_position, expected):
    result = partition(input_list, start, end, pivot_position)
    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)
            else:
                None   
        input_list = swap(input_list, i+1, end)
        return input_list.index(pivot_value)
    else:
        return False

my_list1 = [7, 2, 1, 8, 6, 3, 5, 4]
my_list2 = [7, 2, 1, 8, 6, 3, 5, 4]
my_list3 = [7, 2, 1, 8, 6, 3, 5, 4]
my_list4 = [7, 2, 1, 3, 6, 3, 5, 4]
my_list5 = [7, 2, 1, 3, 6, 3, 5, 4]
print(test_part(my_list1, 1, 6, 4, 5))
print(test_part(my_list2, 1, 6, 1, 2))
print(test_part(my_list3, 1, 6, 6, 4))
print(test_part(my_list4, 1, 6, 5, 3))
print(test_part(my_list4, 6, 1, 5, False))      

[teragramgius]

PREMISE

At first, I thought about using the .extend method to have a brand new list (i.e. the straight copy of the input list) to run the function. Indeed, according to the function, the output_list will always have the same lenght of the input_list.

Then I thought that, effectively, a list is not a set, so it could have been possible that more items could have had the same value.

BACK TO THE ISSUE

I see the partition like a recipe. The ingredients I used to make this recipe are:

1. i variable
2. every time the computer reads a value less then the pivot, I first increased the i position by 1 and then I swapped the element to the i position.
3. Another important thing to say is that, following Ang example, the first operation to do is to swap the pivot to the last position available in the list (or in the sublist, since the issue #29 presents an example of this kind).

This issue is about having the elements less than the pivot on the left side of the list and the element greater than the pivot on the right side of the list. This means that I don't care if the items in the list are not sorted at all.

The discovery of this issue is in the fact that actually, I don't need just to be sure that the pivot is in the right position, but also that the swap action can take place in the algorithm. So I should create a swap function: it takes as input the input_list, the old index and the new index. Calling this function allows me to facilitate the partition process.

I attach the algorithms: professor Peroni's version and Ang's version.

`
#Professor Peroni's version
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):
    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

print(partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7, 6))

print(test_partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7, 6, 3))

`

#Ang version
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_index = pivot_position
 pivot = input_list[pivot_index]
 i_index = start - 1

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

 new_pivot_position = i_index + 1

 return new_pivot_position

print(test_partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7, 6, 3))
print(partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7, 6))