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.

[ValkyrieCain9]

def partition(input_list, start, end, pivot_pos):
    #check that the position value falls within the range of the start and end values
    if pivot_pos<start or pivot_pos>end:
        return None
    else:
        #this method is based on the one explained in the video by KC Ang
        #using the counters i and j, the algorithm will iterate over the list 
        #and rearange the elements based on the value at the pivot value
        pivot_value = input_list[pivot_pos]
        i = start-1
        j = start
        while j<=end:
            #as explained in the video, if the value at j is less than the pivot value, then the i counter will move up one position
            #and the values at i and at j will swap
            if input_list[j]<pivot_value:
                i+=1
                store = input_list[i]
                input_list[i] = input_list[j]
                input_list[j] = store
                j+=1
            else:
                j+=1
        #once all the values have been rearranged the pivot value will be removed from its original postion
        #and reinsterted at the position space ahead from where the i counter was left
        input_list.remove(pivot_value)
        input_list.insert(i+1, pivot_value)
        return input_list.index(pivot_value)

list1 = [2,7,1,8,6,3,5,4]
list2 = [23, 90, 19, 65, 2, 30]
list3 = [7, 5, 13, 6, 4, 2, 1, 8]

print(test_partition(list1,0,len(list1)-1,7,3))
#True
print(test_partition(list2,0,len(list2)-1,2,1))
#True
print(test_partition(list3,0,len(list3)-1,9,None))
#True

[justyna09549]

had a huge problem with tests 2, 3 and 5 returning false. turns out it's because the function actually modifies the list (who would have thought) so redifining the list after each test fixed it.

[yutong316]

I’m a bit confused about the part in Ang’s video where i and j are set and swapped, so I didn’t follow that method. However I think this approach still works.

[KikaYang]

[shiho1000]

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):
    if start > pivot_position or pivot_position > end:
        return None
    
    j = start
    i = start - 1
    pivot_item = input_list[pivot_position]
    while j <= end:
        if input_list[j] >= pivot_item:
            j += 1
        else:
            input_list[j] < pivot_item
            i += 1
            input_list[j] , input_list[i] = input_list[i], input_list[j] # 入れかえる
            j += 1
    input_list.remove(pivot_item)
    input_list.insert(i+1, pivot_item)
    return input_list.index(pivot_item)


my_list1= list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"])
my_list2 = [0,8,0,6,5,7,3,3,2,1,3]
my_list3 = ["Harry", "Ron", "Hermione", "Dumbledore", "Snape", "Voldemort"]

print(test_partition(my_list1,1,4,1,2))  #True
print(test_partition(my_list2,0,len(my_list2)-1,3,8)) #True
print(test_partition(my_list3,0,len(my_list3)-1,3,0)) #True
print(test_partition(my_list3,0,3,4,None)) #True

[lisitein]

the test algorithm can not work because it just divide the list into two parts, but in each part the elements are not ordered.
Except that, I think my algorithm has arrived every conditions that are mentioned above.

def partition(input_list, start, end, pivot_position):
    if pivot_position < start or pivot_position > end:
        return None
    else:
        pivot = input_list[pivot_position]
        i = start-1
        j = start
        input_list.remove(pivot)
        while j < end:
            if input_list[j] <= pivot:
                i += 1
                input_list[i], input_list[j] = input_list[j], input_list[i]
            j += 1
        input_list.insert(i+1, pivot)
        return input_list, i+1

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

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

number = [3,2,5,6,7,1,8,10,6,4]
print(partition(number, 0, len(number)-2, 9))
print(partition(number, 0, 6, 5))

[ERendall]

I took a slightly different approach, moving the pivot position[index] to the end of the list and then comparing (using j) each value in the list.

I hope it is a nice alternative.... I used one of the lists used by @ValkyrieCain9 to see if I got the same result. Seemed to work...

[arinee01]

[orboboro]

def test_partition(input_list, start, end, pivot_position, expected):

    result = partition(input_list, start, end, pivot_position)

    if result != expected:
        
        return False

    else:

        return True

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

    while j <= end:

        if input_list[j] < pivot:

            i+=1

            input_list[j], input_list[i] = input_list[i], input_list[j] 

        j+=1

    input_list.remove(pivot)

    list_part_1=input_list[:i+1]
    list_part_2=input_list[i+1:]

    new_list=list_part_1 + [pivot] + list_part_2

    new_pivot_index=new_list.index(pivot)

    return new_list, new_pivot_index

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

# Solo la parte iniziale della lista è interessata da partition
list=[2,5,4,1,9,7,3] 
print(test_partition(list, 0, 2, 1, ([2, 4, 5, 1, 9, 7, 3], 2)))

# 5 ripetuto due volte
list=[2,5,4,5,8,7,3] 
print(test_partition(list, 0, 6, 3, ([2, 4, 3, 5, 8, 7, 5], 3)))

# True
# True
# True

list=["From the Beginning", "Sultans of Swing", "The Great Gig in che Sky", "Roundabout", "Children of the Moon"]
print(test_partition(list, 0, 4, 0, (['Children of the Moon','From the Beginning','Sultans of Swing','The Great Gig in che Sky','Roundabout'], 1)))

# Solo la parte finale della lista è interessata da partition
list=["From the Beginning", "Sultans of Swing", "The Great Gig in che Sky", "Roundabout", "Children of the Moon"]
print(test_partition(list, 3, 4, 4, (['From the Beginning','Sultans of Swing','The Great Gig in che Sky','Children of the Moon','Roundabout'], 3)))

# Un solo elemento nella lista
list=["From the Beginning"]
print(test_partition(list, 0 ,0 ,0 , (['From the Beginning'], 0)))


# True
# True
# True

[nicoldamelio]