1
\$\begingroup\$

I followed the Algorithms book implementation of quick sort.

pub fn quick_sort<T: PartialOrd>(a: &mut [T]) {
  shuffle(a);

  let low = 0;
  let high = a.len() - 1;
  inner_quick_sort(a, low, high);
}

pub fn inner_quick_sort<T: PartialOrd>(a: &mut [T], low: usize, high: usize) {
  if high <= low {
    return;
  }
  let j = partition(a, low, high);
  // to avoid overflow;
  let min_j = if j == 0 { 0 } else { j - 1 };
  inner_quick_sort(a, low, min_j);
  inner_quick_sort(a, j + 1, high);
}

pub fn partition<T: PartialOrd>(a: &mut [T], low: usize, high: usize) -> usize {
  let mut i = low + 1;
  let mut j = high;
  loop {
    while a[i] < a[low] {
      i += 1;
      if i == high {
        break;
      }
    }

    while a[j] > a[low] {
      j -= 1;
      if j == low {
        break;
      }
    }
    if i >= j {
      break;
    }

    a.swap(j, i);
    i += 1;
    j -= 1;
  }

  a.swap(low, j);
  j
}

First the review is more than welcome, but I was wondering how can I make it more idiomatic rust?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.