import cs125.sorting.quicksort.Partitioner.partition

val array = arrayOf("you", "are", "not", "alone")

partition(array)

println(array.contentDeepToString())

We continue our discussion of sorting algorithms by introducing the wild child: Quicksort.
Quicksort *can* achieve best-case sorting behavior while using less space than Mergesort.
**But**, Quicksort also has some pathological cases we need to understand.
Let’s get started!

Warm Up Debugging Challenge

You knew it was coming…

Let's continue exploring recursion on binary trees. However, this problem takes a significant step forward in difficulty, so be prepared!

We've provided a method `pathToValue`

that accepts a `BinaryTree<Any>`

as its first parameter
and an `Any`

as its second.
It returns a `List<Any>`

containing all the *values* in the tree on the way to the *first* node with a
value equal to the passed `Any`

, or `null`

if the tree does not contain the passed `Any`

. We've handled this
case already for you in the starter code.

Our wrapper method initializes the list properly and then calls a private helper method which performs the
recursion. The helper should return `true`

if the tree contains the value, and if it does also manipulate the list
properly. If the tree does not contain the value it should return `false`

. You will want to use ```
add(int index,
Any value)
```

to add values to the front of the list as you work your way through the tree.

This problem is hard! Here's an outline of a solution to help get you started:

- If you reach an empty tree, you can return
`false`

, since an empty tree does not contain the value - Otherwise, if
*this*node contains the value, add yourself to the list, stop recursing, and return`true`

. - Otherwise, first search your
*right*subtree. If that succeeds, then this node is also part of the path and should be added. If not, try the left subtree. - If neither the right nor left subtree contains the node, you should return false and not modify the list, since this node is not on the path to the desired node.

Good luck and have fun!

Partitioning

Mergesort was our first recursive sorting algorithm. It employed a bottom-up approach—first breaking the array into individual chunks, and then merging them back together.

Quicksort is another recursive approach, but it works differently. Let’s first examine its operation at a high level, and then break it down further.

Like Mergesort, Quicksort is also based on another building block: partitioning. Let’s see how that works:

You’ll get to complete `partition`

on our next homework!
But we can at least experiment with it using the method built-in to our playground:

// Experiment with partition

Quicksort

Next, first we’ll implement Quicksort. Then we’ll analyze its performance!

Implementation

Next, let’s build a recursive sorting algorithm based on `Partitioner.partition`

!
Once we have a partition method, completing the implementation is quite straightforward!

// Quicksort

Performance Analysis

Next, let’s use the Quicksort implementation we completed above to experiment with its performance. Surprises are in store!

// Quicksort Performance Analysis

import kotlin.random.Random

fun randomIntArray(length: Int): Array<Int> {

return Array<Int>(length) { Random.nextInt(128) }

}

println(randomIntArray(8).contentDeepToString())

What’s going on here? Let’s consider things visually.

Sorting Algorithm Review

Let’s review the sorting algorithms we’ve covered together:

Let’s review salient aspects of sorting performance. Specifically: best and worst case inputs and runtime, and memory usage.

Sorting Tradeoffs

Sorting algorithms represent a fascinating set of tradeoffs between different performance attributes. For example:

**Have a very small array to sort?**Insertion sort can actually outperform other algorithms on small arrays, because the recursive calls needed by Mergesort and Quicksort have some overhead associated with them.**Want predictable performance?**Mergesort has your back. O(n log n), O(n log n), O(n log n). Sometimes it’s actually more important that a sort take a predictable amount of time than that it be completely optimal.**Short on space?**Quicksort’s space utilization is substantially smaller than Mergesort, and with good pivot selection it can achieve similar performance.

Timsort, the default sorting algorithm used by several languages including Python and Java, actually combines elements of both insertion sort and Mergesort, in addition to some other tricks.

Sorting Stability

As a final note, let’s discuss sort algorithm *stability*.
Stability is a desirable property of sorting algorithms.
It means that items with equal values will not change positions while the array is sorted.

Why is stability desirable? Because it allows us to run a sorting algorithm multiple times on complex data and produce meaningful results.

For example, imagine that want a list of restaurants sorted first by cuisine and then by name.
Assuming our sorting algorithm is *stable*, we can accomplish this by first sorting the list by name and then by cuisine.
However, if the sorting algorithm in *unstable* that second sort by cuisine will destroy the results of the sort by name, and render the combination meaningless.

Created By: Geoffrey Challen

/ Version: `2020.6.0`

Create a method
`fun partition(value: IntArray?)`

that returns the input array partitioned using the *first*
array value as the pivot. All values smaller than the pivot should precede it in the array,
and all values larger than or equal to the pivot should follow it. Your method should return the
index of the pivot value. If the array is `null`

or empty you should return -1.

Need more practice? Head over to the practice page.