How do you implement a basic sorting algorithm in JavaScript?

This guide demonstrates a basic sorting algorithm, Bubble Sort, implemented in JavaScript. Bubble Sort is one of the simplest sorting algorithms, primarily used for educational purposes due to its low efficiency compared to more advanced algorithms.

Understanding Bubble Sort

Bubble Sort works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Elements 'bubble up' to their correct position.

Bubble Sort Algorithm Steps

• Start with an unsorted list (or array).
• Iterate through the array from the first element to the second-to-last element (i-th index).
• In each iteration, compare the current element with the next element (i-th and i+1-th).
• If the current element is greater than the next element, swap them.
• Repeat this process for each pair of adjacent elements. After the first pass, the largest element will be at the end of the array.
• Decrement the range of elements to consider by one (since the last element is now sorted) and repeat the process until no swaps occur in a full pass, indicating the array is sorted.

JavaScript Implementation

Here's the JavaScript code for a Bubble Sort function:

function bubbleSort(arr) {
  let n = arr.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        // Swap elements
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
    // After each pass, the largest unsorted element is at its correct position
    n--; 
  } while (swapped);
  return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Original array:", unsortedArray);
const sortedArray = bubbleSort(unsortedArray);
console.log("Sorted array:", sortedArray); // Output: [11, 12, 22, 25, 34, 64, 90]

How it Works (Example Walkthrough)

Let's trace the execution with an example array [5, 1, 4, 2, 8].

Time Complexity

Bubble Sort has a time complexity of O(n²) in the worst and average cases, where 'n' is the number of elements in the array. This is because it requires nested loops to compare and potentially swap elements. In the best-case scenario (when the array is already sorted), it can achieve O(n) if an optimization to stop early when no swaps occur is implemented.

Space Complexity

The space complexity for Bubble Sort is O(1) because it sorts the array in-place, meaning it only requires a constant amount of extra memory for temporary variables during swaps, regardless of the input size.