use std::cmp::Ord;
/// Sorts a mutable slice of elements in-place in non-decreasing order using Gnome Sort.
///
/// # Algorithm Logic (Single Loop)
/// - Advances through the slice using a single loop index position.
/// - Moves forward when adjacent elements are in correct relative order (`data[pos - 1] <= data[pos]`).
/// - When an out-of-order adjacent pair is encountered, swaps the elements using `slice::swap`
/// and steps backward one position to verify order against preceding items.
/// - Time Complexity: O(N) best case (already sorted), O(N^2) worst case.
/// - Space Complexity: O(1) auxiliary space.
///
/// # Generics
/// Works for any type `T` that implements `Ord` (total ordering).
pub fn single_loop_sort<T: Ord>(data: &mut [T]) {
let mut pos = 0;
let len = data.len();
while pos < len {
// Advance if at index 0 or if the adjacent pair is in correct ascending order
if pos == 0 || data[pos] >= data[pos - 1] {
pos += 1;
} else {
// Swap out-of-order adjacent elements using Rust's safe in-place slice swap
data.swap(pos, pos - 1);
pos -= 1;
}
}
}
/// Helper function to format a slice into a space-separated string.
fn format_slice<T: std::fmt::Display>(slice: &[T]) -> String {
slice
.iter()
.map(|item| item.to_string())
.collect::<Vec<_>>()
.join(" ")
}
fn main() {
let mut numbers = [42, -5, 12, 0, 89, -18, 33, 7];
println!("Original array:");
println!("{}", format_slice(&numbers));
single_loop_sort(&mut numbers);
println!("\nSorted array:");
println!("{}", format_slice(&numbers));
}
/*
run:
Original array:
42 -5 12 0 89 -18 33 7
Sorted array:
-18 -5 0 7 12 33 42 89
*/
