Algorithms for Complete Beginners
Published: 2020-12-13 13:02:22

## What is Algorithm
**Algorithm** is step by step instructions to solve a problem.
* You might not have noticed but in our every day life we use algorithms. For example when you want to drink coffee you first boil water and pour boiled water to cup to make coffee.




#### Terms that describe how efficient an algorithm is
There are 3 terms that describe how fast our algorithm is and how much space it needs

They are specific terms to describe efficiency of an algorithm for Best Case, Worst Case, Average case
1. **Big Omega Ω** is used to describe the best case for runtime and space complexities of an algorithm.
2. **Order of or Big O** is used to describe the upper bound or the worst for space and runtime of an algorithm
3. **Big Theta (Θ)** is used to indicate that both the upper bound and the best case of our algorithm is the same which is average case

#### How to calculate efficiency of an algorithm?
For finding out **how fast algorithm runs**, If number of operations computer has to perform grows proportionally with the given input it is O(n) if quadratically it is O(n^2) if number operations are constant O(1)

**Think about bigger picture**. What I mean by this is that if number of operations computer has to perform is like this O(100n + 12); O(19n^2 + 2n +10), they are narrowed down to this O(n) and O(n^2). When they are scaled to very large data set for example 1 million and 10 million does not make much difference.

**Space required in memory** by certain primitives are constant which are as followings:
1. Both integer and float needs 4 bytes of memory
2. Bool needs 1 byte
3. Double and long needs 8 bytes of memory

**String** require 1 byte for each character and it can overflow memory and 
**Arrays and Object** also need **n** space in memory

**BIG-O ALGORITHM COMPLEXITIES** [visit](https://www.bigocheatsheet.com/)






# Algorithms



#### Searching Algorithms

**Linear Search** as name indicates searching algorithms in which we search data linearly one at a time
It can work on both **sorted and unsorted arrays**
Example
```
const linearSearch = (arr, num)=>{
    for(let val of arr){
        if(num === val){
            return true
        }
    }
    return false
}
linearSearch([10,8,5,11], 11)
```
**Runtime of an algorithm**
 *Best Case Omega(1); Worst Case O(n)*



**Binary Search** is logarithmic algorithm that's called divide and conquer algorithm. Because it searches target item in the array 1) looks at the middle if target item is in the middle, it returns else 2) eliminates the half in which it can't find target item.
It works only on **SORTED ARRAY**
**Runtime of an algorithm**
 *Best Case Omega(1); Worst Case O(log n)*





#### Sorting Algorithms

**Bubble sort** as its name makes it obvious bigger items bubble up in the array. It uses nested loop and it compares inner loop index with inner loop index + 1 and bigger one bubbles up.

Example: (it is optimized in nearly sorted array Best case will be O(n))
```
const swap = (arr, j)=>{
    let temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
                
}

const bubleSort = (arr)=>{
    let counter = 0;
    for(let i = 0; i < arr.length; i++){
        let isSorted = false;
        for(let j = 0; j < arr.length - 1; j++){
            if(arr[j] > arr[j + 1]){
                swap(arr, j)
                isSorted = true;
            }
        }
        if(!isSorted) break;
    }
    
    return arr;
}
bubleSort([6,4,1,1,1,2,3,4,5]);
```
**Runtime of an algorithm**
 *Average case O(n^2); but best could be O(n) on nearly sorted array*



**Selection Sort** it uses nested loop and find the smallest item between item in outer loop's current index and array items starting outer loop index + 1 till last item and it swaps the smallest item with item in the current index of outer loop

Example
```
 const swap = (arr, i, min) =>{
   const temp = arr[i];
   arr[i] = arr[min];
   arr[min] = temp;
 }
 const selectionSort = (arr)=>{
 for(let i = 0; i < arr.length; i++){
   let min = i;
   for(let j = i + 1; j < arr.length; j++){
     if(arr[j] < arr[min]){
       min = j;
     }
   }
   swap(arr, i, min)
 }
 return arr;
 }
 selectionSort([9,1,10,0,6,3]);
```
**Runtime of an algorithm**
 *Average case O(n^2);*



**Insertion Sort** sorts elements gradually by creating sorted larger half. It's one of the most efficient on nearly sorted array. It also uses nested array

Example
```
const insertionSort = (arr) =>{
  for(let i = 1; i < arr.length; i++){
    let currentMin = arr[i];
    for(var j = i - 1; j >= 0 && arr[j] > currentMin; j--){
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentMin;
  }
  return arr;
}
insertionSort([10,2,5,1]);
```
**Runtime of an algorithm**
 *Average case O(n^2); on nearly sorted data Best case O(n)*



**Merge Sort** logarithmic algorithm which divides array into left and right halves until 0 or 1 item left as 1 item is already sorted it merges left and right halves (it pushes smaller items before bigger items)

Example
```
const merge = (arr1, arr2) =>{
    const mergedArr = [];
    let left = 0;
    let right = 0;
    while(left < arr1.length && right < arr2.length){
        if(arr1[left] > arr2[right]){
            mergedArr.push(arr2[right]);
            right++;
        } else {
            mergedArr.push(arr1[left]);
            left++;
        }
    }
    while(left < arr1.length){
        mergedArr.push(arr1[left]);
        left++;
        
    }
    while(right < arr2.length){
        mergedArr.push(arr2[right]);
        right++;
        }
    return mergedArr;
}

const mergeSort = (arr) =>{
    if(arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}
```
**Runtime of an algorithm**
 *Average case O(n log n); Space complexity O(n)*


*Summary:* 
 * So you learned that an algorithm is how you arrive to solution
 * You now can know runtime of your algorithms and talk about runtime of algorithms with your friends and colleagues  
 * You now know some searching and sorting algorithms which you can use in your project.
 

Read Data Structures for Complete Beginners in [here](https://dev.to/johongirr/data-structures-for-complete-beginners-af5)