Quick Sort in Javascript

Quick sort is faster than bubble sort.

It uses the idea of divide and conquers. Divides the array into two halves using a pivot in such a way that elements in the left half are smaller than the pivot and elements in the right are greater than the pivot — then recursive using quick sort on the left and right parts.

I would recommend below youtube to understand Quick Sort:
https://www.youtube.com/watch?v=eqo2LxRADhU

Here is my implementation in javascript:

function quickSort(arr, start, end) {
  // Stop the recursion when the start equal or smaller to the end
  if (start >= end) { 
    return ; 
  };
  
  // Here is the magic happen
  let pivotIndex = partition(arr, start, end);
  
  // Recursion - quick sort the left part
  quickSort(arr, start, pivotIndex - 1);
  
  // Recursion - quick sort the right part
  quickSort(arr, pivotIndex + 1, end);
}

function partition (arr, start, end) {
  let pivotIndex = start; // Pivot location
  let pivotValue = arr[end]; // Use the last number  
  
  for (let i=start; i<end; i++) {
    // Move number that smaller than pivot value to the front.
    // Update pivot index
    if (arr[i] < pivotValue) {
      // Move to front
      swap(arr, i, pivotIndex);
      pivotIndex++;
    }
  }
  
  // Swap the pivot value to correct location
  swap(arr, end, pivotIndex);
  return pivotIndex;
}

function swap(arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

let arr = [2 ,1, 4, 5, 3, 6, 6, 8, 1, 3];
quickSort(arr, 0, arr.length - 1);

Bubble Sort in Javascript

Bubble soft is the most straightforward sorting algorithm that works by repeatedly swapping the elements if they are in wrong orders.

Example:

1. Swapping the first element.
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

2. Swapping the second element.
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), No swap
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), No swap
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), No swap

3. Pass the sorting criteris when there is no swapping.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), No swap
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), No swap
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), No swap
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), No swap

Let write the code to do it:

let items = [1,2,3,5,4];

function bubbleSort(p_val){
  let sorted = p_val;
  
  for (let i=0, x=p_val.length; i<=x; i++){
      let isSwapRequired = false;
      for(let j=0; j<=x-i-1; j++){
        // compare items and only swap them if the second one's smaller
        if (sorted[j] > sorted[j+1]) {
          isSwapRequired = true;
          let first = sorted[j];
          let second = sorted[j+1];
          sorted[j+1] = first;
          sorted[j] = second
        }
    }
    // IF no two elements were swapped by inner loop, then break 
        if (!isSwapRequired) { break; };
  }
  
  return sorted;
}

document.write(bubbleSort(items));

The best case is when the array is already sorted, and worst case is the array is reverse sorted.

So that is the famous bubble sort. I will talk on other sorting algorithms next time.

Notes: There is a native javascript method to sort an array (Array.sort) that is more efficient and easier to use. This example is to demonstrate the bubble sort.

Recursion in Javascript

A recursive function is the ability to call itself and stop on matching the criteria.

For example, we could write a recursion to reverse a string from "ABC" to "CBA".

// Parameter: A string.
// Return: Last character of the string.

function reverseString(p_val){

  // Get the string's length
  var length = p_val.length;

  // Get the last character
  var lastchar = p_val.charAt(length - 1);

  if (length == 1) {

     // Return the last char
     return lastchar;

  } else {

    // Run the recursion
    return lastchar + reverseString(p_val.substring(0,length - 1))

  }

}

Let's say the parameter is "ABC". The process will be:

1. Return: C + reverseString("AB") 
2. Return: C + B + reverseString("A") 
3. Return: C + B + A

Using Scala Recursion Functions For Permutation Calculation

Permutation is an ordered combination - how many possible ordered combination.

There are 2 types of Permutation:

1. Permutation with Repeat is Allowed
   
   Permutation Lock is an example of Repeat Allowed.
   
   There are 10 numbers to choose from (0,1,...9) and we choose 3 of them.
   
   10 x 10 x 10 = 1000 permutation
   
   
   

   Formula: nr where n is the number of things to choose from, and r 
   is number of times

2. Permutation with No Repeat
   
   
   
   A good example is lottery which number can not be repeat.
   
   There are 3 numbers to choose from (1,2 and 3) and we choose 3 of them.
   
   3 x 2 x 1 = 6 permutation
   
   

   Formula: Without repetition our choices get reduced each time.

But how do we write that mathematically? Answer: we use the "factorial function".

I am going to use recursion method to write factorial function. This program accepts 2 integer inputs (Number of things to choose from and Number of times to choose) and calculate how many permutation (possible combination) with not repeat.

object Permutations {
  def main(args: Array[String]) {
    print("How many lottery number? ")
    val num1 = readInt()
    println()
    print("How many lottery  number to pick? ")
    val num2 = readInt()
    println("Total Permutation: " + factorial(num1,num2).toString)
  }
  
  def factorial(x: BigInt, y: BigInt) : BigInt = {
    if (y > 1)
      x * factorial( x - 1, y - 1)
    else
      x
  }
}

1. Tips: Remember to has exist call on recursive function to avoid unstopped loop