Bubble Sort

Bubble sort is one of the simplest sorting algorithms. While it is easy to understand and implement, it is less efficient than some of the faster sorting algorithms available.

Algorithm

Assuming we want to sort an array in ascending order, bubble sort works like this:

1. The algorithm starts by comparing the first two elements of the array.
   • If the first element is greater than the second element, we swap them.
   • If they are in the correct order, no change is made.
2. The algorithm then moves to the next pair of elements (the second and third elements) and compares them in the same way.
3. This process continues, comparing and swapping adjacent elements until we reach the end of the array.
4. At the end of the first iteration, the largest element in the array will be in its correct position at the end.
5. The algorithm then starts the next iteration, repeating steps 1 to 3, but excluding the last element, as it is already in its correct position.
6. Each iteration moves the next largest element to its correct position at the end of the remaining unsorted portion of the array.
7. The iterations continue until a pass is completed without any swaps, indicating that the array is completely sorted.

To sort the array in descending order, use a 'less than' comparison instead of 'greater than', moving the smaller elements toward the end of the array.

---

Walkthrough

Let's walk through each pass of an example array: [5, 3, 8, 7, 2] to sort it in ascending order:

Pass 1

• Step 1: Starting with the first two elements, 5 and 3, we compare them. Since 5 is greater than 3, we swap their positions. The array now becomes [3, 5, 8, 7, 2].

• Step 2: Moving to the next pair, 5 and 8, we observe that they are already in the correct order. No swap is needed. The array remains [3, 5, 8, 7, 2].

• Step 3: Comparing 8 and 7, we find that they are in the wrong order. We swap them, resulting in [3, 5, 7, 8, 2].

• Step 4: Finally, numbers 8 and 2 are in the wrong order, so we swap them, resulting in [3, 5, 7, 2, 8].

After this initial pass, the largest element, 8, is at the end of the array. We now repeat these steps, omitting one more element from the end each time until no more swaps are made during a pass, ensuring that the array is fully sorted. For our second pass, we no longer need to compare against 8, because this first pass has guaranteed that the largest element made it to the end.

Let's continue with the second pass through the array.

Pass 2

• Step 1: Comparing the first and second elements, 3 and 5. Since they are in the correct order, no swap is needed. The array remains [3, 5, 7, 2, 8].

• Step 2: Comparing the second and third elements, 5 and 7. They are, as well, in the correct order. The array remains [3, 5, 7, 2, 8].

• Step 3: Comparing the third and fourth elements, 7, and 2, we see that 7 is greater than 2, swap them. The array becomes [3, 5, 2, 7, 8].

We don't need to compare the last two elements as the number 8 is already at its correct position. Two passes through the array are complete. The second largest element, 7, is now in its correct position.

Moving on to the third pass through the array.

Pass 3

• Step 1: Starting with the first two elements 3 and 5, we compare them. Since they are in the correct order, no swap is needed. The array remains [3, 5, 2, 7, 8].

• Step 2: Moving on to the next two elements, 5 and 2, we compare them. Since 5 is greater than 2, we swap their positions. The array now becomes [3, 2, 5, 7, 8].

We don't need to compare other elements as they are already in the correct order. Three passes through the array are complete. The third largest element, 5, is now in its correct position.

Moving on to the fourth and final pass.

Pass 4

• Step 1: Starting with the updated array [3, 2, 5, 7, 8], we compare the first pair 3 and 2. They are in the wrong order, so we will swap them. The array becomes [2, 3, 5, 7, 8].

Every other element in the array is already in its correct place. This means that the array is now fully sorted in ascending order: [2, 3, 5, 7, 8].

Note that we would have ended the iterations earlier if the given array was nearly sorted. However, since this wasn't the case, we had to perform four passes through it.

---

Code Implementation

Here's the code implementation of the bubble sort algorithm in JavaScript:

function bubbleSort(arr) {
  const len = arr.length;

  for (let i = 0; i < len - 1; i++) {
    // Flag to track if any swaps were made
    let swapped = false;

    // Last i elements are already in place
    for (let j = 0; j < len - 1 - i; j++) {
      // Check if the element in the current iteration
      // is greater than the one in the next iteration
      if (arr[j] > arr[j + 1]) {
        // Swapping elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    if (!swapped) {
      // If no swaps were made in this iteration, the array is already sorted
      break;
    }
  }

  return arr;
}

const array = [5, 3, 8, 7, 2];
console.log(bubbleSort(array)); // Output: [2, 3, 5, 7, 8]

Bubble sort has a time complexity of O(N^2), where N is the number of elements in the array. This means that the time it takes to sort the array grows quadratically with the input size.

Due to its nested loop structure, bubble sort is not considered efficient for large datasets. It performs a comparison and potential swap for every pair of elements in the array, leading to many unnecessary operations. Additionally, if the swapping or comparison operations are costly, the inefficiency of bubble sort becomes more pronounced.

Let's further explain this:

• In certain cases, the comparison operation can be computationally expensive. For instance, if the elements being compared involve complex calculations, database queries, network requests, or accessing external resources, the time required for comparisons can be substantial.
• Swapping elements in memory can also be costly if the elements are large in size. For example, if the array elements are large arrays or structures, performing swaps that involve moving significant amounts of data in memory can result in performance overhead. This consideration does not apply to languages where large elements are swapped by reference rather than by value.

However, when the array is already sorted or nearly sorted, the number of passes through the array will be significantly reduced. As soon as we iterate through the array without performing any swaps, we know that the array is already sorted. This means that in the best-case scenario, its time complexity is O(N), as we only need to perform one pass in a sorted array. This makes bubble sort a viable choice in practical scenarios involving nearly sorted arrays due to its simple implementation.