Lecture "Divide and conquer algorithm", exercise 1

[essepuntato]

Implement in Python the partition algorithm – i.e. def partition(input_list, start, end, pivot_position) – that takes a list and the positions of the first and last elements in the list to consider as inputs, and 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. In addition, the new position where the pivot value is now stored will be returned by the algorithm. 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.

[delfimpandiani]

This was took quite a long while. There is probably a cleaner, shorter way to solve this. Here is one that, at least, works for many different inputs:

Clean code:

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] 
    list_to_consider = input_list[start:end + 1] 

    for item in list_to_consider: 
        if input_list.index(item) < input_list.index(pivot_value) and item > pivot_value:
                input_list.insert(pivot_position, item)
                input_list.remove(item)
                pivot_position -= 1
        elif input_list.index(item) > input_list.index(pivot_value) and item < pivot_value: 
                input_list.remove(item)
                input_list.insert((pivot_position), item)
                pivot_position += 1
                
    pivot_finalpos = input_list.index(pivot_value)
    return(pivot_finalpos, input_list)


print(test_partition(["D", "F", "R", "E", "A"], 1, 4, 0, (1, ["A", "D", "F", "R", "E"])))
print(test_partition(["D", "F", "R", "E", "A"], 1, 4, 1, (3, ["D", "E", "A", "F", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 1, 4, 2, (4, ["D", "F", "E", "A", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 1, (3, ["D", "E", "A", "F", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 3, 1, (2, ["D", "E", "F", "R", "A"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 2, (4, ["D", "F", "E", "A", "R"])))


#True
#True
#True
#True
#True
#True

Code with comments

# Test of partition algorithm
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

# Code of partition algorithm

def partition(input_list, start, end, pivot_position):
    pivot_value = input_list[pivot_position] 
    #create a variable for the value of the item in the pivot position
    list_to_consider = input_list[start:end + 1] 
    #create a new sublist from start to end of the elements to consider

    for item in list_to_consider: 
    # for each item that has to be considered
        if input_list.index(item) < input_list.index(pivot_value) and item > pivot_value:
    # if the item to be considered is on the left of the pivot value and it is bigger than the pivot value
                input_list.insert(pivot_position, item)
                # add the item to the right of the pivot value
                input_list.remove(item)
                # remove first instance of item
                pivot_position -= 1
                # pivot position decreases by 1 since the pivot value moved left
        elif input_list.index(item) > input_list.index(pivot_value) and item < pivot_value: 
        # if the item to be considered is on the right of the pivot value and it is smaller than pivot value
                input_list.remove(item) 
                # remove the item
                input_list.insert((pivot_position), item) 
                # insert the item on the pivot position 
                pivot_position += 1
                # pivot position increases by 1 since the pivot value moved right
                
    pivot_finalpos = input_list.index(pivot_value)
    # create a new variable that hold the final position of the pivot value
    return(pivot_finalpos, input_list)
    # return the new pivot value positoin and the input list with the modifications
 
# Test runs # note that the expected value contains the tuple of expected new pivot position and the expected input list
print(test_partition(["D", "F", "R", "E", "A"], 1, 4, 0, (1, ["A", "D", "F", "R", "E"])))
print(test_partition(["D", "F", "R", "E", "A"], 1, 4, 1, (3, ["D", "E", "A", "F", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 1, 4, 2, (4, ["D", "F", "E", "A", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 1, (3, ["D", "E", "A", "F", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 3, 1, (2, ["D", "E", "F", "R", "A"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 2, (4, ["D", "F", "E", "A", "R"])))

#True
#True
#True
#True
#True
#True

[delfimpandiani]

Here is another way..
Guys help me clean this up, I'm sure it can be cleaner

Clean code

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]
    uncon_left = input_list[0:start]
    con_left = input_list[start:pivot_position]
    con_right = input_list[(pivot_position + 1):(end + 1)]
    uncon_right = input_list[(end + 1):len(input_list)]
    new_list = []

    for item in con_left:
        if item > pivot_value:  
            con_left.remove(item)
            con_right.append(item)

    for item in con_right[0:len(con_right)]:
        if item < pivot_value:
            con_right.remove(item)
            con_left.append(item)

    new_list.extend(uncon_left)
    new_list.extend(con_left)
    new_list.append(pivot_value)
    new_list.extend(con_right)
    new_list.extend(uncon_right)

    pivot_finalpos = new_list.index(pivot_value)
    return pivot_finalpos, new_list

print(test_partition(["D", "F", "R", "A", "E"], 0, 4, 1, (3, ["D", "A", "E", "F", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 3, 1, (2, ["D", "E", "F", "R", "A"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 2, (4, ["D", "F", "E", "A", "R"])))

Code with comments

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]

    # 4 lists
    uncon_left = input_list[
                 0:start]  # from first element of input list to the first element to be considered (noninclusive)
    con_left = input_list[
               start:pivot_position]  # from first element to be considered to the pivot position (noninclusive)
    con_right = input_list[(pivot_position + 1):(
                end + 1)]  # from element after pivot position to the las element to be considered (inclusive)
    uncon_right = input_list[(end + 1):len(
        input_list)]  # from element after last element to be considerd to the end of the input list
    new_list = []

    for item in con_left:  # for each item to be considered that is to the left of the pivot value
        if item > pivot_value:  # if the item is bigger than the pivot value
            con_left.remove(item)  # remove from left list
            con_right.append(item)  # add to right list

    for item in con_right[0:len(con_right)]:  # for each item to be considered that is to the right of the pivot value
        if item < pivot_value:  # if the item is smaller than the pivot value
            con_right.remove(item)  # remove from right list
            con_left.append(item)  # add to left list

    # uncon_left and uncon_right remain the same
    new_list.extend(uncon_left)
    new_list.extend(con_left)
    new_list.append(pivot_value)
    new_list.extend(con_right)
    new_list.extend(uncon_right)


    pivot_finalpos = new_list.index(pivot_value)
    return pivot_finalpos, new_list


print(test_partition(["D", "F", "R", "A", "E"], 0, 4, 1, (3, ["D", "A", "E", "F", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 3, 1, (2, ["D", "E", "F", "R", "A"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 2, (4, ["D", "F", "E", "A", "R"])))


# True
# True
# True

[lisasiurina]

def partition(input_list, start, end, pivot_position):
 l =list()
 u=0 
 for i in input_list : 
   print(l)
   if pivot_position<u<end:      
                l.append(i)
      
   else:
                
                l.insert(start,i)
   u=u+1
   print(l)
 g=input_list[pivot_position]
 v=end-start
 k=l.index(g, 0 ,v)
 print(k)
partition(["A","B","C","D","E"],1,5,2)

[]
['A']
['A']
['A', 'B']
['A', 'B']
['A', 'C', 'B']
['A', 'C', 'B']
['A', 'C', 'B', 'D']
['A', 'C', 'B', 'D']
['A', 'C', 'B', 'D', 'E']
1

[simayguzel]

@Hizkie and I found a solution after 2 days of working. Our solution works for all probable pivot_positions.

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]
    for position, item in enumerate(input_list):
        if start <= position <= end:
            if item in input_list[start:pivot_position+1]:
                if item > pivot_value:
                    new_value = item
                    input_list.pop(position)
                    input_list.insert(end,new_value)
                    pivot_position = position
            elif item in input_list[pivot_position+1:end+1]:
                if item < pivot_value:
                    new_value = item
                    input_list.pop(position)
                    input_list.insert(start,new_value)
                    pivot_position = position
    
    for position, item in enumerate(input_list):
        if start <= position <= end:
            if item in input_list[start:pivot_position+1]:
                if item > pivot_value:
                    for position, item in enumerate(input_list):
                        if item == pivot_value:
                            pivot_position = position
                    partition(input_list, start, end, pivot_position)
            elif  item in input_list[pivot_position+1:end+1]:
                if item < pivot_value:
                    for position, item in enumerate(input_list):
                        if item == pivot_value:
                            pivot_position = position
                    partition(input_list, start, end, pivot_position)
    for position, item in enumerate(input_list):
        if item == pivot_value:
            return position
    
 #Since lists are mutable, we have used different names for each list while running the test.

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list1 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list2 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list3 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])

print(test_partition(my_list, 1, 4, 1,2))     #True
print(test_partition(my_list1, 1, 4, 2,4))    #True
print(test_partition(my_list2, 1, 4, 4,1))     #True
print(test_partition(my_list3, 1, 4, 3,3))     #True

[ilsamoano]

I've understood in the end how Delfina & Lisa sorted the problem.
Anyway my first approach was to create 2 new lists, saving in the first one every element of the considered range of the input list > the pivot position,
and in the second every element of the considered range of the input list <= the pivot position,
and then add to the second list created the first one: I am not able to code it correctly, for the moment.
but I'd like to understand if it is a doable approach or if the logic behind this is wrong: I've put below the correct solution my wrong attempt as a reference

#correct 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):
  
    pivot_value = input_list[pivot_position]
    start_end_list = input_list[start: end + 1]
    
    for item in start_end_list:
         if input_list.index(item)< input_list.index(pivot_value) and item > pivot_value: 
             input_list.insert(pivot_position,item)
             input_list.remove(item)
             pivot_position -= 1
             
             
         elif input_list.index(item) > input_list.index(pivot_value) and item < pivot_value:          
             input_list.remove(item)
             input_list.insert(pivot_position, item)
             pivot_position += 1
             
    new_pivot_position= (input_list.index(pivot_value))
    return (input_list,new_pivot_position )


print(TEST_partition(["Z", "C", "N", "G", "A"], 1, 4, 1, (['Z', 'A','C','N','G'],2)))

True

#my first wrong approach

def partition(input_list, start, end, pivot_position):
  
    pivot_value = input_list[pivot_position]
    start_end_list = input_list[start: end + 1]
    leftlist= list()
    rightlist= list()
   
    
    for Item in start_end_list:
       
          if input_list.index(Item) >= input_list.index(pivot_value):
       
           rightlist.append(Item)
           input_list.remove(Item)
       
     
          elif input_list.index(Item) <= input_list.index(pivot_value):
       
           leftlist.append(Item)
           input_list.remove(Item)
                
           
           
    input_list.extend(leftlist)
    input_list.extend(rightlist)


    new_pivot_position= (input_list.index(pivot_value))
    return (input_list,new_pivot_position)

[delfimpandiani]

@ilsamoano

Here is what I meant on my voice note:

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]
    start_end_list = input_list[start: end + 1]
    not_considered = input_list[0:start]
    leftlist = list()
    rightlist = list()

    for item in start_end_list:

        if input_list.index(item) > input_list.index(pivot_value):

            rightlist.append(item)
            input_list.remove(item)


        elif input_list.index(item) < input_list.index(pivot_value):

            leftlist.append(item)
            input_list.remove(item)

    for leftitem in leftlist:
        if leftitem > pivot_value:
            rightlist.append(leftitem)
            leftlist.remove(leftitem)

    for rightitem in rightlist:
        if rightitem < pivot_value:
            leftlist.append(rightitem)
            rightlist.remove(rightitem)

    input_list = not_considered
    input_list.extend(leftlist)
    input_list.append(pivot_value)
    input_list.extend(rightlist)

    new_pivot_position = (input_list.index(pivot_value))
    return (input_list, new_pivot_position)


print(test_partition(["Z", "C", "N", "G", "A"], 1, 4, 1, (['Z', 'A', 'C', 'N', 'G'], 2)))

# true

Thought about it more and shortened it just a bit:

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]
    start_end_list = input_list[start: end + 1]
    leftlist = input_list[0:pivot_position]
    rightlist = input_list[(pivot_position + 1): len(input_list)]

    for leftitem in leftlist:
        if leftitem in start_end_list and leftitem > pivot_value:
            rightlist.append(leftitem)
            leftlist.remove(leftitem)

    for rightitem in rightlist[0:len(rightlist)]:
        if rightitem in start_end_list and rightitem < pivot_value:
            leftlist.append(rightitem)
            rightlist.remove(rightitem)

    input_list = leftlist
    input_list.append(pivot_value)
    input_list.extend(rightlist)

    new_pivot_position = (input_list.index(pivot_value))
    return (new_pivot_position, input_list)


print(test_partition(["D", "F", "R", "A", "E"], 0, 4, 1, (3, ["D", "A", "E", "F", "R"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 3, 1, (2, ["D", "E", "F", "R", "A"])))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 2, (4, ["D", "F", "E", "A", "R"])))

# true
# true
# true

[SeverinJB]

The following algorithm employs the principles of "divide and conquer algorithms" (base case, divide, conquer, combine). In order to implement the divide and conquer approach, the algorithm uses two inner functions of which one is using itself recursively.

When I am doing the second exercise tomorrow, I will try to improve this algorithm. If I am able to tweak the code I'll post an update.

# --- Test Algorithm ---
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

# --- Algorithm ---
def partition(input_list, start, end, pivot_position):
    if 0 <= start <= pivot_position <= end <= len(input_list):
        pivot_object = input_list[pivot_position]
        excerpt_list = input_list[start:end + 1]
        excerpt_list.remove(pivot_object)
        ordered_list = [pivot_object]

        def conductor(input):
            input_len = len(input)

            if input_len == 1: 
                return assistant(input)
            else:  
                mid = input_len // 2 
                conductor(input[0:mid])
                conductor(input[mid:input_len]) 

        def assistant(value): 
            if value[0] > pivot_object:
                ordered_list.insert(len(ordered_list), value[0]) 
            else:
                ordered_list.insert(0, value[0]) 

        conductor(excerpt_list)
        input_list[start:end + 1] = ordered_list
        print(input_list.index(pivot_object))
        return input_list

    else:
        print("Input values without effect.")
        return input_list

# --- Test Cases ---
print(test_partition(["Rory", "Lorelai", "Luke", "Lane"], 1, 3, 2, ["Rory", "Lane", "Lorelai", "Luke"]))
print(test_partition(["Tristan", "Logan", "Jess", "Dean"], 5, 3, 2, ["Tristan", "Logan", "Jess", "Dean"]))

[delfimpandiani]

Simple, clean approach based on Prof. Peroni's explanation in class today.

def test_partition(input_list, s, e, pp, expected):
    result = partition(input_list, s, e, pp)
    if result == expected:
        return True
    else:
        return False

def partition(input_list, s, e, pp):
        pv = input_list[pp]
        for item in input_list[s:(e +1)]:
            if item == pv:
                pass
            elif item < pv:
                input_list.remove(item)
                input_list.insert(0, item)
            elif item > pv:
                input_list.remove(item)
                input_list.insert(e, item)
        new_pp = input_list.index(pv)
        return new_pp

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

#True 
#True 

# also tried with Hizkiel's test and it works:

my_list = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list1 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list2 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])
my_list3 = list(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"])

print(test_partition(my_list, 1, 4, 1,2))     #True
print(test_partition(my_list1, 1, 4, 2,4))    #True
print(test_partition(my_list2, 1, 4, 4,1))     #True
print(test_partition(my_list3, 1, 4, 3,3))    #True 

[tceron]

I'm extremely happy to be posting the solution of this exercise after so many hours over it, nightmares (for real) and hints from colleagues :D

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

def partition(input_list, start, pivot_position, end):
    pivot_value = input_list[pivot_position]
    for i in input_list[start:end +1]:
        if i < pivot_value:
            curEle = i
            input_list.remove(curEle)
            input_list.insert(0, curEle)
        elif i > pivot_value:
                input_list.append(i)
                input_list.remove(i)
    new_pivot_position =  input_list[pivot_position]
    return new_pivot_position

test_partition(['oranges', 'banana', 'strawberry', 'pineapple', 'apple', 'pear'], 1, 1, 4, "oranges") #true
test_partition([["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"], 1, 2, 4, "Coraline") #true

[EleonoraPeruch]

Here I propose two possible solutions: the first algorithm uses a sublist and it works; however, I wanted to use the range and I have been struggling for hours trying to find a solution. So the second code I propose uses the range, but it worked only with some tests so I know it is not correct, but maybe it can be a start, of course only in the case in which we can actually use range for solving this exercise. Suggestions are more than welcome!

# test 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 of the algorithm using sublist
# it works with whatever type of value in the list
def partition(input_list, start, end, pivot_position):
    p = input_list[pivot_position]
    for item in input_list[start : end + 1]:
            if item > p :
                input_list.remove(item)
                input_list.insert(end, item)
            if item < p :
                input_list.remove(item)
                input_list.insert(start, item)
    new_pivot_position = input_list.index(p) # use index to retrieve the position of an item in a list
    return new_pivot_position

# run some tests
print(test_partition(["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens", "American Gods"], 1, 4, 1, 2))
print(test_partition([4, 3, 5, 1, 7], 0, 4, 0, 2))

# true
# true


# code of the algorithm using range
def partition(input_list, start, end, pivot_position):
    p = input_list[pivot_position]
    for i in input_list: # i is taken as an item of the list, either number or str
        if i in range(start, end + 1): # with range i is taken as integer
            if i > p :
                input_list.remove(i)
                input_list.insert(end, i)
            if i < p :
                input_list.remove(i)
                input_list.insert(start, i)
    new_pivot_position = input_list.index(p)
    return new_pivot_position

# run some tests
print(test_partition([4, 3, 5, 1, 7], 0, 4, 0, 2))

# true

[federicabologna]

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

print(test_partition([4, 1, 7, 3, 7, 8, 9, 2], 0, 7, 0, 3))
print(test_partition([4, 3, 5, 1, 7], 0, 4, 0, 2))
my_list = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"]
my_list2 = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"]
my_list3 = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"]
my_list4 = ["The Graveyard Book", "Coraline", "Neverwhere", "Good Omens","American Gods"]
print(test_partition(my_list, 1, 4, 1, 2))
print(test_partition(my_list2, 1, 4, 2, 4))
print(test_partition(my_list3, 1, 4, 4, 1))
print(test_partition(my_list4, 1, 4, 3, 3))
print(test_partition(["D", "F", "R", "A", "E"], 0, 4, 1, 3))
print(test_partition(["D", "F", "R", "E", "A"], 0, 3, 1, 2))
print(test_partition(["D", "F", "R", "E", "A"], 0, 4, 2, 4))

True
True
True
True
True
True
True
True
True

[essepuntato]

Hi guys,

That has been the most interesting discussion we had so far in the entire course. I really thank you for all you effort in solving it, providing an incredible number of different perspectives and angles to look at this problem. It has been great.

Here my solution to the problem - I hope you can find it clear but I'm happy to discuss it in the next lecture. The source code is available online as usual.

# Test case for the algorithm
def test_partition(input_list, start, end, pivot_position, expected):
    p_value = input_list[pivot_position]
    result = partition(input_list, start, end, pivot_position)
    if expected == result and p_value == input_list[result]:
        return True
    else:
        return False


# Code of the algorithm
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))