/*
============================================================
Title: Rearranging a Vector into Zig-Zag Order in Rust
Pattern: a < b > c < d > e < f > g ...
============================================================
Goal:
Given a vector of numbers, rearrange it so that:
v[0] < v[1] > v[2] < v[3] > v[4] ...
Example:
Input : [4, 3, 7, 8, 6, 2, 1]
Output: [3, 7, 4, 8, 2, 6, 1]
Approach:
Perform a single pass through the vector.
At each index i:
- If i is even, ensure:
v[i] <= v[i + 1]
- If i is odd, ensure:
v[i] >= v[i + 1]
If a condition is violated, swap the adjacent elements.
Advantages:
- O(n) time complexity
- O(1) extra space
- Simple and idiomatic Rust
*/
fn zig_zag<T>(data: &mut [T])
where
T: PartialOrd,
{
// `less` indicates the relation expected between
// the current element and the next one.
//
// true => current < next
// false => current > next
let mut less = true;
for i in 0..data.len().saturating_sub(1) {
let should_swap =
(less && data[i] > data[i + 1]) ||
(!less && data[i] < data[i + 1]);
if should_swap {
data.swap(i, i + 1);
}
// Alternate expected relation:
// < then > then < then > ...
less = !less;
}
}
fn main() {
let mut values = vec![3, 5, 1, 7, 9, 6, 4, 2];
println!("Original vector: {:?}", values);
zig_zag(&mut values);
println!("Zig-zag vector : {:?}", values);
}
/*
run:
Original vector: [3, 5, 1, 7, 9, 6, 4, 2]
Zig-zag vector : [3, 5, 1, 9, 6, 7, 2, 4]
*/