Sorting Algorithms: Bubble Sort

#algorithms #codenewbie

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:

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

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.

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.