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 in the list 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 which is useful to understand the rationale of the partition steps.

[diegochillo]

The partition function has to return the new pivot position and reorganize the content of input_list, so I check both objects in the test_partition function. I watched Ang's video after doing the exercise. That's why I get the result in a more naive way.

def test_partition(input_list,start,end,pivot_position,expected,expected_list):
    result=partition(input_list,start,end,pivot_position)
    return result==expected and input_list==expected_list

def partition(input_list,start,end,pivot_position):

    outbefore = list()
    outafter = list()
    before = list()
    after = list()
    newindex = 0

    pivot_e=input_list[pivot_position]
    i=0

    for i in range(len(input_list)):

        if i<start:
           outbefore.append(input_list[i])
        elif i>end:
           outafter.append(input_list[i])
        else:
            if input_list[i]<pivot_e:
               before.append(input_list[i])
            elif input_list[i]>pivot_e:
               after.append(input_list[i])

    input_list.clear()

    input_list.extend(outbefore)
    input_list.extend(before)
    input_list.append(pivot_e)
    input_list.extend(after)
    input_list.extend(outafter)

    newindex=len(outbefore)+len(before)
    #print("DEBUG newindex="+str(newindex))
    return newindex

print(test_partition (["Rick","Morty","Beth","Summer","Mr. Poopybutthole","Jerry"],1,5,3,5,["Rick","Morty","Beth","Mr. Poopybutthole","Jerry","Summer"]))
print (test_partition (["Birdperson","Mr. Meeseeks","Evil Morty","Squanchy","Gazorpazorpfield","Pickle Rick"],0,3,2,1,["Birdperson","Evil Morty","Mr. Meeseeks","Squanchy","Gazorpazorpfield","Pickle Rick"]))
print(test_partition([4,9,22,3,7,8,43,12,100,65],2,7,7,5,[4,9,3,7,8,12,22,43,100,65]))

[fcagnola]

EDIT: after reviewing the code, my original solution had two problems. Following Bruno's advice I first changed the return statement to return what the exercise actually requested: the index of the pivot (and not the list). Also, I noticed that while modifying the list in place the pivot position was changing, and I was actually comparing a static pivot position, ultimately resulting in weird outputs. I solved these problems and what follows should work:

def swap(list, old_idx, new_idx):
    tmp = list[old_idx]
    list[old_idx] = list[new_idx]
    list[new_idx] = tmp

def partition(input_list, first_elem, last_elem, pivot_position):

    idx = first_elem - 1  # counter for elements smaller than pivot
    compare = first_elem  # selects element to be compared and, in case, swapped with idx

    pivot = input_list.pop(pivot_position)
    # remove the pivot from the list, in order for it not to be moved while re-arranging the list in place

    for i in range(first_elem, last_elem):  # loops through list from start to end, but
        # the list is actually shorter since the pivot was removed through the pop() operation

        if input_list[compare] >= pivot:  # if element is >= pivot, do nothing and compare the next

            compare += 1

        elif input_list[compare] < pivot:  # if element <pivot switch places to idx and compare

            idx += 1

            swap(input_list, compare, idx)

            compare += 1

    input_list.insert(idx+1, pivot)
    # the last step before returning the index of the pivot actually re-inserting the pivot at its correct index
    # print("debug: input list {}".format(input_list))
    return idx+1

list_a = [7, 2, 1, 8, 6, 3, 5, 4]
list_b = [3, 6, 7, 9, 12, 8, 23, 15, 83, 24, 16]
list_c = [0, 17, 34, 51, 68, 0, 21, 42, 63, 84, 105, 126]
list_d = ["g", "a", "d", "e", "f", "b", "c", "h"]
print(partition(list_a, 0, 7, 6))  # returns True
print(partition(list_b, 0, 10, 7))  # returns True
print(partition(list_c, 0, 12, 8))  # returns True
print(partition(list_d, 0, 8, 3))  # returns True

[giorgiasampo]

def test_partition(input_list, start, end, pivot_position, expected):
  result = partition(input_list, start, end, pivot_position)
  return result == expected

def partition(input_list, start, end, pivot_position):
    work_list = input_list[start:end+1]
    pivot_value = input_list[pivot_position]
    left_list = list()
    right_list = list()
    right_list.append(pivot_value)
    result = input_list[:start]
    for item in work_list:
        if item < pivot_value:
            left_list.append(item)
        elif item != pivot_value:
            right_list.append(item)
    result.extend(left_list)
    result.extend(right_list)
    result.extend(input_list[end+1:])
    return result, result.index(pivot_value)

print(test_partition([0,1,2,3,4,5,6,7,8,9], 2, 5, 3,([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 3)))
print(test_partition(['b','c','e','a','z','f','o','n'], 2, 7, 6,(['b', 'c', 'e', 'a', 'f', 'o', 'n', 'z'], 5)))

[SarahTew]

In working on this problem I ran into some weird questions for @essepuntato.

1) Why doesn't my numbers example (taken directly from the KC Ang video) end up in the same exact order as the video? Even thought it is correct it is not what I expected.

2) In my code with my alphabet example, if I leave off the 'or equal to' sign in my code, it doesn't work for the last letter in my list, "b". It doesn't go in the right place. When I have the 'or equal to" sign in the code, it works fine, but there are no repeat values in the list anyway so I don't understand why it is relevant and messing with the result in this particular case.

def partition(input_list, start, end, pivot_position):
    pivot_item = input_list[pivot_position]
    i = start - 1
    j = start

    for element in range(len(input_list[start:end+1])):

        if input_list[j] >= input_list[pivot_position]:
            j = j + 1
#if you remove the "=" from the above if statement, it doesn't work. Why not? Switch it out for the if statement below to see what happens. (See example with list "alphabet")
        #if input_list[j] > input_list[pivot_position]:
        elif input_list[j] < input_list[pivot_position]:
            i += 1
            input_list [i], input_list[j] = input_list[j], input_list[i] 
            j += 1

    input_list[i+1], input_list[pivot_position] = input_list[pivot_position], input_list[i+1]
    print(input_list)
    return input_list.index(pivot_item)

numbers=[7, 2, 1, 8, 6, 3, 5, 4]
alphabet=["e","a","g", "c", "d", "f", "b"]
print(partition(numbers, 0, 7, 7))
print (partition(alphabet, 0, 6, 4))  

For numbers it prints: [2, 1, 3, 4, 6, 7, 5, 8] For alphabet it prints: ['a', 'c', 'b', 'd', 'e', 'f', 'g'] For alphabet without the 'or equal to' in the code it prints ['a', 'c', 'd', 'e', 'g', 'f', 'b']

[gabrielefiorenza]

def test_partition(input_list, start, end, pivot_position,expected):
    result = partition(input_list, start, end, pivot_position)
    return expected==result

def partition(input_list,start,end,pivot_position):
    i=start-1
    j=start
    pivot= input_list[pivot_position]
    input_list.pop(pivot_position)
    for e in range(len(input_list[start:end+1])):
        if input_list[j]>=pivot:
            j+=1
        elif input_list[j]<pivot:
            i+=1
            input_list[j], input_list[i]=input_list[i],input_list[j]
            j+=1
    input_list.insert(i + 1,pivot)
    return(i+1)

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
print(test_partition(my_list, 1, 4, 1,2))

[SarahTew]

I tried make a new partition function that worked by actually dividing the list and I came up with one that sort of works.

Instead of returning all the elements in a single list, it returns them in a series of sublists. I kind of like it better because it's easier to see what was included within the start and end range and what was outside of the range.

BUT since it is done this way, you can't get the index of the pivot since it's not actually a list of elements

The other weird thing is that even though I've put the pivot element in it's own list, it doesn't become a sublist in the final list. I don't know why this one gets added as a element to the previous list and not its own sublist. (The reason I made the pivot element into a list in the first place is because I kept getting an error about mixing lists and elements when trying to add them my final list.)

To be honest, I don't really understand why it's adding them as sublists. I have tried concatenation, .extend, .append and I can't get it just be a normal list (unless the range is the entire list to begin with) What is happening here?

def partition(input_list, start, end, pivot_position):
    smaller = []
    larger = []
    left_of_start = [input_list[:start]]
    right_of_end = [input_list[end + 1:]]
    pivot_element_list = [input_list[pivot_position]]
    pivot_element=input_list[pivot_position]
    final_list = []
    j = start
    for element in range(len(input_list[start:end+1])):
        if input_list[j] > input_list[pivot_position]:
            larger.append(input_list[j])
            j += 1
        elif input_list[j]< input_list[pivot_position]:
            smaller.append(input_list[j])
            j += 1
    if start != 0:
        final_list.extend(left_of_start)
    final_list.extend(smaller)
    final_list.extend(pivot_element_list)
    final_list.extend(larger)
    if end+1 != len(input_list):
        final_list.extend(right_of_end)
    index = final_list.index(pivot_element)
    return final_list
numbers=[7, 2, 1, 8, 6, 3, 5, 4]
print(partition(numbers, 1, 4, 3))
print(partition(numbers, 0, 7, 7))

1st print (with narrow range) will print [[7], 2, 1, 8, [3, 5, 4]] 2nd print (range includes all items in list) will print: [2, 1, 3, 4, 7, 8, 6, 5]

[vanessabonanno]

items_list = [10, 11, 13, 14, 16, 18, 19, 15, 17]
my_pivot_position = 4
my_start = 0
my_end = 8

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):
    # check if it is a valid list:
    if start > end:
        return "Wrong input list!"

    i = start - 1
    j = start
    pivot = input_list.pop(pivot_position)

    for element in items_list:
        if element > pivot:
            j += 1
        elif element < pivot:
            i += 1
            input_list[i], input_list[j] = input_list[j], input_list[i]
            j += 1
    items_list.insert(i+1, pivot)
    return items_list 

print(partition(items_list, 3, 1, my_pivot_position))             # Wrong input list!
print(partition(items_list, my_start, my_end, my_pivot_position)) # [10, 11, 13, 14, 15, 16, 19, 18, 17]

# Tests:
print(test_partition(items_list, my_start, my_end, my_pivot_position, [10, 11, 13, 1, 15, 16, 19, 18, 17])) # False
print(test_partition(items_list, my_start, my_end, my_pivot_position, [10, 11, 13, 14, 15, 16, 19, 18, 17]))# True
print(test_partition(items_list, 5, 1, my_pivot_position, "Wrong input list!"))                             # True
print(test_partition(items_list, my_start, my_end, my_pivot_position, 1.5))                                 # False

[SofiBar]

def test_partition(input_list, start, end, pivot_position, expected):
    if partition(input_list, start, end, pivot_position) == expected:
        return True

def partition(input_list, start, end, pivot_position):
    my_list = input_list[start:end]
    p = input_list[pivot_position]
    result_list = [p]
    new_pp = 0

    for item in my_list:
        if item > p:
            result_list.insert(new_pp + 1, item)
        if item < p:
            result_list.insert(new_pp, item)
            new_pp += 1
    del input_list[start:end]
    for item in reversed(result_list):
        input_list.insert(start, item)

    new_pp += start
    print(new_pp)
    return input_list

my_num_list = [8, 7, 3, 5, 2, 1, 9, 20, ]
b_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
print(test_partition(my_num_list, 1, 5, 3, [8, 3, 2, 5, 7, 1, 9, 20])) 
print(test_partition(b_list, 1, 5, 2, ["The Graveyard Book", "Coraline", "Good Omens", "American Gods", "Neverwhere"]))

[dbrembilla]

def partition(input_list, start, end, pivot_position):
    before_pivot=[]
    after_pivot=[]
    before=[]
    after=[]
    pivot = input_list[pivot_position]
    for i in input_list:
        idx=input_list.index(i)
        if idx < start:
            before_pivot.append(i)
        elif idx > end:
            after_pivot.append(i)
        else:
            if i < pivot:
                before.append(i)
            elif i > pivot:
                after.append(i)
    result = before_pivot+ before + [pivot] + after + after_pivot
    return result.index(pivot)

[AlessandraFa]

def test_partition(input_list, start, end, pivot_position, expected):
    result = partition(input_list, start, end, pivot_position)
    return result == expected

def partition(input_list, start, end, pivot_position):
    list_temp = []
    pivot = input_list[pivot_position]
    position = 0
    for item in input_list[start:end]:
        if item < pivot:
            list_temp.insert(position, item)
            position += 1
        elif item > pivot:
            list_temp.append(item)
    list_temp.insert(position, pivot)
    input_list[start:end] = list_temp
    return input_list, position + start

print(test_partition([1,5,8,7,3,9,2,11], 0, 7, 3, ([1, 5, 3, 2, 7, 8, 9, 11], 4)))
print(test_partition(["f","n","e","d","a","m"], 0, 5, 3, (['a', 'd', 'f', 'n', 'e', 'm'], 1)))

[AlessandroBertozzi]

def test_partition(input_list, start, end, pivot_position, expected):
    result = partition(input_list, start, end, pivot_position)
    return result == expected

def partition(input_list, start, end, pivot_position):
    my_list = input_list[start:end + 1]
    if len(input_list) == 1:
        return pivot_position
    left_list = []
    right_list = []
    for element in my_list:
        if element > my_list[pivot_position]:
            right_list.append(element)
        elif element < my_list[pivot_position]:
            left_list.append(element)
        elif element == my_list[pivot_position]:
            pass
    position_pivot = len(left_list)
    left_list.append(my_list[pivot_position])
    my_list = left_list.extend(right_list)
    return position_pivot + start

print(test_partition(["The Graveyard Book", "American Gods", "Coraline",
                      "Neverwhere", "Good Omens"], 1, 4, 1, 2))
print(test_partition([1], 0, 1, 0, 0))

[LuisAmmi]

def partition(input_list, start, end, pivot_position):
    pivot_item = input_list[pivot_position]
    current_list = input_list[start:end+1]
    before_start = input_list[:start]
    after_end = input_list[end+1:]
    result = list()
    result.append(pivot_item)
    for i in current_list:
        if i != pivot_item:
            if i < pivot_item:
                result.insert(result.index(pivot_item), i)
            if i > pivot_item:
                result.insert(result.index(pivot_item) + 1, i)
    update_list = before_start + result + after_end
    return update_list.index(pivot_item)

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
my_list2 = list(["Hola", "Ciao", "Amigo", "Salut", "Hello", "Hi"])
print(partition(my_list, 1, 4, 1))
print(partition(my_list2, 2, 6, 3))

[GiuliaMenna]

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

def partition(input_list, start, end, pivot_position):
    part_list = input_list[start:end + 1]
    pivot_value = input_list[pivot_position]
    left = []
    right = []

    if len(input_list) == 1:
        return pivot_position

    for item in part_list:
        if item < input_list[pivot_position]:
            left.append(item)
        if item == part_list[pivot_position]:
            pass
        if item > part_list[pivot_position]:
                right.append(item)

    position_pivot = len(left)
    left.append(part_list[pivot_position])
    input_list = left.extend(right)

    return position_pivot + start

list_ = ["sole", "luna", "abete", "alberi", "canzoni"]
print(test_partition(list_, 1, 4, 3, 2))
list_numbers = [7, 3, 1, 5, 24]
print(test_partition(list_numbers, 0, 4, 1, 1))
list__=[24]
print(test_partition(list__, 0, 1, 0, 0))
family_list= ["dario","gemma","emanuela","stefania","giulia"]
print(test_partition(family_list,0,4,1,2))

[yunglong28]

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 start > end or end >= len(input_list) or pivot_position >= len(input_list):
        return None  # to be safe
    outbefore = list()  #elements before start
    outafter = list()  #elements after end
    before = list()  #elements before the pivot
    after = list()  #elements after the pivot

    pivot_e = input_list[pivot_position]
    pivoter = 1  # count the elements equal to the pivot

    for i in range(len(input_list)):

        if i < start:
            outbefore.append(input_list[i])
        elif i > end:
            outafter.append(input_list[i])
        else:
            if input_list[i] < pivot_e:
                before.append(input_list[i])
            elif input_list[i] > pivot_e:
                after.append(input_list[i])
            else:
                pivoter += 1  #if there's an element = to the pivot

    input_list.clear()

    input_list.extend(outbefore)
    input_list.extend(before)
    # append as many elements to the center as the ones equal to the pivot element
    while pivoter > 0:
        input_list.append(pivot_e)
        pivoter -= 1
    input_list.extend(after)
    input_list.extend(outafter)

    newindex = len(outbefore) + len(before)
    return newindex

print(test_partition(['Mario', 'Luigi', 'Peach', 'Donkey Kong', 'Bowser Jr.'], 0, 4, 3, 1))  #True
print(test_partition([18,22,19,21,24,4], 0, 5, 0, 1))  #True
print(test_partition(['a', 'cc', 'bbb', 'ahahah', 'f'], 0, 4, 0, 0))  #True

[edoardodalborgo]

def test_partition(input_list, start, end, pivot, expected):
    return partition(input_list, start, end, pivot) == expected

def substitution(i, j, input_list):
    i += 1
    input_list.insert(i, input_list[j])
    del input_list[j + 1]
    j += 1
    return input_list, i, j

def partition(input_list, start, end, pivot):
    j, f, i = start, end, start - 1
    pivot_value = input_list[pivot]
    while j <= f:
        if j < pivot:
            if input_list[j] < pivot_value:
                input_list, i, j = substitution(i, j, input_list)
            else:
                j += 1
        else:  
            if input_list[j] >= pivot_value:
                j += 1
            else:
                input_list, i, j = substitution(i, j, input_list)
    return input_list.index(input_list[i + 1])

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

[essepuntato]

About @SarahTew, @LuisAmmi and @dbrembilla's code:

input_list.index(pivot_item) # or similar

You should not use the index method to find the index of your pivot, but you should already know which is the index according to all the swaps you have done.

@SarahTew, about the other comments, did you try to run your code using Python Tutor? I think that you seeing the behaviour of the execution of your algorithm visually can help you in correcting it.

For all: as introduced during a lecture, it would be better to modify the input list "in place" (as Ang does: without creating a new list). Please remind that you must return only the new index of the pivot. However, the execution of partition will also modify the input list by swapping its elements. This is entirely possible if you consider that lists in Python are mutable objects.

[IlaRoss]

I took seriously the "please take your time, think about it" advice @essepuntato! I am posting the last 5 exercises just now, sorry for that. One question regarding partition (and, consequently, quicksort): should these work also when an element occurs more than once in the input_list? If this is the case I will correct my algorithm as it doesn't seem to work. Thank You

# test
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

# algo
def partition(input_list, start, end, pivot_value):
    if start < 0 or start > len(input_list) - 1 or end > len(input_list) - 1:
        return 'start or end outta range'
    if start > end:
        return 'start cannot be greater than end'
    if pivot_value < start or pivot_value > end:
        return 'pivot must be included between start and end'
    else:
        pivot_el = input_list[pivot_value]
        i = start - 1
        k = start
        while (k >= start) and (k <= end):
            if input_list[k] >= pivot_el:
                k += 1
            elif input_list[k] < pivot_el:
                i += 1
                local_variable = input_list[i]
                input_list[i] = input_list[k]
                input_list[k] = local_variable
                k += 1
        copy_pivot = pivot_el
        input_list.remove(pivot_el)
        input_list.insert(i + 1, copy_pivot)
        newpivot = input_list.index(copy_pivot)
        return newpivot

alist = ['g', 'c', 'e', 'd', 'a', 'f', 'b']
blist = [3, 7, 5, 4, 1, 6, 2]
mlist = ['Monteverdi C.', 'Gesualdo C.', 'Marenzio L.', 'Schein J.H.', 'Dowland J.', 'Willaert A.', 'Verdelot, P.',
         'Palestrina G.P.']

# test runs
print(test_partition(alist, 0, 5, 3, 2))
print(test_partition(blist, 1, 5, 4, 1))
print(test_partition(mlist, 2, 7, 7, 4))
print(test_partition(alist, 4, 2, 5, 'start cannot be greater than end'))
print(test_partition(blist, 3, 8, 5, 'start or end outta range'))
print(test_partition(blist, -3, 6, 3, 'start or end outta range'))
print(test_partition(mlist, 1, 4, 6, 'pivot must be included between start and end'))