Bubble Sort

#javascript #html #css #webdev

                   -Intro to Sorting Algorithm
                   -Built-In JavaScript Sorting
                   -Bubble Sort
                   -Bubble Sort: Implementation
                   -Bubble Sort: Optimization

Intro to Sorting Algorithm

A sorting algorithm is the process of rearranging items in a collection such as an array, so that the items are in some kind of order.

Some examples include

-Sorting numbers from smallest to largest
-Sorting names alphabetically
-Sorting movies based on release year
-Sorting movies based on revenue

Sorting is a common functionality in applications. There are many different ways to sort things; different techniques have their own advantages and disadvantages.

An interesting web site to show off sorting algorithms with animations.

https://www.toptal.com/developers/sorting-algorithms

Built-In JavaScript Sorting

Javascript has a built-in sorting method, however it works slightly different than expected. The sort() method sorts the elements of an array in place and returns the array. Not a stable way to sort items.

The built-in sort method accepts an optional comparator function. The comparator function tells JavaScript how you want it to sort. The comparator looks at pairs of elements (a and b), determines their sort and order based on the return value.

More information here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Bubble Sort: sorting algorithm where the largest values bubble up to the top. Many sorting algorithms involve some type of swapping functionality.

Bubble Sort: Implementation


function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){
    for(var j = 0; j < i - 1; 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;         
      }
    }
  }
  return arr;
}

// ES2015 Version
function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);

Bubble Sort: Optimization



function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;         
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);