Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list.

Here's an example with an array of 5 elements: [5, 3, 8, 4, 2]. I'll describe each iteration of the bubble sort algorithm on this array.

1. Initial Array

    [5, 3, 8, 4, 2]
   

2. First Pass

   • Compare 5 and 3, swap because 5 > 3.

       [3, 5, 8, 4, 2]
     

   • Compare 5 and 8, no swap because 5 < 8.

       [3, 5, 8, 4, 2]
     

   • Compare 8 and 4, swap because 8 > 4.

       [3, 5, 4, 8, 2]
     

   • Compare 8 and 2, swap because 8 > 2.

       [3, 5, 4, 2, 8]
     

3. Second Pass

   • Compare 3 and 5, no swap because 3 < 5.

       [3, 5, 4, 2, 8]
     

   • Compare 5 and 4, swap because 5 > 4.

       [3, 4, 5, 2, 8]
     

   • Compare 5 and 2, swap because 5 > 2.

       [3, 4, 2, 5, 8]
     

   • Compare 5 and 8, no swap because 5 < 8.

       [3, 4, 2, 5, 8]
     

4. Third Pass

   • Compare 3 and 4, no swap because 3 < 4.

       [3, 4, 2, 5, 8]
     

   • Compare 4 and 2, swap because 4 > 2.

       [3, 2, 4, 5, 8]
     

   • Compare 4 and 5, no swap because 4 < 5.

       [3, 2, 4, 5, 8]
     

   • Compare 5 and 8, no swap because 5 < 8.

       [3, 2, 4, 5, 8]
     

5. Fourth Pass

   • Compare 3 and 2, swap because 3 > 2.

       [2, 3, 4, 5, 8]
     

   • Now, the array is already sorted, but the algorithm does not know it yet and will go through the entire array one more time without any swap.

After these passes, the array is sorted in ascending order. The bubble sort algorithm is not very efficient for large lists, but its simplicity makes it easy to understand and implement.

Here's the pseudo-code for the Bubble Sort algorithm:

function bubbleSort(array)
    n = length(array)
    repeat
        swapped = false
        for i = 1 to n-1
            if array[i] > array[i+1]
                swap(array[i], array[i+1])
                swapped = true
        n = n - 1
    until not swapped
end function

Explanation:

• n = length(array): This sets n to the size of the array. This is used to control the number of times the array is iterated over.

• repeat...until not swapped: This loop continues to run the sorting process until no more swaps are made, indicating the array is sorted.

• for i = 1 to n-1: This loop iterates over the array. The range is from 1 to n-1 because in each iteration, the inner loop will compare the current element with the next element.

• if array[i] > array[i+1]: This conditional checks if the current element is greater than the next element.

• swap(array[i], array[i+1]): If the condition is true, the current element and the next element are swapped.

• swapped = true: This flag is set to true to indicate that a swap has occurred.

• n = n - 1: This decreases the value of n. Since the largest element in the unsorted part of the array is moved to its correct position at the end of each outer loop iteration, we can ignore this element in the next iteration.

Here's the C code for the Bubble Sort algorithm:

#include <stdio.h>

void bubbleSort(int array[], int n) {
    int i, j, temp;
    int swapped;

    for (i = 0; i < n-1; i++) {
        swapped = 0;
        for (j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                swapped = 1;
            }
        }

        // If no two elements were swapped by inner loop, then break
        if (swapped == 0) {
            break;
        }
    }
}

int main() {
    int array[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(array)/sizeof(array[0]);
    bubbleSort(array, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", array[i]);
    printf("\n");
    return 0;
}

Explanation of the Code:

1. Include the Standard IO Library:

    #include <stdio.h>
   

   This includes the Standard Input Output library for using the printf function.

2. The bubbleSort Function:

   • Function Definition:

       void bubbleSort(int array[], int n)
     

     This function takes an array and its size n as arguments.

   • Loop through the Array:

       for (i = 0; i < n-1; i++)
     

     This loop runs n-1 times. In each iteration, it moves the largest element in the unsorted part of the array to its correct position.

   • Track if a Swap Occurred:

       swapped = 0;
     

     This flag is used to track if any swap has happened in the inner loop. If no swap occurs, the array is already sorted.

   • Inner Loop for Comparison and Swapping:

       for (j = 0; j < n-i-1; j++)
     

     This loop does the actual comparison and swapping. It compares each element with its next element and swaps them if they are in the wrong order.

   • Swapping Elements:

       temp = array[j];
       array[j] = array[j+1];
       array[j+1] = temp;
       swapped = 1;
     

     If the current element (array[j]) is greater than the next element (array[j+1]), they are swapped.

   • Break if No Swap:

       if (swapped == 0) {
           break;
       }
     

     If no swap occurs in the inner loop, the array is already sorted, and the function exits the outer loop.

3. The main Function:

   • Define and Initialize the Array:

       int array[] = {64, 34, 25, 12, 22, 11, 90};
     

     This is the array that will be sorted.

   • Calculate the Size of the Array:

       int n = sizeof(array)/sizeof(array[0]);
     

     The size of the array is calculated by dividing the total size of the array by the size of one element.

   • Call bubbleSort and Print the Sorted Array:

       bubbleSort(array, n);
     

     This sorts the array. The sorted array is then printed using a loop.

The complexity analysis of the Bubble Sort algorithm involves evaluating its time and space complexity. Let's break down each aspect:

Time Complexity

1. Worst and Average Case (O(n²)): In the worst case, the array is in reverse order, and we need to make n-1 passes through the array, where n is the number of elements. During each pass, nearly n comparisons and swaps are made. Therefore, the worst-case time complexity is O(n²).

   The average case is also O(n²), assuming that the elements are in random order. This is because, on average, half of the comparisons will require a swap, leading to a quadratic number of operations.

2. Best Case (O(n)): In the best case, the array is already sorted, and no swaps are needed. The algorithm will still make one pass through the array to confirm that no swaps are required, resulting in a linear time complexity O(n). This is an optimized behavior of the provided Bubble Sort implementation, which checks if any swaps have been made in each pass.

Space Complexity

1. Space Complexity (O(1)): Bubble Sort is an in-place sorting algorithm. It does not require any extra space except for a small constant amount (for variables like i, j, temp, and swapped). Therefore, its space complexity is O(1), which is constant space complexity.

Important to note

• Worst-Case Time Complexity: O(n²)

• Average-Case Time Complexity: O(n²)

• Best-Case Time Complexity: O(n)

• Space Complexity: O(1)

Bubble Sort is not suitable for large datasets due to its quadratic time complexity in the average and worst cases. However, its simplicity and the fact that it requires only a constant amount of additional memory space make it useful for small datasets or for educational purposes to demonstrate basic sorting principles.