i want to write a sort algo. I think it did work, but when it comes to a big array which has so many number that would make the stack overflow. i had used two recursion, now i have changed one into loop, but i cannot change the other one into loop, could u help me? THX!
pub struct Solution;
impl Solution {
// this method should be use
pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
Self::sort(&mut nums);
nums
}
fn sort(v: &mut [i32]) {
// used in the inner while loop.
let mut len = v.len();
let mut pd = v;
// let mut len2;
// let mut pd2;
let mut il;
let mut ir;
let mut mark;
while len > 1 {
il = 0;
ir = pd.len() - 1;
mark = WhoMove::Right;
while il < ir {
match pd[il] <= pd[ir] {
true => Self::mo(mark, &mut il, &mut ir),
false => {
let temp = pd[il];
pd[il] = pd[ir];
pd[ir] = temp;
mark.turn_over()
}
}
}
// recursion here
// can it be changed into a loop?
Self::sort(&mut pd[0..il]);
pd = &mut pd[il + 1..];
len = pd.len();
}
}
// move the pointer which should be moved, to make the two index closer.
fn mo(wm: WhoMove, il: &mut usize, ir: &mut usize) {
match wm {
WhoMove::Left => *il += 1,
WhoMove::Right => *ir -= 1,
}
}
}
#[derive(Copy, Clone)]
enum WhoMove {
Left,
Right,
}
impl WhoMove {
// change the moving pointer
fn turn_over(&mut self) {
match self {
WhoMove::Left => *self = WhoMove::Right,
WhoMove::Right => *self = WhoMove::Left,
}
}
}
···