Table of content

Bubble Sort in Rust

Bubble sort is one of the simplest sorting methods. Because each element will be like a bubble when sorting, one by one will pop up the top of the sequence, hence the name. Because of its simple and easy to understand, the name is interesting, often used as the first entry method for learning. However, its efficiency is not good, not even as the insertion sort for quadratic time.

The principle of Bubble sort is very ordinary, that is, the adjacent two elements are compared with each other, and if the size order is wrong, the position is replaced. Compare to the next pair.

The characteristics of Bubble sort are as follows:
  • Also known as sinking sort.
  • Stable sorting : Elements of the same key value, the relative position does not change after sorting.
  • In-place sorting : no additional storage space to sort.
step
  • Compare two adjacent elements. If the first element is larger than the next element, replace the position of both.
  • Step one is performed on the adjacent elements in order until the top of the sequence is reached, at which point the top element is sorted.
  • Repeat the entire sequence iteration of steps 1 - 2 until no element permutation is performed in any of the iterations.
/// Bubble sort

pub fn bubble_sort(arr: &mut [i32]) { let mut swapped = true; while swapped { // No swap means array is sorted. swapped = false; for i in 1..arr.len() { if arr[i - 1] > arr[i] { arr.swap(i - 1, i); swapped = true } } } }

/// Optimized bubble sort

/// Memorize last swapped index to avoid unnecessary check.

pub fn bubble_sort_optimized(arr: &mut [i32]) { let mut new_len: usize; let mut len = arr.len(); loop { new_len = 0; for i in 1..len { if arr[i - 1] > arr[i] { arr.swap(i - 1, i); new_len = i; } } if new_len == 0 { break; } len = new_len; } }

#[cfg(test)]
mod base { use super::*; base_cases!(bubble_sort); }

#[cfg(test)]
mod optimized { use super::*; base_cases!(bubble_sort_optimized); }

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions