Sorting

Usually the first algorithm in almost every major course is insertion sort, but they're boring, and hard to start with. Instead, we start with bubble sort.

Definition of a sorted array

Generally, in a sorted array , for any given , .

Bubble Sort

Bubble sort is a simple algorithm that works by swapping adjacent elements if they are out of order. This is done until the array is sorted.

[2, 6, 1, 3, 5]
 ^  ^
 |  |
 i  i + 1
[2, 6, 1, 3, 5]
    ^  ^
    |  |
    i  i + 1
[2, 1, 6, 3, 5]
       ^  ^
       |  |
       i  i + 1
[2, 1, 3, 6, 5]
          ^  ^
          |  |
          i  i + 1
[2, 1, 3, 5, 6]
[1, 2, 3, 5 | 6] << sorted

This is one iteration, and it pushes the largest element to the end. This is repeated until the array is sorted.

[2, 6, 1, 3, 5]
[2, 1, 3, 5, 6]
[1, 2, 3, 5, 6]

Time complexity

The first iteration requires comparisons, the second requires , and so on. This means that the total number of comparisons is:

This is because we drop constants and lower-order terms.

Implementation

pub fn bubble_sort<T: PartialOrd + Clone>(array: &[T]) -> Vec<T> {
    let mut result: Vec<T> = array.into();
    for i in 0..result.len() {
        for j in 0..(result.len() - 1 - i) {
            if result[j] > result[j + 1] {
                result.swap(j, j + 1)
            }
        }
    }
    result
}