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.
I see four methods that can be used to iterate through a
IntoIter. [Edit 07/23: I had intended this to be "
IntoIterator for Vec<T, A>", but it is also implemented for
&mut Vec. Since the instruction was ambiguous, answering for any of those is fine.]
Veccan be (implicitly) dereferenced to an array slice, and array slices implement
.iter_mut(), also from dereferencing to array slices.
RangeFullobject 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
- What does it return? (In each case, it returns something that implements
- What type of values are produced by the iterator, i.e. the
vif 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,
fmt::Displayso we can print a nice format, the numerator and denominator, separated by a slash:
-6/8or similar. [Hint.]
From<Rational> for f64so we can convert to floating point values.
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
r, you can do both
let f = f64::from(r) and
let f: f64 = r.into(). In the Rust docs for
Into, try to figure out how you just implemented
Into<f64> for Rational without writing any code.
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).
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
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).
Quicksort is actually slower than insertion sort for small arrays: the mechanics of Quicksort only make sense for larger arrays.
quicksort_partial function so that for lengths below
INSERTION_SORT_CUTOFF, it calls
insertion_sort instead of recursing to
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.
Submit your files through CourSys for Exercise 9.