Sorting Algorithms: Bubble Sort
Tags: algorithms, codenewbie
Published: 2021-03-30 00:21:13

# Sorting Algorithms?
So, you're probably wondering, _"What exactly are sorting algorithms?"_. Well, a sorting algorithm is simply used to rearrange a given array or some list of elements in an ascending or descending order. With the use of a comparison operator that decides the new order of the elements in the data structure.

An example would be if we had an array of unsorted numbers, we wanted our algorithm to sort them in ascending order.
```
[3,5,7,1,2] => [1,2,3,5,7]
```
________
## Bubble Sort
Now, A __Bubble Sort__ algorithm is one of the simplest sorting algorithms to understand. Bubble sort works by repeatedly swapping the adjacent elements if they are in the wrong order. Let's say we are ascending from smallest to largest in an array:
{% youtube 9I2oOAr2okY%}
***
### What Exactly Is Happening Here?
What our bubble sort algorithm is doing here is, through every single iteration, it is continuously comparing each pair of integers, determining where to place those two integers in regards to how we design the code. In the example above, it is sorting in ascending order from smallest to largest.
### Pseudocode
_Here are some steps to get you started on how you can implement a __bubble sort algorithm__._
- First, create a function called _bubbleSort_ that takes in an array.
- Using a for loop, with a variable i from the end of the array to the beginning.
- Using an inner loop, with a variable of j that starts at the beginning and ends i - 1.
- Compare if arr[j] is greater than arr[j + 1], swap those two values.
- at the end return the sorted array

********* 
### The Code
```javascript
function bubbleSort(arr){
  for(let i = arr.length - 1; i > 0; i++){
    for(let j = i -1; j < arr.length; j++){
      if(arr[j] > arr[j + 1]){
        var temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}
```
If you take a good look at this code, we aren't quite finished just yet! In the scenario of our data almost sorted or is already sorted, it doesn't need to be sorted again. Yet, right now our bubble sort algorithm doesn't regard if the array is somewhat or already there. If we had an array of lengths 32 or more, this kind of logic will take up unnecessary space.

To combat this, we can have checks within our code asking, "Did we make any swaps here?", If no, then we must be done in our iteration. 

### Opimization
So, to optimize this code to prevent unnecessary swapping from happening, we can use a _noSwaps_ variable that will take in a boolean. 

```javascript
function bubbleSort(arr){
  var noSwaps;
  for(let i = arr.length - 1; i > 0; i++){
    noSwaps = true
    for(let j = i -1; j < arr.length; j++){
      console.log(arr, arr[j], arr[j + 1])
      if(arr[j] > arr[j + 1]){
        var temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        nSoSwaps = false
      }
    }
    if(noSwaps) break
  }
  return arr
}
```
Here, if there aren't anymore swaps within an iteration, we must break out of the code and return our array. This gets rid of the unnecessary actions of our code iterating through the area for a possible swap.
### Conclusion
That concludes this blog on bubble sort! Stay tuned for my next blog that will focus on __Selection Sort__