(chapter7:quicksort)=
# Quicksort
The sorts we have seen previously, [bubble sort](chapter4:sevenFunctions:bubblesort), [insertion sort](chapter4:sevenFunctions:practice:insertion), and [selection sort](chapter4:sevenFunctions:practice:selection)
all have a run-time that lies in $\theta (n^2)$.  Can we do better?

What would better look like?  $n^2 = n \cdot n$ so if we can get one of the $n$ terms to grow slower we will have an improvement.  Our goal is to find a faster sorting algorithm, one with a run-time in $\theta(n \log n)$.

How might we create this algorithm?  The simple sorts have one thing in common:  only one item is put into its correct position with each major pass and the items do not move far from where they started. Could we create an algorithm that moves many items closer to their correct position, all in one pass?
The answer is "yes" and many such algorithms have already been invented.  We will study `quicksort` as it is one of the first such algorithms and it is easily expressed with recursion so provides an example of the usefulness of recursion.

## Quicksort Algorithm
In quicksort we pick an item, called the **pivot**, in the list that will get positioned into its proper sorted place.  We move all of the rest of the items so that those less than the pivot are placed into one set, called the **lessor set** and labelled as **L** and those greater than the pivot are placed into another set, called the **greater set** and labelled as **G**[^1].  We then quicksort the lessor set and quicksort the greater set.  Our fully sorted list is the result of sorting the lessor set, appended with the pivot, appended with the result of sorting the greater set, to get ascending order.

The algorithm consists of two parts:  partitioning and sorting.
> Algorithm **partition**($aList, aPivot$) <br>
> Assumes:  <br>
> $\;\;\;\;\;$   - items in $aList$ are unique <br>
> $\;\;\;\;\;$   - $aPivot$ is out of $aList$ <br>
> $\;\;\;\;\;$   - **L** and **G** are empty to start <br>
> <br>  
> 1.  For each item in aList: <br>
> $\;\;\;\;\;$   a. If the item is less than aPivot, move it into **L** <br>
> $\;\;\;\;\;$   b. Otherwise, move it into **G** <br>
> 2.  Return the two lists **L** and **G**. <br>


> Algorithm **quicksort**($aList$) <br>
> Assumes: <br>
> $\;\;\;\;\;$   - items in aList are unique <br>
> <br>  
> 1.  Select a pivot and call it $aPivot$ <br>
> 2.  Remove the pivot from the list <br>
> 3.  Partition $aList$, i.e. {**L**, **G**} ← $partition(aList, aPivot)$ <br>
> 4.  Sort **L** to get **L'**: <br>
> $\;\;\;\;\;$   a.  If **L** is empty or contains one element then **L'** ← **L** <br>
> $\;\;\;\;\;$   b.  Otherwise **L'** ← **$quicksort$**(**L**) <br>
> 5.  Sort **G** to get **G'**: <br>
> $\;\;\;\;\;$   a.  If **G** is empty or contains one element then **G'** ← **G** <br>
> $\;\;\;\;\;$   b.  Otherwise **G'** ← **$quicksort$**(**G**) <br>
> 6.  Return the new list which is the combination of **L'**, {aPivot}, and **G'**, in that order <br>


[^1]: Assumes that the list contains unique items only.  If duplicate items exist, then one of the sets must contain the duplicates.



## Quicksort Example
This algorithm can be run on the following list:
```
{27, 12, 29, 14, 13, 25, 16, 10}
```
If the first pivot chosen is the 16, then when we partition, the lessor and greater sets are:
```
L1 = {12, 14, 13, 10}   the items less than 16
G1 = {27, 29, 25}       the items greater than 16
```
All the items in `L1` will come before the pivot in our final sorted list;  all the items in `G1` will come after the pivot in our final sorted list.

Now `quicksort` is called on `L1` and on `G1`.  For `L1`, assume that the pivot chosen is 13.  Then, when we partition, the new lessor and greater sets are:
```
L2 = {12, 10}
G2 = {14}
```
This requires one more call to `quicksort`, just on `L2` as `G2` is already sorted.  If the pivot is 12, then the partition is:
```
L3 = {10}
G3 = {}
```
Putting this all together, by combining, creates this result so far:
````{list-table}
:header-rows: 0
* - 
    ```
    quicksort(L1) + quicksort(G1)
    {10, 12, 13, 14} + quicksort(G1)
    ```
  - 
    ```{image} figures/qsEx1.png
    :alt: quicksort half done
    :align: center
    ```
````

<br><br>
The algorithm is about half done.  Now the `G1` needs to be sorted.  Partitioning `G1`, with pivot 25, yields:
```
L4 = {}
G4 = {27, 29}
```
One more call to quicksort, on `G4` with pivot 29, will finish the process:
```
L5 = {27}
G5 = {}
```

Combining the results gives the final sorted list.
````{list-table}
:header-rows: 0
* - 
    ```
    {10, 12, 13, 14} + quicksort(G1)
    {10, 12, 13, 14} + {25, 27, 29}
    {10, 12, 13, 14, 25, 27, 29}
    ```
  - 
    ```{image} figures/qsEx2.png
    :alt: quicksort all done
    :align: center
    ```
````

## Quicksort Run-Time Complexity
As you may see in the tree diagrams to the right, above, the first pass through the list results in one item in the correct place.  The second pass results in two more items in the correct place, the two pivots.  The third pass results in up to four more items in the correct place (three in our case because of the shortness of the list).  This process continues, with each pass resulting in up to $2^{p-1}$ more items in their correct place, where $p$ is the pass number.  We see an exponential growth on the number of items in the correct place with each pass through the list.  Thus, we expect a logarithmic function as part of the run-time since there is an exponential amount less to do with each pass, that is run-time will be in $\theta (n \log n)$.

We see that in this diagram, where the nodes at the end mark base cases and hence no key comparisons:  
```{image} figures/qsEx3.png
:alt: quicksort all done with complexity on right side
:align: center
:width: 75%
```

Each pass does fewer than $n$ key comparisons to the pivot, significantly fewer as we move down the tree.  The depth of the tree is a function of $\log _2 n$, because we are cutting our list in about half each time, so our complexity result is in $\theta (n \log n)$.

Note that this expectation of running in $\theta (n \log n)$ is only valid if *the input list keeps dividing approximately in half*. There are cases where this will not happen, and we must be cautious.

```{admonition} Assumptions
Assumptions are critical in computing.  We must overthink everything and see where those assumptions break down.

```

### Worst Case Beware
In the example above, the pivot was chosen to create the ideal situation for `quicksort`.  However, in our programs, the pivot must be chosen in some pre-set manner, without knowing the input list.  Suppose the pivot is chosen as the last item.  What happens if our original list is exactly in order or in reverse order and we run `quicksort`?

Consider the initial list, to be sorted in ascending order:
```
{29, 27, 25, 16, 14, 13, 12, 10}
```
Here is a visualization of the process:
```{image} figures/qsWorstCaseEx.png
:alt: quicksort in worst case tree
:align: center
:width: 75%
```
Yikes!  `quicksort` is back to an algorithm in $\theta (n^2)$, no better than `bubblesort`.  The run-time is even worse than `bubblesort` because we are making recursive calls and, thus, using the stack during execution.  

However, though beyond the scope of this textbook, it has been shown that most of the time `quicksort` will run in $\theta (n \log n)$ with a selection of a good pivot.  A good pivot may be obtained by choosing the median of the first, middle and last elements in the list.  If we had done that in our previous example, we can see that our run-time is again in $\theta (n \log n)$.


```{admonition} Programmer Beware Of Quicksort Worst Case
In life-critical, real-world applications, if no information is known about the data then `quicksort` must be treated as having run-time in $\theta (n^2)$.
```

## In-Place Quicksort
Another potential problem with `quicksort` would be if the lessor and greater  sets (**L** and **G**) are created with a copy process in memory.  On a big list, there are three problems: the time required for allocation of the new memory, knowing the size of each list, and the computer may simply run out of memory.

Linked lists could be used to avoid these problems, but would require a lot of pointers to be moved.  A single array can also be sorted directly in-place with quicksort, and require no extra memory.  The idea is to put the pivot into a specific spot at the start, for example, at the end of the list.  Think of the remainder of the list as divided into two sections:  the left side will become **L** and the right side will become **G**.  When partitioning is complete the pivot is moved to the middle by exchanging it with the first element of **G**.

> Algorithm **inPlacePartition**($aList$, $left$, $right$) <br>
> Assumes: <br>
> $\;\;\;\;\;$  - partitions the list between $left$ and $right$ inclusive <br>
> $\;\;\;\;\;$  - items in $aList$ are unique <br>
> $\;\;\;\;\;$  - pivot is at location $right + 1$ in $aList$ <br>
>   
> 1.  Save variable $pivotLoc$ ← $right + 1$, need at the end when placing pivot <br>
> 2.  Set $aPivot$ ← $aList[pivotLoc]$ <br>
>
> 3.  REPEAT: As long as $left <= right$, i.e. $left$ and $right$ have not crossed <br>
> $\;\;\;\;\;$   a.  Find the first incorrect item in **L**, by moving $left$ sequentially to it (forwards or towards the right) <br>
> $\;\;\;\;\;$   b.  Find the first incorrect item in **G**, by moving $right$ sequentially to it (backwards or towards the left) <br>
> $\;\;\;\;\;$   c.  If $left$ and $right$ have not crossed: <br>
> $\;\;\;\;\;$$\;\;\;\;\;$       i.   Swap the items at $left$ and $right$ <br>
> $\;\;\;\;\;$$\;\;\;\;\;$       ii.  Increment $left$ <br>
> $\;\;\;\;\;$$\;\;\;\;\;$       iii. Decrement $right$ <br>
>        
> 4.  Place the pivot by swapping the items at $pivotLoc$ and $left$ <br>
>
> 5.  Return $left$ as that is now the location of the pivot.  The **L** set is to the
    left of this location and the **G** set is to the right

<br>

> Algorithm **inPlaceQuicksort**($aList$, $left$, $right$) <br>
> Assumes: <br>
> $\;\;\;\;\;$   - sorts the list between $left$ and $right$ inclusive <br>
> $\;\;\;\;\;$   - assumes the pivot is at $right + 1$ <br>
> $\;\;\;\;\;$   - items in $aList$ are unique <br>
> $\;\;\;\;\;$   - $left$ and $right$ are valid locations in the list, at least on first call <br>
>   
> 1.  Base Case: stop if $left > right$ <br>
>
> 2.  Partition and get new pivot location:<br>
> $\;\;\;\;\;$   $pivotLoc$ ← $inPlacePartition(aList, left, right)$<br>
>    
> 3.  quicksort **L** with  $inPlaceQuicksort(aList, left, pivotLoc - 2)$ <br>
> $\;\;\;\;\;$  " $- 1$" would take us to **L**, but the pivot is there so make boundary "$- 2$" <br>
>    
> 4.  quicksort **G** with  $inPlaceQuicksort(aList, pivotLoc + 1, right)$ <br>


## In-Place Quicksort Example
Let's see how `inPlaceQuicksort` works on this list:
```
{27, 12, 29, 14, 13, 25, 10, 16}
```
````{list-table}
:header-rows: 0
* - **1** Starting configuration. $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;\;\;$ $\;\;\;$ 
    ```{image} figures/ip1.png
    :alt: in place quicksort step 1.  27 12 29 14 13 25 10 16  left at 27 right at 10 pivot at 16
    :align: center
    ```
  - **2** Neither `left` nor `right` move because each already has an item that needs to change.  Items are swapped.
    ```{image} figures/ip2.png
    :alt: in place quicksort step 2. 10 12 29 14 13 25 27 16  left at 10 right at 27 pivot at 16
    :align: center
    ```
* - **3** When swap is done, `left` and `right` both move.
    ```{image} figures/ip3.png
    :alt: in place quicksort step 3.  10 12 29 14 13 25 27 16  left at 12 right at 25 pivot at 16
    :align: center
    ```
  - **4** 12 < 16 so `left` moves.
    ```{image} figures/ip4.png
    :alt: in place quicksort step 4. 10 12 29 14 13 25 27 16  left at 29 right at 25 pivot at 16
    :align: center
    ```
* - **5** 29 is not less than 16 so `left` stops.  25 > 16 so `right` moves. 
    ```{image} figures/ip5.png
    :alt: in place quicksort step 5.  10 12 29 14 13 25 27 16  left at 29 right at 13 pivot at 16
    :align: center
    ```
  - **6** 13 is not greater than 16 so `right` stops.  Items at `left` and `right` are swapped.
    ```{image} figures/ip6.png
    :alt: in place quicksort step 6. 10 12 13 14 29 25 27 16  left at 13 right at 29 pivot at 16
    :align: center
    ```
* - **7** After a swap, both `left` and `right` move. 
    ```{image} figures/ip7.png
    :alt: in place quicksort step 7.  10 12 13 14 29 25 27 16  left at 14 right at 14 pivot at 16
    :align: center
    ```
  - **8** 14 < 16 so `left` moves. `left` and `right` have crossed. 
    ```{image} figures/ip8.png
    :alt: in place quicksort step 8. 10 12 13 14 29 25 27 16  left at 13 right at 14 pivot at 16
    :align: center
    ```
* - **9** Swap `pivot` with `left`
    ```{image} figures/ip9.png
    :alt: in place quicksort step 9.  10 12 13 14 16 25 27 29 left at 16 right at 14
    :align: center
    ```
  - **10** Run `inPlaceQuicksort` on the lessor set and the greater set.  
    ```{image} figures/ip10.png
    :alt: in place quicksort step 10. 10 12 13 14 16 25 27 29  left at 10 right at 13 pivot at 14 and left at 25 right at 27 pivot at 29
    :align: center
    ```
````
Do not assume the computer stops just because it looks to us like the list is sorted.  The algorithm must run to completion, following the same steps on the two (sub)lists.
<br><br>
## In-Place Quicksort Java Code

Here is Java code for in-place quicksort:
```{code-block} java
/**
 * Swaps two items in an array of ints.
 * 
 * @param aList - the array
 * @param i - one location
 * @param j - other location
 * 
 * NOTE:  the array will be physically changed.
 */
private static void swap(int[] aList, int i, int j) {
    int temp = aList[i];
    aList[i] = aList[j];
    aList[j] = temp;
}

/**
 * In-place partitions a portion of an integer array for quicksort.
 * Assumes:
 * - unique items in aList
 * - pivot is at end of section to partition, i.e. location right + 1
 * 
 * @param aList - the array to partition
 * @param left - the starting location to partition
 * @param right - the ending location to partition
 * @return - the location of the pivot when done
 * 
 * NOTE:  the array will be physically changed. 
 */
private static int partition(int[] aList, int left, int right) {
    int pivotLoc = right + 1;
    int pivot = aList[pivotLoc];
    while (left <= right) {
        //Find first incorrect in L
        while ((left <= right && aList[left] < pivot)) {
            left++;
        }
        //Find first incorrect in G
        while ((right >= left && aList[right] > pivot)) {
            right--;
        }
        //Swap
        if (left < right) {
            swap(aList, left, right);
            left++;
            right--;
        }
    }

    //Place Pivot
    swap(aList, left, pivotLoc);

    //Need to know the boundary between L and G
    return left; 
}

//Uses the end item as the pivot
/**
 * Implements an in-place version of quicksort to sort a list of integers.
 * The last item in a section is assumed to be the pivot.
 * 
 * @param aList - the list to sort
 * 
 * NOTE 1: aList will be physically changed
 * NOTE 2: the items of aList must be unique
 * NOTE 3: this is a wrapper only
 */
public static void quicksort(int[] aList){
    //last item is at aList.length - 1 and that is the pivot
    //so sort only up to there (pivot moves into place by partition)
    quicksort(aList, 0, aList.length - 2);
}

/**
 * Actual recursive method for in-place quicksort.
 * 
 * @param aList - the array to sort
 * @param left - the lower bound for sort from (inclusive)
 * @param right - the upper bound to sort to (inclusive)
 * 
 * NOTE 1: the items of aList must be unique
 * NOTE 2: the pivot is the item at location right + 1
 */
private static void quicksort(int[] aList, int left, int right){
    int pivotLoc;

    //0 or 1 element [if == there are still 2 elementsm this element
    //and the pivot]
    if (left > right){ 
        return;
    }     

    pivotLoc = partition(aList, left, right);
    quicksort(aList, left, pivotLoc - 2);  //L (remember pivot at end)
    quicksort(aList, pivotLoc + 1, right); //G (new item moved to end)
}
```

(chapter7:quicksort:practice)=
## Practice Questions
1. Draw the operation of `inPlaceQuicksort`, showing each pass, sorting in acsending order, on the following list:
   ```
   {24, 67, 102, 14, 90, 55, 10, 76, 92, 59}
   ```
   Identify all pivots.
2. Draw the operation of `inPlaceQuicksort`, showing each pass, sorting in acsending order, on the following list:
   ```
   {7, 6, 5, 4, 3, 2, 1}
   ```
   Identify all pivots.
3. Draw the operation of `inPlaceQuicksort`, showing each pass, sorting in acsending order, on the following list:
   ```
   {97, 68, 75, 34, 45, 60}
   ```
   Identify all pivots.
4. Write a method called `getMedianLoc` that returns the location of the median of the first element, the last element and the middle element of a list of integers.  Assume that the list has three or more unique elements.
5. Write a Java method to put the median of the first, middle and last elements at the end of a list of integers and puts the original last element wherever the median was.  Use your method from the previous question.  Assume that the list has three or more unique elements.
6. What changes would need to be made to the in-place quicksort Java code if we wanted to sort the list in descending order?

[To Solutions](chapter7:solutions:quicksort)

<br><br>