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

[arcangelo7]

The algorithm should work, but it is not a divide and conquer algorithm. The delivery says it doesn't have to be a recursive algorithm. So maybe that's okay. Anyway, if someone can improve it I would be very grateful. Let's say that it's a temporary solution.

def test_partition(input_list, start, end, pivot_position, expected):
    if expected == partition(input_list, start, end, pivot_position):
        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

my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 4, 1, 1)) # True
# The algorithm messes up the list every time, so I instantiate it again each time
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 1, 4, 1, 2)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 0, 1, 1)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 5, 5, 1, 1)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 2, 4, 4, 2)) # True
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 3, 0, 3)) # True

[arcangelo7]

This is instead the solution by Ang sensei, the video teacher, which is still not a divide and conquer algorithm. Any suggestions?

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

def partition(input_list, start, end, pivot_position):
    i = start - 1
    pivot_item = input_list[pivot_position]
    for item in input_list[start:end+1]:
        if item < pivot_item:
            i += 1
            current_element = item
            input_list[input_list.index(item)] = input_list[i]
            input_list[i] = current_element
    input_list.remove(pivot_item)
    input_list.insert(i + 1, pivot_item)
    return i + 1

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

# The algorithm messes up the list every time, so I instantiate it again each time
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 1, 4, 1, 2)) # True

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

my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 3, 0, 3)) # True

[arcangelo7]

Reading the third issue I realized that this is probably the ancillary algorithm for that one. So I don't think this should be a divide and conquer algorithm.

[sntcristian]

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

def partition(input_list, start, end, pivot_position):
    pivot = input_list[pivot_position]
    for position, item in enumerate(input_list):
        if start <= position and end >= position:
            if item > pivot:
                input_list.insert(pivot_position + 1, input_list.pop(position))
            elif item < pivot:
                input_list.insert(pivot_position, input_list.pop(position))
            pivot_position = input_list.index(pivot)
    return pivot_position

my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 0, 4, 0, 4)) #True

[elisasilvad]

This one is my solution:

This is the solution reached following the video's suggestions:

[FrancescoFernicola]

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

num_list = [2, 4, 42, 20, 16]
print(test_partition(num_list, 1, 4, 4, 2))
num_list = [2, 4, 42, 20, 16]
print(test_partition(num_list, 0, 4, 2, 4))
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 1, 4, 1, 2))
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
print(test_partition(my_list, 2, 4, 0, 4))
FF_list = [ "Terra", "Vivi", "Cid", "Auron", "Sephirot", "Kefka", "Zidane", "Squall"]
print(test_partition(FF_list, 2, 6, 4, 5))

[essepuntato]

Hi all,

please find attached my personal solution – also available online:

# Test case for the function
def test_partition(input_list, start, end, pivot_position, expected):
    p_value = input_list[pivot_position]
    result = partition(input_list, start, end, pivot_position)
    output = expected == result and p_value == input_list[result]

    for item in input_list[0:result]:
        output = output and item <= p_value
    for item in input_list[result + 1:len(input_list)]:
        output = output and item >= p_value

    return output

# Code of the function
def partition(input_list, start, end, pivot_position):
    pivot_value = input_list[pivot_position]

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

    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):
    cur_value = input_list[old_index]
    input_list[old_index] = input_list[new_index]
    input_list[new_index] = cur_value

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