As discussed in class, the quicksort algorithm starts by partitioning the list: a pivot value

is selected, and the list is partitioned around that pivot. For this problem we'll assume that

The pivot is always the element at index $0$ of the original list $($i$.$e$.,$ before any rearranging

of elements is performed$).$

After partitioning, all the elements to the left of the pivot are $$ the pivot, and all the

elements to the right of the pivot are $>$ the pivot.

In the following parts, assume that stuff is a list of integers.

$($a$)(7$ points$)$ Consider this naive algorithm for partitioning a list stuff:

Create two new low and high lists. These will be used to store the elements of stuff

that are $$ or $>$ the pivot, respectively.

Loop through all elements of stuff besides the pivot. If the element is $$ the pivot,

copy it into low. If the element is $>$ the pivot, copy it into high.

Copy the elements of low back into stuff, then the pivot back into stuff, and finally

the elements of high back into stuff.

Within a Python file named

partitioning.py$,$ write a function partition$\_$naive$($stuff$)$

that implements the above algorithm. The function should return the final $($non$-$negative$)$

index of the pivot, after partitioning is complete. Note that partition$\_$naive doesn't need

to return the partitioned list because the actions that it performs will affect the original

list argument. Make sure that your function works for a list of any length $1.$

$($b$)(7$ points$)$ The partitioning algorithm from the previous part is not very efficient. Creating

the two lists low and high requires extra time as well as memory. A better way is to perform

the partition in$-$place, which means that no new lists are created. Instead, we just modify

the elements of the original list directly.

Suppose we have a list a containing the elements $10,5,16,14,2,10,13.$ As

before, we want to use the first element $(10)$ as the pivot. Here's an algorithm to perform

an in$-$place partition:

Create two indices, L and U$.$ Start L from the beginning of the list; start U from the

end.

Move L forward through the list until we find the first element that's $>$ the pivot $($or

until we run out of elements$).$ Move $U$ backward through the list until we find the first

element that's $$ the pivot $($or until we run out of elements$).$