How to Do Bubble Sort in Rust

Bubble sort is a popular sorting algorithm that compares the adjacent elements in a list and swaps them if they are not in the specified order.

This tutorial will go through how to implement the bubble sort algorithm in Rust with the help of code examples.

---

How Bubble Sort Works

The bubble sort algorithm, also known as sinking sort, is the most straightforward sorting algorithm. The algorithm goes through an array repeatedly, compares adjacent elements and swaps them if they are out of order. We can use the bubble sort algorithm to sort in ascending (largest element last) or descending order (largest element first). Let’s look at an example of how the bubble sort algorithm can sort an array of five numbers in ascending order.

First Iteration

1. Starting from the first element in the array, compare the first and second elements.
2. If the first element is greater than the second element, swap the elements.
3. Compare the second and third elements, swap them if they are not in order.
4. Proceed with the above process until the last element.

Let’s look at the first pass, which means the algorithm goes over the array:

The above image shows how the array looks after each step in the pass over the array. Note how the largest number in the array bubbles to the top of the array. Let’s look at the second pass:

The algorithm only swaps elements if the right element is less than the left element in the array. Finally, we have the third pass:

The number of passes over the array is dependent on the array size and the arrangement of the array elements.

Bubble Sort Pseudocode

Let’s look at the pseudo-code describing the bubble sort algorithm.

procedure bubbleSort(A : list of sortable items)
    n := length(A)
      for i := 0 to n-1 inclusive do
         for j := 0 to n-i-1 inclusive do
            // Element comparison
             if A[j] > A[j+1] then
                 // If not in the correct order then swap the elements
                 swap(A[j], A[j+1])
             end if
        end for
    end for
end procedure

What is Rust?

Rust is a statically-typed, low-level programming language designed for memory safety and performance. The language provides solutions to many problems in C/C++, such as segmentation faults, garbage collection, and data races.

Optimized Bubble Sort in Rust

Let’s look at the function to perform Bubble sort in Rust. We will save this function in a module called bubble.rs. The logic of the code is as follows:

pub fn bubble_sort_optimized(arr: &mut [i32]) {

    let mut new_len: usize;

    let mut len = arr.len();

    // Outer loop

    loop {

        new_len = 0;

        // Inner loop

        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;

    }

}

We introduce a variable new_len initialized to 0. We set new_len to the index of the first element if we swap the elements after comparison. Otherwise, we leave it as 0.

We use an if statement to check the value of new_len. If we get 0, we break out of the loop, ensuring that we do not compare already sorted elements.

Let’s look at the main function. In the following code, we attach the bubble module and use crate to import the bubble_sort_optimized function. We then define an array of numbers to sort in ascending order and pass it to the bubble sort function.

mod bubble;

use std::time::Instant;

use crate::bubble::*;

fn main() {

    println!("Sort numbers ascending");

    let mut numbers = [2, 60, -1, -30, 0, 99, 2, 83, 700, 5];

    print!("Before: {:?}", numbers);

    bubble_sort_optimized(&mut numbers);

    println!("After: {:?}\n", numbers);

}

How to Compile in Rust

We can compile our rust code by passing the main.rs code to the Rust compile rustc. We can specify the name of our executable using the -o flag.

rustc -O main.rs -o rust.exe

./rust.exe

Let’s run the code to see what happens:

Sort numbers ascending
Before: [2, 60, -1, -30, 0, 99, 2, 83, 700, 5]
After: [-30, -1, 0, 2, 2, 5, 60, 83, 99, 700]

We successfully sort the array of numbers in ascending order.

Rust Sorting Benchmark

Sorting with 50,000 Elements Ten Times with Rust

Let’s scale the application of the optimized Bubble Sort algorithm. We will define an array of 50,000 numbers and pass it to the Bubble sort algorithm, and we will repeat the sorting of the array ten times. Let’s look at the code:

mod bubble;

use std::time::Instant;

use crate::bubble::*;

fn main() {
  
    let mut array = [0_i32; 50 * 1000];

    let len = array.len();

    for i in 0..len {

        array[i] = len as i32 - i as i32;

    }

    let rerun = 10;

    let start = Instant::now();

    for _q in 0..rerun {

       bubble_sort_optimized(&mut array);

    }

    let duration = start.elapsed();

    println!("Took: {:?} to sort {:?} elements {:?} times", duration, array.len(), rerun);
    
}

Note we are importing the same bubble_sort_optimized function into the main code. We use the Instant struct from the std::time module to quantify the time to sort the array ten times. Let’s compile and run the code to get the timing result:

rustc -O main.rs -o rust.exe
./rust.exe

Took: 1.606648366s to sort 50000 elements 10 times

Bubble Sort Complexity

Time Complexity

Bubble sort employs two loops: an inner loop and an outer loop. The number of comparisons made is:

(n - 1 ) + (n - 2) + (n - 3) + ... + 1 = n(n-1)/2

Which approximates to , therefore the complexity of the bubble sort algorithm is .

Bubble Sort Worst Case Time Complexity

• Outer loop runs O(n) times
• As a result the worst-case time complexity of bubble sort is .
• This is also the average case complexity, in other words, the elements of the array are in jumbled order and are neither ascending nor descending. This complexity occurs because irrespective of the arrangement of elements, the number of comparisons is the same.

Bubble Sort Best Case Time Complexity

• If the list is already sorted, outer loop runs O(n) times.

Space Complexity

• Space complexity is O(1) because we use an extra variable temp for swapping.
• In the optimized bubble sort algorithm we use two extra variables temp and is_swapped. Therefore the space complexity is O(2).

Summary

Congratulations on reading to the end of this tutorial! We went through how to do Bubble Sort with Rust.

For further reading on the implementation of Bubble Sort, go to the articles:

• How to do Bubble Sort in Python
• How to Do Bubble Sort in C++

For further reading on Rust, go to the articles:

• How to Concatenate Strings in Rust.
• How to Split a String in Rust
• How to Convert String to Integer and Float in Rust

Have fun and happy researching!