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.

[krzywonos]

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

def partition(input_list, start, end, pivot_position):
    i = start - 1;
    for j in range(start, end):
        if input_list[j] <= input_list[pivot_position]:
            i = i + 1;
            (input_list[i], input_list[j]) = (input_list[j], input_list[i]);
    (input_list[i + 1], input_list[end]) = (input_list[end], input_list[i + 1]);
    return i + 1;

test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2);
test_partition([5, 3, 9, 21, 2, 3, 3], 1, 5, 3, 5);

[valetedd]

#Ex 2 D&C algorithms: Partition algorithm
def test_partition(input_list, start, end, pivot_position, expected):
    if partition(input_list, start, end, pivot_position) == expected:
        return True
    else:
        return False

def partition(input_list, start, end, pivot_position):
    if not (start <= pivot_position <= end) or len(input_list) == 0:
        return None
    pivot_element = input_list[pivot_position]

    for i in input_list[start : end + 1]:
        curr_index = input_list.index(i)
        if  i > pivot_element and curr_index < pivot_position:
            input_list.remove(i)
            input_list.insert(pivot_position, i)
            pivot_position -= 1
        elif i < pivot_element and curr_index > pivot_position:
            input_list.remove(i)
            input_list.insert(pivot_position, i)
            pivot_position += 1
        else: 
            pass
    return pivot_position

print(test_partition(['Coraline', 'Neverwhere', 'American Gods', 'The Graveyard Book'], 0, 3, 2, 0))
print(test_partition(['Coraline', 'Neverwhere', 'American Gods', "Coraline", 'The Graveyard Book'], 0, 4, 2, 0))
print(test_partition([2,-2, 9, 7, 5, 1, 11], 2, 6, 3, 4))
print(test_partition(["bobcat", "cat",  "lion", "deer","beetle" , "albatros"], 1, 5, 3, 4))
print(test_partition([0, 1], 0, 1, 1, 1))
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 0, 3, 2, 2))

[ThIheb]

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_val = input_list[pivot_position]
    i = start -1 
    for j in range(start, end+1):
        if input_list[j] < input_list[pivot_position]:
            i += 1
            if i == pivot_position:
                pivot_position = j
            swap(input_list, i, j)
    k = i +1
    swap(input_list, pivot_position, k)
    return k
def swap(input_list, o, n):
    temporary_value = input_list[o]
    input_list[o] = input_list[n]
    input_list[n] = temporary_value
print(test_partition(['Coraline', 'Neverwhere', 'American Gods', 'The Graveyard Book'], 0, 3, 2, 0))
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))

[Liber-R]

[qwindici]

def partition(input_list, start, end, pivot_position):
    try:
        i = start - 1
        j = start
        pivot = input_list[pivot_position]
        while j <= end:
            if input_list[j] > pivot:
                j += 1
            elif input_list[j] < pivot:
                i += 1
                # swap j and i
                input_list[j], input_list[i] = input_list[i], input_list[j]
                j += 1
            else:
                j += 1
        input_list.remove(pivot)
        input_list.insert(i + 1, pivot)
        return i + 1
    except IndexError:
        return "Invalid pivot"

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

# integer list
print(
    test_partition(
        input_list=[7, 2, 1, 8, 6, 3, 5, 4],
        start=2,
        end=7,
        pivot_position=5,
        expected=3,
    )
)
# string list
print(
    test_partition(
        input_list=["Zebra", "Cow", "Sheep", "Cat", "Dog"],
        start=1,
        end=4,
        pivot_position=1,
        expected=2,
    )
)
# first element as pivot
print(
    test_partition(
        input_list=[7, 2, 1, 8, 6, 3, 5, 4],
        start=0,
        end=7,
        pivot_position=0,
        expected=6,
    )
)
# last element as pivot
print(
    test_partition(
        input_list=[7, 2, 1, 8, 6, 3, 5, 4],
        start=0,
        end=7,
        pivot_position=7,
        expected=3,
    )
)
# empty list
print(
    test_partition(
        input_list=[],
        start=0,
        end=7,
        pivot_position=7,
        expected="Invalid pivot",
    )
)

# invalid pivot
print(
    test_partition(
        input_list=[1, 2, 3],
        start=1,
        end=7,
        pivot_position=5,
        expected="Invalid pivot",
    )
)

[frammenti]

def test_partition(input_list, start, end, pivot_position, expected):
    result = partition(input_list, start, end, pivot_position)
    # If partition is not possibile test is concluded after match between expected and result
    if expected == result == None:
        return True
    # Test checks not only for the new position of the pivot but also for compliancy to program specification:
    # the modified list should have items smaller than the pivot to its left and bigger to its right
    elif expected == result:
        left_side = input_list[start:expected]
        right_side = input_list[expected+1:end+1]
        pivot = input_list[expected]
        if (left_side == [] or [item <= pivot for item in left_side] and
            right_side == [] or [item >= pivot for item in right_side]):
            return True
        else:
            return False
    else:
        return False

def partition(input_list, start, end, pivot_position):
    if start <= pivot_position <= end and len(input_list) > 0:
        i = start - 1
        pivot = input_list.pop(pivot_position)
        # Range is inclusive of end item because pivot item (included in range)
        # was removed from the list
        for j in range(start,end):
            if input_list[j] < pivot:
                i += 1
                input_list[i], input_list[j] = input_list[j], input_list[i]
        new_position = i + 1
        input_list.insert(new_position, pivot)
        return new_position

num_list = [7, 2, 1, 8, 6, 3, 5, 4]
book_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
ordered_list = [1, 2, 3, 4, 5, 6, 7]
binary_list = [0, 0, 1, 1, 0, 1, 0, 0, 1]

# Tests are run on copies of input lists to make their reuse possible
print(test_partition(list(book_list), 1, 4, 1, 2)) # Pivot in start position
print(test_partition(list(num_list), 0, 7, 7, 3)) # Pivot in last position
print(test_partition(list(book_list), 0, 3, 0, 3)) # Pivot in zero position
print(test_partition(list(binary_list), 1, 7, 3, 5)) # List with repetitions
print(test_partition(list(ordered_list), 2, 5, 4, 4)) # Ordered list
print(test_partition(list(ordered_list[::-1]), 2, 5, 4, 3)) # Reversed order list
print(test_partition([1], 0, 0, 0, 0)) # One-item list
print(test_partition([], 0, 0, 0, None)) # Empty list
print(test_partition(list(book_list), 1, 4, 0, None)) # Pivot out of range

The pop-insert method may modify the order of items bigger than the pivot strictly on the right side, but is it a problem? Although not ideal, the function is still compliant with program specifications. I think the pop-insert method best implements the procedure shown by the nice gentleman in the video.

Edit: removed the negative range thing because in hindsight it was absurd

[rufferbaraldi]

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

print(test_partition(["The Graveyard Book", "American Gods", "Coraline", "Neverwhere", "Good Omens"], 1, 4, 1, 1))
print(test_partition([2, 8, 9, 3, 5, 1, 7], 1, 6, 3, 2))
print(test_partition(["Good Omens", "Neverwhere", "American Gods", "Coraline", "The Graveyard Book"], 0, 4, 2, 0))
print(test_partition(["Bologna", "Milano", "Napoli", "Roma", "Firenze", "Venezia"], 0, 5, 3, 4))

[valentinabertelli]

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]
    i = start - 1
    for item in input_list[start:end + 1]:
        if item < pivot_value:
            i = i + 1
            j = input_list.index(item)
            input_list[i], input_list[j] = input_list[j], input_list[i]
    input_list.remove(pivot_value)
    input_list.insert(i + 1, pivot_value)        
    return input_list.index(pivot_value)

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

[vattelalberto]

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 pivot_position < start or pivot_position > end:
        return None
    pivot = input_list.pop(pivot_position)
    i = start - 1
    for j in range(start, end):
        j_item = input_list[j]
        i_item = input_list[i]
        if j_item < pivot:
            i += 1
            input_list[i], input_list[j] = input_list[j], input_list[i]
    new_pivot_position = i + 1
    input_list.insert(new_pivot_position, pivot)
    return new_pivot_position

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

[Sergpoipoip]

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

def partition(input_list, start, end, pivot_position):
    el = input_list[pivot_position]
    for i in input_list[start:end+1]:
        if i < el:
            input_list.remove(i)
            input_list.insert(start, i)
        elif i > el:
            input_list.remove(i)
            input_list.insert(end, i)
    return input_list.index(el)

my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"]
my_list_1 = [0, 23, 11, -3, 20, 18, -1, 34]
my_list_2 = ['A', 'Z', 'X', 'P', 'B', 'F', 'Q']
print(test_partition(my_list, 1, 4, 1, 2))
print(test_partition(my_list_1, 0, 6, 4, 5))
print(test_partition(my_list_2, 0, 6, 3, 3))

[enricabruno]

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

# function 
def partition(input_list, start, end, pivot_position):
    if start <= pivot_position <= end and len(input_list) > 0:  
# where to put element to swap
        j = start - 1
# pivot as the last element of the list
        pivot_position = input_list.pop(pivot_position)
# consider all the element before pivot
        for i in range(start, end):
            if input_list[i] < pivot_position:
                j += 1
                input_list[i], input_list[j] = input_list[j], input_list[i]
        new_position = j + 1
        input_list.insert(new_position, pivot_position)
        return new_position

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

[simocasaz]

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 swap(pos_1, pos_2, input_list):
    prov = input_list[pos_1]
    input_list[pos_1] = input_list[pos_2]
    input_list[pos_2] = prov

def partition(input_list, start, end, pivot_position):
    i = start - 1
    swap (pivot_position, end, input_list)
    for j in range(start, end):
        if input_list[j] < input_list[end]:
            i += 1
            swap(i, j, input_list)
    new_pivot_position = i + 1
    input_list.insert(new_pivot_position, input_list[end])
    del input_list[end + 1]
    return new_pivot_position

print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))
print(test_partition(["I soliti ignoti"], 0, 0, 0, 0))
print(test_partition(["Inglourious Basterds", "Jackie Brown", "The Hateful Eight", "Reservoir Dogs", "Once Upon a Time in Hollywood", "Kill: Bill Vol. 2", "Kill Bill: Vol. 1", "Pulp Fiction"], 2, 6, 3, 5))
print(test_partition([4, 10, 3, 7, 8, 9, 1], 2, 3, 3, 3))
print(test_partition([10, 5, 7, 4, 2, 9], 0, 5, 0, 5))