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() for Vec<T> because Vec implements IntoIter.
• .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 8.