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.

[delete4ever]

It's not beautiful enough and works strangely I think I should try again.

# Test case for the algorithm
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
# Code for the algorithm
def partition(input_list, start, end, pivot_position):
    if len(input_list) <= 1:
        return 0
    else:
        left_list= list()
        right_list= list()
        wanted_list= input_list[start:(end+1)]
        if pivot_position >= start:
            for i in wanted_list:
                if i < input_list[pivot_position]:
                    left_list.append(i)
                if i > (input_list[pivot_position]):
                    right_list.append(i)
            input_list[:] = list(input_list[0:start] + left_list + [input_list[pivot_position]] + right_list + input_list[end+1:len(input_list)])
            return len(input_list[0:start]) + len(left_list)
# Three test runs
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2)) #True
print(test_partition([3, 2, 4, 1, 5], 0, 4, 3, 0)) #True
print(test_partition([0], 0, 0, 0, 0)) #True

[leonardozilli]

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

    if pivot_position >= start and pivot_position <= end:
        for item in input_list[start:end + 1]:
            if item < input_list[pivot_position]:
                i += 1
                if pivot_position == i:
                    pivot_position = input_list.index(item)
                input_list[input_list.index(item)], input_list[i] = input_list[i], input_list[input_list.index(item)]
        input_list.insert(i + 1, input_list[pivot_position])
        input_list.pop(pivot_position + 1)

        pivot_new_position = input_list.index(pivot_item)
        return input_list, pivot_new_position
    else:
        return None


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

[ranacoskun]

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

    for position in range(start, end + 1):
        if input_list[position] < input_list[pivot_position]:
            i = i + 1
            if i == pivot_position:
                pivot_position = position
            temp = input_list[position]
            input_list[position] = input_list[i]
            input_list[i] = temp

    temp = input_list[pivot_position]
    input_list[pivot_position] = input_list[i + 1]
    input_list[i + 1] = temp

    return i + 1


print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))  # True
print(test_partition(["d", "e", "a", "c"], 0, 3, 3, 1))  # True
print(test_partition([7, 6, 3, 9, 12, 1], 0, 5, 5, 0))  # True
print(test_partition([7, 6, 3, 9, 12, 1], 2, 5, 4, 5))  # True

[EricaAndreose]

Solution

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
            temp=input_list[j]
            input_list[j]=input_list[i]
            input_list[i]=temp
    return i+1


print(test_partition(["a", "c", "b", "f"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 3, 3))
print(test_partition(["a", "c", "b", "f"], 0, 2, 1, 2)) 
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 1, 4, 1, 1))
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 0, 4, 3, 4)) 

Second try

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: list, start, end, pivot_position):
    i= start-1
    item_pivot=input_list[pivot_position]
    for item in input_list[start:end+1]:
        if item < item_pivot:
            i = i+1
            input_list.remove(item)
            input_list.append(item)
    item == item_pivot
    pivot_position = i+1
    return pivot_position


print(test_partition(["a", "c", "b", "f"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 3, 3))
print(test_partition(["a", "c", "b", "f"], 0, 2, 1, 2)) 
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 1, 4, 1, 1))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 0, 4, 3, 4)) 

First try

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: list, start, end, pivot_position):
    i= start-1
    item_pivot=input_list[pivot_position]
    left_list = list()
    right_list = list()
    for item in input_list[start:end+1]:
        if item > item_pivot:
            right_list.append(item)
        elif item < item_pivot:
            left_list.append(item)
            i = i+1
    pivot_position = i+1
    left_list + [pivot_position] + right_list
    return pivot_position

print(test_partition(["1", "3", "2", "7"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 0, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 2, 1))
print(test_partition(["1", "3", "2", "7"], 1, 3, 2, 1))
print(test_partition(["a", "c", "b", "f"], 1, 3, 3, 3))
print(test_partition(["a", "c", "b", "f"], 0, 2, 1, 2)) 
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 1, 4, 1, 1))
print(test_partition(["mela", "banana", "pera", "uva", "kiwi"], 0, 4, 3, 4)) 
print(test_partition(["mela", "banana", "pera", "uva", "arancia"], 2, 4, 4, 2)) 
print(test_partition(["1", "3", "2", "7"], 0, 3, 2, 1))
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))
print(test_partition(["d", "e", "a", "c"], 0, 3, 3, 1))

[lucia1299]

Solution

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

print(test_partition([0, 3, 5, 6, 2, 9, 10], 0, 6, 2, 3)) #True
print(test_partition(["Bologna", "Milano", "Napoli", "Parlemo", "Firenze", "Venezia"], 0, 5, 3, 4)) #True
print(test_partition([56, 34, 901, 2, 3, 6, 345], 0, 6, 4, 1)) #True

Previous solution

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):
    left_list = list()
    right_list = list()
    pivot_item = input_list[pivot_position]
    for item in input_list[start:]:
        if item < input_list[pivot_position]:
            left_list.append(item)
        elif item > input_list[pivot_position]:
            right_list.append(item)
        elif item == input_list[pivot_position]:
            right_list.append(pivot_item)
            pivot_item = right_list[0]
    new_list = list(left_list + right_list)
    return new_list.index(pivot_item)

print(test_partition([0, 3, 5, 6, 2, 9, 10], 0, 6, 2, 3)) #True
print(test_partition(["Bologna", "Milano", "Napoli", "Palermo", "Firenze", "Venezia"], 0, 5, 3, 4)) #True
print(test_partition([56, 34, 901, 2, 3, 6, 345], 0, 6, 4, 1)) #True

[n1kg0r]

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


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


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

[ChiaraParravicini]

# considering the end item as pivot
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_position >= start and pivot_position <= end
    i = start - 1
    j = start
    for j in range(len(input_list[start:end+1])):
        if input_list[j] <= input_list[pivot_position]:
            i += 1
            temp = input_list[j]
            input_list[j] = input_list[i]
            input_list[i] = temp
    return i
print(test_partition([4, 2, 5, 0, 9, 3], 0, 5, 5, ([2, 0, 3, 4, 9, 5], 2)))
print(test_partition([0, 5, 7, 1, 2], 0, 3, 3, ([0, 1, 7, 5, 2], 1)))
print(test_partition(["c", "a", "b", "d", "b"], 0, 4, 4, (["a", "b", "b", "d", "c"], 2)))
print(test_partition([''], 0, 0, 0, ([''], 0)))

[alka2696]

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

print(test_partition(["Alka","Prabha","Neelam","Madan"],0,3,3,1)) #True
print(test_partition(["a","e","j","i","d"],1,4,3,3)) #True