How to rearrange a vector into a zig-zag pattern (a < b > c < d > e < f > g) in Rust

1 Answer

0 votes
/*
    ============================================================
    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]

*/

 



answered Oct 9 by avibootz

Related questions

...