Sorting — Algorithm- javascript

Photo by Sophie Elvis on Unsplash

1. Bubble Sorting Algorithm:

In this algorithm greater number goes down and smallest number bubbles out.

function bubbleSort2(a) {
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length; j++) {
      if (a[j] > a[j + 1]) {
        temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }
  }
  return a;
}

we can optimise the above solution by a simple check, before the second loop we will initialise it as false.Now if any swap not occurred in second loop it means that our array is already sorted and no need to loop it again.So will break the loop and rerun the array.

function bubbleSort2(a) {
  for (let i = 0; i < a.length; i++) {
    let swap = false;
    for (let j = 0; j < a.length; j++) {
      if (a[j] > a[j + 1]) {
        temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
        swap = true;
      }
    }
    if (!swap) {
      return a;
    }
  }
  return a;
}

Best: O(n) Average: O(n*2) Worst : O(n*2) => Time Complexity

2. Selection sorting algorithm:

In selection sort the minimum number comes out first one by one and sort the list.

function selectionSort(a) {
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < a.length; j++) {
      if (a[i] < a[j]) {
        temp = a[j];
        a[j] = a[i];
        a[i] = temp;
      }
    }
    console.log('a', a);
  }
  return a;
}

Best: O(n*2) Average: O(n*2) Worst : O(n*2) => Time Complexity

3. Insertion sorting algorithm:

This algorithm is useful if the array is almost sorted.

1. start by taking the second element in the array.
2. Now compare the second element woth the one before it swap if necessary.
3. Continue to the next element and if it in incorrect order, iterate through the sorted portion.
4. Repeat until array sorted
function insertionSort(arr){
    var currentVal;
    for(var i = 1; i < arr.length; i++){
        currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}
Another way for solving this :-
function insertionSort(ar) {
  const length = ar.length;
  for (let i = 0; i < length; i++) {
    if (ar[i] < ar[0]) {
      //move number to the first position
      ar.unshift(ar.splice(i, 1)[0]);
    } else {
      if (ar[i] < ar[i - 1]) {
        //find where number should go
        for (var j = 1; j < i; j++) {
          if (ar[i] >= ar[j - 1] && ar[i] < ar[j]) {
            //move number to the right spot
            ar.splice(j, 0, ar.splice(i, 1)[0]);
          }
        }
      }
    }
  }
}

Best: O(n) Average: O(n*2) Worst : O(n*2) => Time Complexity