Bubble Sort: Given an Array of Unsorted Items, Return A Sorted Array
Published: 2024-07-08 19:36:38

While most modern languages have built-in sorting methods for operations like this, it is still important to understand some of the common basic approaches and learn how they can be implemented.

The bubble sort method starts at the beginning of an unsorted array and 'bubbles up' unsorted values towards the end, iterating through the array until it is completely sorted. 

It does this by comparing adjacent items and swapping them if they are out of order. The method continues looping through the array until no swaps occur at which point the array is sorted.

This method requires multiple iterations through the array and for average and worst cases has quadratic time complexity. While simple, it is usually impractical in most situations.

### Instructions: 
Write a function bubbleSort which takes an array of integers as input and returns an array of these integers in sorted order from least to greatest.

    Waiting: bubbleSort should be a function.
    Waiting: bubbleSort should return a sorted array (least to greatest).
    Waiting: bubbleSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]) should return an array that is unchanged except for order.
    Waiting: bubbleSort should not use the built-in .sort() method.


Let's implement the `bubbleSort` function according to the specifications. Here's a step-by-step implementation of the bubble sort algorithm:

```javascript
function bubbleSort(array) {
  // Make a copy of the original array to avoid modifying it directly
  let arr = [...array];
  let swapped;
  
  do {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        // Swap elements
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
  } while (swapped);
  
  return arr;
}
```

Let's break down this implementation:

1. We start by creating a copy of the input array using the spread operator (`[...array]`). This ensures we don't modify the original array.

2. We use a do-while loop that continues as long as we make any swaps in a pass through the array.

3. Inside the loop, we iterate through the array, comparing adjacent elements.

4. If we find two adjacent elements that are out of order (the left one is greater than the right one), we swap them using destructuring assignment.

5. We set the `swapped` flag to `true` whenever we perform a swap.

6. The outer loop continues until we make a full pass through the array without any swaps, indicating that the array is fully sorted.

7. Finally, we return the sorted array.

This implementation satisfies all the given requirements:
- It's a function named `bubbleSort`.
- It returns a sorted array from least to greatest.
- It works correctly for the given example input.
- It doesn't use the built-in `.sort()` method.

You can test it with the provided example:

```javascript
console.log(bubbleSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]));
```

This will output the sorted array:

```
[1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]
```

Note that while this implementation correctly sorts the array, bubble sort has a time complexity of O(n^2) in the average and worst cases, making it inefficient for large arrays. However, it's a simple algorithm to understand and implement, which makes it useful for educational purposes.