Bubble Sort

Mark as Completed

Lesson

Write a function called bubbleSort
that takes an array of integers and sorts it using the bubble sort algorithm. Explain the process of the algorithm, how it works, and why it is considered inefficient. Provide an example of input and output.

Example:

Input: [5, 3, 1, 4, 2]
Output: [1, 2, 3, 4, 5]

Walkthrough

The bubble sort algorithm is the simplest sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order, going through multiple passes through the entire array until the array is in sorted order.

The bubbleSort
function takes an input array, and initializes a variable called swapped
to false. It then enters a do-while loop to swap the elements, where a for-loop goes through the entire array, checking if the current element is greater than the next element. If it is, it swaps their positions, and sets swapped
to true.

The loop continues until no more swaps are made. The function then returns the sorted array.

Bubble sort has a time complexity of O(n^2), meaning the time taken to execute increases exponentially with the size of input. This is because the algorithm has to compare each element in the array with every other element to ensure that it is sorted. For large arrays, the number of comparisons needed grows quickly and becomes very time-consuming. Therefore, bubble sort is considered inefficient and is generally avoided.

Example:

function bubbleSort(array) {
  const length = array.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < length; i++) {
      if (array[i] > array[i + 1]) {
        const temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return array;
}

const inputArray = [5, 3, 1, 4, 2];
console.log(bubbleSort(inputArray)); // Output: [1, 2, 3, 4, 5]

Big O Complexity Analysis: The time complexity of bubble sort is O(n^2), where n is the number of elements in the array. This is because it compares each element with every other element, leading to an exponential increase in the time taken to execute with the size of the input.

The space complexity of bubble sort is O(1) because it does not require any additional memory allocation beyond the input array.

Previous Lesson Next Lesson