# #1 Bubble Sort

###### tags:`Sort` `Easy`

## Problem
Write a function that takes in an array of integers and returns a sorted version of that array. Use the Bubble Sort algorithm to sort the array.
If you're unfamiliar with Bubble Sort, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

### Sample Input

array = [8, 5, 2, 9, 5, 6, 3]

### Sample Output

[2, 3, 5, 5, 6, 8, 9]

<br>

:::spoiler **Optimal Space & Time Complexity**

:::

<br>

:::spoiler Hint 1

:::

<br>

:::spoiler Hint 2

:::

<br>

:::spoiler Hint 3

:::

<br>

<hr/>

## Solutions

### Official

<br>

---

### Everyone's

:::spoiler 月

// Time O(n^2) | Space O(1)
// n is the length of array

function bubbleSort(array) {
  const { length } = array;
  for(let i = 0; i < length; i++){
    for(let j = 0; j < length - 1 - i; j++){
      if(array[j] > array[j+1]){
        [array[j],array[j+1]] = [array[j+1], array[j]];
      }
    }
  }
  return array
}

:::

<br>

:::spoiler Hao

/**
 * Time complexity: O(N^2) where N stands for array.length
 * Space complexity: O(1)
 */

function bubbleSort(array) {
  for (let i = 0; i < array.length; i += 1) {
    const lastIdxShouldCheck = array.length - i;

    for (let j = 0; j < lastIdxShouldCheck + 1; j += 1) {
      if (array[j] > array[j + 1])
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
    }
  }

  return array;
}

- In line 10, the inner loop could be `array.length - 1`.
- And to avoid unnecessary comparisions, you can implete in `lastIdxShouldCheck - 1`
:::

<br>

##### best case O(n)

:::spoiler 東

// Time O(n^2) | Space O(1) - n is the length of input array
function bubbleSort(array) {
  let hasSwap = false;
  for(let i = 0; i < array.length; i++){
    hasSwap = false;
    for(let j = 0; j < array.length - i - 1; j++){
      if(array[j] > array[j+1]) {
        swap(array, j, j + 1 );
        hasSwap = true;
      }
    }
    if(!hasSwap) return array; // if the array is sorted can return directly.
  }
  return array;
}

function swap(array, idx1, idx2){
  [array[idx1], array[idx2]] = [array[idx2], array[idx1]];
}

:::

<br />

:::spoiler YC

function bubbleSort(array) {
    /*
        time: best case O(n), otherwise O(n^2) - where n is the length of the array
        space: O(1)
    */
  let isSorted = false;
  let finishedNum = 0;
  while(!isSorted){
    isSorted = true;
    for(let i = 0; i < array.length - 1 - finishedNum; i++){
      if(array[i] > array[i+1]){
        [array[i], array[i+1]] = [array[i+1], array[i]]
        isSorted = false;
        
      }
    }
    finishedNum++;
  }
  return array;
}

- use `isSorted` to control flow and determine whether sort.
:::

---

## Supplement / Discussion
#### The bubble sort algorithm
- `O(n^2)`
#### Improve the bubble sort algorithm(a little bit)
- Subtract the number of passes from the inner loop to avoid all the unnecessary comparisons done by the inner loop.
- If the array is sorted, can turn directly. And the time complexity will become `O(n)`.