Description

Not suitable for large data sets
Implementation is short and simple

# Time & Space Complexity

Time:
- Best (Optimized): O(n)
- Best (Not Optimized): O(n^2)
- Average: O(n^2)
- Worst: O(n^2)
Space:
- O(1)

# Implementation

# Not Optimized

javascript

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - i - 1; j++) {
      // Swap
      if (array[j] > array[j + 1]) {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

# Optimized

javascript

function bubbleSort(array) {
  let isSwaped = false;

  for (let i = 0; i < array.length; i++) {
    isSwapped = false;

    for (let j = 0; j < array.length - i - 1; j++) {
      // Swap
      if (array[j] > array[j + 1]) {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
        isSwaped = true;
      }
    }

    // Break if no elements are swaped (array is completely sorted)
    if (!isSwaped) break;
  }
}

# Possible Test Cases

javascript

const array1 = [] // Given array is empty
const array2 = [3] // Given array contains only a single element
const array3 = [0, 0, 0, 0] // Given array contains only zeros
const array4 = [2, 2, 2, 2] // Given array contains same elements
const array5 = [1, 2, 3, 4, 5] // Given array is already sorted
const array6 = [5, 4, 3, 2, 1] // Given array is reversed
const array7 = [-2, -5, 3, 1, 0] // Given array contain both positive and negative numbers
const array8 = generateRandom(10000) // Given array contains large number of elements

javascript

const generateRandom = (count) => {
  // Create array of integers
  let nums = [...Array(count).keys()];

  // Shuffle
  for (let i = nums.length - 1; i > 0; i--) {
    let randomIndex = Math.floor(Math.random() * i) % i;

    // Swap
    let temp = nums[i];
    nums[i] = nums[randomIndex];
    nums[randomIndex] = temp;
  }

  return nums;
};

# Working Example

Type yarn test on console to run vitest.