Table of content

Shellsort in Rust

As we all know, Insertion sort is very efficient for sequences that are almost finished sorting. In other words, when element replacement does not need to move too far, it is very efficient. On the other hand, if there is an element that is very far away, the performance will be greatly reduced.

Shellsort uses a gap sequence to sort data according to the specified gap (gap) for insertion sort, so that distant elements can be quickly homing, and the next sorting will be accelerated by the previous sorting result getting closer and closer to completion.

The last gap of Shellsort must be 1, that is, the sorting will degenerate into the insertion sort. At this point, most of the elements are sorted and the insertion sort is very efficient.

The Shell sort features are as follows:
  • Adaptive sorting : Accelerate sorting according to the current data sorting situation. The closer the data is to the sorting, the higher the efficiency.
  • Unstable ordering : After sorting, the relative position of elements of the same key value may change.
  • In-place sorting : no additional storage space to sort.
  • Can be regarded as generalization (Generalizaion) insertion sort .
Steps

Shellsort is divided into two steps:

  • Decide on a set of gap sequences.
  • The iterative gap sequence is used to sort the packets, each time with an interval of insertion sort. That is, each element is compared and replaced with the elements of its adjacent gap.

The last sort (gap = 1) will degenerate into insertion sort, completing the entire sort.

/// Marcin Ciura's gap sequence.

pub const MARCIN_GAPS: [usize; 8] = [701, 301, 132, 57, 23, 10, 4, 1];

/// Shellsort

pub fn shellsort(arr: &mut [i32]) { let len = arr.len(); for gap in MARCIN_GAPS.iter() { let mut i = *gap; // Type of gap is `&usize`. Deference it! while i < len { let mut j = i; while j >= *gap && arr[j - gap] > arr[j] { arr.swap(j - *gap, j); j -= *gap; } i += 1; } } }

#[cfg(test)]

mod base { use super::*; base_cases!(shellsort); }

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions