1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//! Cycle Sort (Generic, Production-Grade)
//!
//! Sorts a mutable slice in ascending order using the Cycle Sort algorithm.
//!
//! # Type Parameters
//! * `T`: The element type. Must implement `Ord` + `PartialEq`.
//!
//! # Example
//! ```rust
//! use lunaris_engine::list::cycle_sort::cycle_sort;
//! let mut arr = vec![4, 10, 3, 5, 1];
//! cycle_sort(&mut arr);
//! assert_eq!(arr, vec![1, 3, 4, 5, 10]);
//! ```
/// Cycle Sort: O(n^2) time, O(1) space, not stable. Minimizes writes.
/// Safe, classic Cycle Sort: No unsafe code, correct for all input.
pub fn cycle_sort<T: Ord + PartialEq + Copy>(arr: &mut [T]) {
let n = arr.len();
for cycle_start in 0..n.saturating_sub(1) {
let mut item = arr[cycle_start];
let mut pos = cycle_start;
for val in arr.iter().skip(cycle_start + 1) {
if *val < item {
pos += 1;
}
}
if pos == cycle_start {
continue;
}
while item == arr[pos] {
pos += 1;
}
if pos != cycle_start {
std::mem::swap(&mut arr[pos], &mut item);
}
while pos != cycle_start {
pos = cycle_start;
for val in arr.iter().skip(cycle_start + 1) {
if *val < item {
pos += 1;
}
}
while item == arr[pos] {
pos += 1;
}
if item != arr[pos] {
std::mem::swap(&mut arr[pos], &mut item);
}
}
}
}