Pure Programmer
Project: Quicksort
The [[Quicksort]] one of the most efficient sorts. It was first introduced by [[Tony Hoare]] in 1959. It can be implemented very easily using recursion. Write a function that takes a list of integers and sorts the list, in place, using a Quicksort. Test the function by creating a random list of integers, print the random list, sort the list, then print out the sorted list. Accept the number of integers to put in the list and the maximum integer to randomly generate on the command line. What is the worst case performance of the Quicksort?
Output
$ rustc Quicksort.rs
error[E0425]: cannot find value `args` in this scope
--> Quicksort.rs:44:5
|
44 | if args.len() != 3 {
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::env::args;
|
error[E0425]: cannot find function `exit` in this scope
--> Quicksort.rs:46:3
|
46 | exit(1);
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::process::exit;
|
error[E0425]: cannot find value `Utils` in this scope
--> Quicksort.rs:48:23
|
48 | let listSize:isize = Utils.stoiWithDefault(args[1], 10);
| ^^^^^ not found in this scope
error[E0425]: cannot find value `args` in this scope
--> Quicksort.rs:48:45
|
48 | let listSize:isize = Utils.stoiWithDefault(args[1], 10);
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::env::args;
|
error[E0425]: cannot find value `Utils` in this scope
--> Quicksort.rs:49:21
|
49 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100);
| ^^^^^ not found in this scope
error[E0425]: cannot find value `args` in this scope
--> Quicksort.rs:49:43
|
49 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100);
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::env::args;
|
warning: denote infinite loops with `loop { ... }`
--> Quicksort.rs:13:2
|
13 | while true {
| ^^^^^^^^^^ help: use `loop`
|
= note: `#[warn(while_true)]` on by default
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:10:25
|
10 | let pivot:isize = list[(high + low) / 2];
| ^^^^^^^^^^^^^^^^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:16:14
|
16 | if !(list[i] < pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:20:14
|
20 | if !(list[j] > pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:25:25
|
25 | let temp:isize = list[j];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:26:8
|
26 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:26:18
|
26 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:27:8
|
27 | list[i] = temp;
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0308]: mismatched types
--> Quicksort.rs:13:2
|
9 | fn partition(list:&mut Vec<isize>, low:isize, high:isize) -> isize {
| ----- expected `isize` because of return type
...
13 | / while true {
14 | | loop {
15 | | i += 1;
16 | | if !(list[i] < pivot) { break; }
... |
27 | | list[i] = temp;
28 | | }
| |_____^ expected `isize`, found `()`
|
note: the function expects a value to always be returned, but loops might run zero times
--> Quicksort.rs:13:2
|
13 | while true {
| ^^^^^^^^^^ this might have zero elements to iterate on
...
23 | return j;
| -------- if the loop doesn't execute, this value would never get returned
= help: return a value for the case when the loop has zero elements to iterate on, or consider changing the return type to account for that possibility
error[E0308]: mismatched types
--> Quicksort.rs:40:27
|
40 | quicksort0(&mut list, 0, list.len() - 1);
| ---------- ^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| arguments to this function are incorrect
|
note: function defined here
--> Quicksort.rs:31:4
|
31 | fn quicksort0(list:&mut Vec<isize>, low:isize, high:isize) -> () {
| ^^^^^^^^^^ ----------
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
40 | quicksort0(&mut list, 0, (list.len() - 1).try_into().unwrap());
| + +++++++++++++++++++++
error[E0425]: cannot find function `irandom` in this scope
--> Quicksort.rs:56:20
|
56 | listToSort.push(irandom(maxInt));
| ^^^^^^^ not found in this scope
error: aborting due to 16 previous errors; 1 warning emitted
Some errors have detailed explanations: E0277, E0308, E0425.
For more information about an error, try `rustc --explain E0277`.
$ rustc Quicksort.rs
error[E0425]: cannot find value `args` in this scope
--> Quicksort.rs:44:5
|
44 | if args.len() != 3 {
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::env::args;
|
error[E0425]: cannot find function `exit` in this scope
--> Quicksort.rs:46:3
|
46 | exit(1);
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::process::exit;
|
error[E0425]: cannot find value `Utils` in this scope
--> Quicksort.rs:48:23
|
48 | let listSize:isize = Utils.stoiWithDefault(args[1], 10);
| ^^^^^ not found in this scope
error[E0425]: cannot find value `args` in this scope
--> Quicksort.rs:48:45
|
48 | let listSize:isize = Utils.stoiWithDefault(args[1], 10);
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::env::args;
|
error[E0425]: cannot find value `Utils` in this scope
--> Quicksort.rs:49:21
|
49 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100);
| ^^^^^ not found in this scope
error[E0425]: cannot find value `args` in this scope
--> Quicksort.rs:49:43
|
49 | let maxInt:isize = Utils.stoiWithDefault(args[2], 100);
| ^^^^ not found in this scope
|
help: consider importing this function
|
7 + use std::env::args;
|
warning: denote infinite loops with `loop { ... }`
--> Quicksort.rs:13:2
|
13 | while true {
| ^^^^^^^^^^ help: use `loop`
|
= note: `#[warn(while_true)]` on by default
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:10:25
|
10 | let pivot:isize = list[(high + low) / 2];
| ^^^^^^^^^^^^^^^^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:16:14
|
16 | if !(list[i] < pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:20:14
|
20 | if !(list[j] > pivot) { break; }
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:25:25
|
25 | let temp:isize = list[j];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:26:8
|
26 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:26:18
|
26 | list[j] = list[i];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0277]: the type `[isize]` cannot be indexed by `isize`
--> Quicksort.rs:27:8
|
27 | list[i] = temp;
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[isize]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<isize>` to implement `Index<isize>`
error[E0308]: mismatched types
--> Quicksort.rs:13:2
|
9 | fn partition(list:&mut Vec<isize>, low:isize, high:isize) -> isize {
| ----- expected `isize` because of return type
...
13 | / while true {
14 | | loop {
15 | | i += 1;
16 | | if !(list[i] < pivot) { break; }
... |
27 | | list[i] = temp;
28 | | }
| |_____^ expected `isize`, found `()`
|
note: the function expects a value to always be returned, but loops might run zero times
--> Quicksort.rs:13:2
|
13 | while true {
| ^^^^^^^^^^ this might have zero elements to iterate on
...
23 | return j;
| -------- if the loop doesn't execute, this value would never get returned
= help: return a value for the case when the loop has zero elements to iterate on, or consider changing the return type to account for that possibility
error[E0308]: mismatched types
--> Quicksort.rs:40:27
|
40 | quicksort0(&mut list, 0, list.len() - 1);
| ---------- ^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| arguments to this function are incorrect
|
note: function defined here
--> Quicksort.rs:31:4
|
31 | fn quicksort0(list:&mut Vec<isize>, low:isize, high:isize) -> () {
| ^^^^^^^^^^ ----------
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
40 | quicksort0(&mut list, 0, (list.len() - 1).try_into().unwrap());
| + +++++++++++++++++++++
error[E0425]: cannot find function `irandom` in this scope
--> Quicksort.rs:56:20
|
56 | listToSort.push(irandom(maxInt));
| ^^^^^^^ not found in this scope
error: aborting due to 16 previous errors; 1 warning emitted
Some errors have detailed explanations: E0277, E0308, E0425.
For more information about an error, try `rustc --explain E0277`.