# Exercise 9

Download and extract the code skeleton for this exercise. As last week, the code includes an outline of how to organize your work and some tests.

## Iterating Vectors

I see four methods that can be used to iterate through a `Vec`

:

`.into_iter()`

because`Vec`

implements`IntoIter`

. [**Edit 07/23:**I had intended this to be "`IntoIterator for Vec<T, A>`

", but it is also implemented for`&Vec`

and`&mut Vec`

. Since the instruction was ambiguous, answering for any of those is fine.]`.iter()`

because`Vec`

can be (implicitly) dereferenced to an array slice, and array slices implement`.iter()`

.`.iter_mut()`

, also from dereferencing to array slices.`.drain(..)`

[The`..`

is a`RangeFull`

object that expresses "all elements".]

Why so many? In a file `iter.txt`

, for each one of these, briefly describe:

- What is the receiver argument it takes? In other words, does it move, borrow, or mutably-borrow
`self`

? - What does it return? (In each case, it returns something that implements
`Iterator`

.) - What type of values are produced by the iterator, i.e. the
`v`

if we do “`for v in vec.this_method()`

” or similar? - Give a brief sentence describing why it's necessary or what it would be used for.

## Rational Numbers, again

Let's return to our `Rational`

struct from last week. We would like to also implement:

- From last week: the struct itself,
`::new`

,`From<i64>`

,`.reduce()`

. `fmt::Display`

so we can print a nice format, the numerator and denominator, separated by a slash:`3/4`

or`-6/8`

or similar. [Hint.]`From<Rational> for f64`

so we can convert to floating point values.

## Test It

In `rational_tests.rs`

, create some tests of the new and old `Rational`

behaviour. Some examples were provided last week, and you can use those as a starting point.

In particular, check that with a `Rational`

value `r`

, you can do both `let f = f64::from(r)`

and `let f: f64 = r.into()`

. In the Rust docs for `From`

and `Into`

, try to figure out how you just implemented `Into<f64> for Rational`

without writing any code.

## Sorting

In `sort.rs`

, write a function `quicksort_partial(v, left, right)`

that sorts `v[left..=right]`

in-place with the Quicksort algorithm, using the provided `partition`

function (which implements in-place Lomuto partitioning, returning the final position of the pivot).

Write a function `quicksort(v)`

that sorts an entire vector (by calling `quicksort_partial`

with appropriate bounds).

For both `quicksort_partial`

and `quicksort`

, I have deliberately omitted the types of the arguments from this description: figuring them out is part of the exercise. Your implementation should work for as many types as possible (given the restrictions of the algorithm, and provided `partition`

implementation).

The provided `sort_tests.rs`

contains some tests of the sorting algorithm. No additions are necessary in this file (unless you want to test something else to convince yourself your code is correct).

### Tuning Quicksort

Quicksort is actually *slower* than insertion sort for small arrays: the mechanics of Quicksort only make sense for larger arrays.

Update your `quicksort_partial`

function so that for lengths below `INSERTION_SORT_CUTOFF`

, it calls `insertion_sort`

instead of recursing to `quicksort_partial`

.

The provided benchmark functions will time your Quicksort: adjust `INSERTION_SORT_CUTOFF`

to a reasonable value (of which there is a fairly wide range).

The built-in sorting implementations are included in the benchmarks: assuming your results are the same as mine, we're slower than `Vec.sort`

but reasonably close, which is probably the best we could hope for. `Vec.sort_unstable`

is much faster again: `.sort`

is a highly-optimized merge sort (similar to Python's Timsort), and `.sort_unstable`

is a highly optimized Quicksort.

## Submitting

Submit your files through CourSys for Exercise 9.