Crust of Rust: Sorting Algorithms

2024-03-04 2024-03-18 约 2100 字预计阅读 5 分钟

In this Crust of Rust episode, we implement some common sorting algorithms in Rust. This episode doesn't aim to explain any single concept, but rather showcase what writing “normal” Rust code is like, and explaining various “odd bits” we come across along the way. The thinking here is that sorting algorithms are both familiar and easy to compare across languages, so this might serve as a good bridge into Rust if you are familiar with other languages.

整理自 John Gjengset 的影片

问题

You may note that the url of this posy is “orst”. Why was it given this name?

Since “sort” when sorted becomes “orst”. 🤣

影片注解

Total order vs Partial order

Wikipedia: Total order
Wikipedia: Partial order
Stack Overflow: What does it mean by “partial ordering” and “total ordering” in the discussion of Lamport's synchronization Algorithm?

This definition says that in a total order any two things are comparable. Wheras in a partial order a thing needs neither to be “smaller” than an other nor the other way around, in a total order each thing is either “smaller” than an other or the other way around.

简单来说，在 total order 中任意两个元素都可以进行比较，而在 partial order 中则不一定满足。例如对于集合

$$ S = \{a,\ b,\ c\} $$

在 total order 中，$a, b, c$ 任意两个元素之间都必须能进行比较，而在 partial order 中没有怎么严格的要求，可能只有 $a < b, b < c$ 这两条比较规则。

在 Rust 中，浮点数 (f32, f64) 只实现了 PartialOrd 这个 Trait 而没有实现 Ord，因为根据 IEEE 754，浮点数中存在一些特殊值，例如 NaN，它们是没法进行比较的。出于相同原因，浮点数也只实现了 PartialEq 而没有实现 Eq trait。

Trait & Generic

1
2
3
4
5
6
7
8
9
pub fn sort<T, S>(slice: &mut [T])
where
    T: Ord,
    S: Sorter<T>,
{
    S::sort(slice);
}

sort::<_, StdSorter>(&mut things);

这段代码巧妙地利用泛型 (generic) 来传递了"参数"，当然这种技巧只限于可以通过类型来调用方法的情况 (上面代码段的 S::sort(...) 以及 sort::<_, StdSorter>(...) 片段)。

思考以下代码表示的意义:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub trait Sorter<T> {
    fn sort(slice: &mut [T])
    where
        T: Ord;
}

pub trait Sorter {
    fn sort<T>(slice: &mut [T])
    where
        T: Ord;
}

第一个表示的是有多个 tait，例如 Sorter<i32>, Sorter<i64> 等，第二个表示只有一个 trait Sorter，但是实现这个 trait 需要实现多个方法，例如 sort<i32>, sort<i64> 等，所以第一种写法更加普适和使用 (因为未必能完全实现第二种 trait 要求的所有方法)。

Bubble sort

Wikipedia: Bubble sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
n := length(A)
repeat
    swapped := false
    for i := 1 to n-1 inclusive do
        { if this pair is out of order }
        if A[i-1] > A[i] then
            { swap them and remember something changed }
            swap(A[i-1], A[i])
            swapped := true
        end if
    end for
until not swapped

Insertion sort

Wikipedia: Insertion sort

1
2
3
4
5
6
7
8
9
i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

使用 Binary search algorithm 可以将 insertion sort 的 comparsion 次数降到 $O(nlogn)$，但是 swap 次数仍然是 $O(n^2)$ 🤣

1
2
3
4
5
6
7
8
9
// use binary search to find index
// then use .insert to splice in i
let i = match slice[..unsorted].binary_search(&slice[unsorted]) {
    // [ a, c, e].binary_search(c) => Ok(1)
    Ok(i) => i,
    // [ a, c, e].binary_search(b) => Err(1)
    Err(i) => i,
};
slice[i..=unsorted].rotate_right(1);

match 的内部逻辑也可以改写为 OK(i) | Err(i) => i

Selection sort

Wikipedia: Selection sort

引用

There are many different ways to sort the cards. Here’s a simple one, called selection sort, possibly similar to how you sorted the cards above:

Find the smallest card. Swap it with the first card.
Find the second-smallest card. Swap it with the second card.
Find the third-smallest card. Swap it with the third card.
Repeat finding the next-smallest card, and swapping it into the correct position until the array is sorted.

source

使用函数式编程可以写成相当 readable 的程式码，以下为获取 slice 最小值对应的 index:

1
2
3
4
5
6
let smallest_in_rest = slice[unsorted..]
                .iter()
                .enumerate()
                .min_by_key(|&(_, v)| v)
                .map(|(i, _)| unsorted + i)
                .expect("slice is not empty");

Quicksort

Wikipedia: Quicksort

可以通过 extra allocation 和 in-place 两种方式来实现 quicksort，其中 extra allocation 比较好理解，in-place 方式的 pseudocode 如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
Quicksort(A,p,r) {
    if (p < r) {
       q <- Partition(A,p,r)
       Quicksort(A,p,q)
       Quicksort(A,q+1,r)
    }
}
Partition(A,p,r)
    x <- A[p]
    i <- p-1
    j <- r+1
    while (True) {
        repeat { j <- j-1 }
        until (A[j] <= x)
        repeat { i <- i+1 }
        until (A[i] >= x)
        if (i < j) swap(A[i], A[j])
        else       return(j)
    }
}

source

method slice::split_at_mut

实现 Quick sort 时使用了 split_at_mut 来绕开引用检查，因为如果你此时拥有一个指向 pivot 的不可变引用，就无法对 slice 剩余的部分使用可变引用，而 split_at_mut 则使得原本的 slice 被分为两个可变引用，从而绕开了之前的单一引用检查。

后面发现可以使用更符合语义的 split_first_mut，当然思路还是一样的

注意

我个人认为实现 Quick sort 的关键在于把握以下两个 invariants:

left: current checking index for element which is equal or less than the pivot
right: current checking index for element which is greater than the pivot

即这两个下标对应的元素只是当前准备检查的，不一定符合元素的排列规范，如下图所示:

1
2
3
4
[ <= pivot ] [ ] [ ... ] [ ] [ > pivot ]
              ^           ^
              |           |
            left        right

所以当 left == right 时两边都没有对所指向的元素进行检查，分情况讨论 (该元素是 $<= pivot$ 或 $> pivot$) 可以得出: 当 left > right 时，right 指向的是 $<= pivot$ 的元素，将其与 pivot 进行 swap 即可实现 partition 操作。(其实此时 left 指向的是 $> pivot$ 部分的第一个元素，right 指向的是 $<= pivot$ 部分的最后一个元素，但是需要注意 rest 与 slice 之间的下标转换)

Benchmark

通过封装类型 SortEvaluator 及实现 trait PartialEq, Eq, PartialOrd, Ord 来统计排序过程中的比较操作 (eq, partial_cmp, cmp) 的次数。

Stack Overflow: Why can't the Ord trait provide default implementations for the required methods from the inherited traits using the cmp function?

R and ggplot2

1
2
3
4
5
# install R
$ sudo apt install r-base
# install ggplot2 by R
$ R
> install.packages("ggplot2")

问题

deepin 软件源下载的 R 语言包可能版本过低 (3.5)，可以通过添加库源的方式来下载高版本的 R 语言包:

1.添加 Debian buster (oldstable) 库源到 /etc/apt/sourcelist 里:

1
2
# https://mirrors.tuna.tsinghua.edu.cn/CRAN/
deb http://cloud.r-project.org/bin/linux/debian buster-cran40/

2.更新软件，可能会遇到没有公钥的问题 (即出现下方的 NO_PUBKEY):

1
2
3
4
$ sudo apt update
...
  NO_PUBKEY XXXXXX
...

此时可以 NO_PUBKEY 后的 XXXXXX 就是公钥，我们只需要将其添加一下即可:

1
$ sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys XXXXXX

添加完公钥后再重新更新一次软件源

3.通过指定库源的方式来安装 R (如果未指定库源则还是从默认源进行下载 3.5 版本):

1
2
3
$ sudo apt install buster-cran40 r-base
$ R --version
R version 4.3.3 (2024-02-29)

大功告成，按照上面安装 ggplot2 即可

Homework

信息

实作说明:

添加标准库的 sort_unstable 进入基准测试
将交换操作 (swap) 纳入基准测试
尝试实现 Merge sort
尝试实现 Heapsort

参考资料:

Wikipedia: Merge sort
Wikipedia: Heapsort

Documentations

这里列举视频中一些概念相关的 documentation

学习的一手资料是官方文档，请务必自主学会阅读规格书之类的资料

Crate std

可以使用这里提供的搜素栏进行搜索 (BTW 不要浪费时间在 Google 搜寻上！)

Module std::cmp
- Trait std::cmp::Ord
- Trait std::cmp::PartialOrd
- Trait std::cmp::Eq
- Trait std::cmp::PartialEq
Primitive Type slice
- method slice::sort
- method slice::sort_unstable
- method slice::sort_by
- method slice::sort_by_key
- method slice::swap
- method slice::binary_search
- method slice::rotate_right
- method slice::split_at_mut
- method slice::split_first_mut
- method slice::to_vec
Trait std::iter::Iterator
- method std::iter::Iterator::min
- method std::iter::Iterator::min_by_key
- method std::iter::Iterator::enumerate
Enum std::option::Option
- method std::option::Option::expect
- method std::option::Option::map
Enum std::result::Result
- method std::result::Result::expect
- method std::result::Result::map
Module std::time
- method std::time::Instant::now
- method std::time::Instant::elapsed
- method std::time::Duration::as_secs_f64

Crate rand

Function rand::thread_rng
method rand::seq::SliceRandom::shuffle

References

orst [Github]
Sorting algorithm [Wikipedia]
Timsort [Wikipedia]
Difference between Benchmarking and Profiling [Stack Overflow]