Bubble Sort

The method operates by exchanging neighboring elements through successive iterations if they are found to be out of sequence. However, this approach is characterized by high time complexity and is deemed unsuitable for handling extensive datasets. Here’s an example implementation of the Bubble Sort algorithm:

Time Complexity: O (n²)

--------------------------------------------------------------
Algorithm: Bubble Sort
--------------------------------------------------------------
Input: arr (an array of integers)
Output: arr (sorted array)

1. n <- length of arr
2. for i <- 0 to n - 1 do
3.     for j <- 0 to n - i - 2 do
4.         if arr[j] > arr[j + 1] then
5.             Swap arr[j] and arr[j + 1]
6.         end if
7.     end for
8. end for
9. return arr
______________________________________________________________

Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Last i elements are already in place
        for j in range(n-i-1):
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

This implementation takes an array arr as input and sorts it in ascending order using the Bubble Sort algorithm. The outer loop runs n times, where n is the length of the array, and the inner loop runs n-i-1 times in each iteration of the outer loop. Within the inner loop, if the current element is greater than the next element, they are swapped. After all iterations are complete, the sorted array is returned.

C

void bubble_sort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        // Last i elements are already in place
        for (j = 0; j < n - i - 1; j++) {
            // Traverse the array from 0 to n-i-1
            // Swap if the element found is greater than the next element
            if (arr[j] > arr[j+1]) {
                // Swap elements
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Rust

fn bubble_sort(mut arr: Vec<i32>) -> Vec<i32> {
    let n = arr.len();
    for i in 0..n {
        // Last i elements are already in place
        for j in 0..n-i-1 {
            // Traverse the array from 0 to n-i-1
            // Swap if the element found is greater than the next element
            if arr[j] > arr[j+1] {
                arr.swap(j, j+1);
            }
        }
    }
    arr
}

Explanation:

• fn bubble_sort(mut arr: Vec) -> Vec defines a function that takes a mutable Vec of i32s as input and returns a sorted Vec of i32s.
• let n = arr.len(); declares a variable n and assigns the length of the input vector arr to it.
• for i in 0..n { … } loops through arr from i = 0 to i = n-1, inclusive.
• for j in 0..n-i-1 { … } loops through arr from j = 0 to j = n-i-2, inclusive. The n-i-1 term comes from the fact that after each iteration of the outer loop (i loop), the largest element in the remaining unsorted elements will be placed at the end of the vector, so we don’t need to compare those elements again.
• if arr[j] > arr[j+1] { arr.swap(j, j+1); } compares adjacent elements arr[j] and arr[j+1] and swaps them if arr[j] is greater than arr[j+1].
• arr is returned after sorting.