DEV Community

Cover image for Notes on algorithms
Emilie Gervais
Emilie Gervais

Posted on • Edited on

Notes on algorithms

#computerscience #javascript #programming

I'm doing CS50: Introduction to Computer Science on edx.org. I find it's a great way to review what I learn by completing, rewriting and sharing some of my notes.

Note: Big O notation can be though of “on the order of” and it represents the running time of an algorithm. In the C examples, n is equivalent to sizeof(arr)/sizeof(arr[0]) which translates in JavaScript to arr.length.

Week 3 is about algorithms. 😺

Table Of Contents

Linear Search

To iterate across the array from left to right searching for a target element.

Pseudocode example #1:

Repeat, starting at the first element:
    If the element is the target element, stop
    Else, move to the next element
Enter fullscreen mode Exit fullscreen mode

Pseudocode example #2:

For i from 0 to n–1
    If i'th element is target_element
        Return true
Return false
Enter fullscreen mode Exit fullscreen mode

C example:

bool linearSearch(int arr[], int n, int target) 
{ 
    for (int i = 0; i < n; i++) 
        if (arr[i] == target) return true;
    return false; 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript example:

linearSearch = (arr, target) => {
    for (let i = 0; i < arr.length; i++)
        if (arr[i] === target) return true;
    return false;
}
Enter fullscreen mode Exit fullscreen mode

Linear Search algorithm's

  • Worst case scenario:
    Having to look through the entire array of n elements in the case where the target element is the last one or it is not in the array.
    In Big O notation, it translates to O(n).

  • Best case scenario:
    The target element is the 1st element.
    In Big O notation, it translates to Ω(1).

Binary Search

To find the target element by reducing the search area by half each time. Make sure the array on which the binary search algorithm is used on is sorted, else it's impossible to make assumptions about its content.

Pseudocode example #1:

Repeat until the (sub)array is of size 0:
    Calculate the middle point of the current (sub)array
    If the target element is the middle element, stop
    Else if it's less than the middle: 
        End point is now just to the left of the current middle, repeat
    Else if it's greater than the middle: 
        Start point is now just to the right of the current middle, repeat
Enter fullscreen mode Exit fullscreen mode

Pseudocode example #2:

If no items
    Return false
If middle item is target_element
    Return true
Else if target_element < middle item
    Update end point
    Search left half
Else if target_element > middle item
    Update start point
    Search right half
Enter fullscreen mode Exit fullscreen mode

C example (recursive):

int binarySearch(int arr[], int target, int start, int end) 
{ 
    if (end >= start) { 
        // instead of (start+end)/2 to avoid overflow
        int mid = start+(end-start)/2; 
        if (arr[mid] == target) return mid; 
        else if (arr[mid] > target) return binarySearch(arr, target, start, mid-1); 
        else return binarySearch(arr, target, mid+1, end); 
    } 
    return -1; 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript example (recursive):

binarySearch = (arr, target, start, end) => {   
    if (end >= start) {
        let mid = Math.floor((start+end)/2);
        if (arr[mid] === target) return mid;
        else if(arr[mid] > target) return binarySearch(arr, target, start, mid-1); 
        else return binarySearch(arr, target, mid+1, end); 
    }
    return false;
}
Enter fullscreen mode Exit fullscreen mode

Binary Search algorithm's

  • Worst case scenario:
    Having to divide a list of n elements in half repeatedly to find the target element because the target is found at the end of the last division or it is not in the array.
    In Big O notation, it translates to O(log n).

  • Best case scenario:
    The target element is at midpoint of the array, so we can stop searching immediately after we start.
    In Big O notation, it translates to Ω(1).

Bubble Sort

To sort in a bubbling way: move higher values towards the right of the array and lower values, towards the left.

Pseudocode example #1:

Set swap counter to a non-zero value
Repeat until the swap counter is equal to 0:
    Reset swap counter to 0
    Look at each adjacent pair:
        If two adjacent elements are not in order:
            Swap them
            Add one to the swap counter
Enter fullscreen mode Exit fullscreen mode

Pseudocode example #2:

Repeat until no swaps
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them
Enter fullscreen mode Exit fullscreen mode

C example:

void bubbleSort(int arr[], int n) 
{ 
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
            {
                int temp = arr[j]; 
                arr[j] = arr[j+1]; 
                arr[j+1] = temp;
            }
}
Enter fullscreen mode Exit fullscreen mode

JavaScript example:

bubbleSort = arr => {
    for (let i = 0; i < arr.length-1; i++)
        for (let j = 0; j < arr.length-i-1; j++)
            if (arr[j] > arr[j+1]) {
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
    return arr;
}
Enter fullscreen mode Exit fullscreen mode

Because comparing the ith and i+1th element, the sorting only needs to go up to n-2 for i before swapping the two elements if they're out of order. Knowing the largest n-1 elements will have bubbled to the right, the sorting can stop after n-1 passes.
When re-going through the array, only consider the unsorted elements.
When the swap counter remains at 0, there is nothing else to swap.

Bubble sort algorithm's

  • Worst case scenario:
    Having to bubble each of the elements all the way across the array because the array is in reverse order. Since it's only possible to fully bubble one element into its sorted position per pass, the sorting must happen n times.
    In Big O notation, it translates to O(n²).

  • Best case scenario:
    The array is already perfectly sorted, resulting in no swapping on the first pass.
    In Big O notation, it translates to Ω(n).

Selection Sort

To find the smallest unsorted element and add it to the end of the sorted list.

Pseudocode example #1:

Repeat until there is no unsorted elements remaining:
    Search unsorted part of data to find the smallest value
    Swap the found value with the first element of the unsorted part
Enter fullscreen mode Exit fullscreen mode

Pseudocode example #2:

For i from 0 to n–1
    Find smallest item between i'th item and last item
    Swap smallest item with i'th item
Enter fullscreen mode Exit fullscreen mode

C example:

void selectionSort(int arr[], int n) 
{ 
    for (int i = 0; i < n-1; i++)
    {
        int min = i; 
        for (int j = i+1; j < n; j++) 
            if (arr[j] < arr[min]) min = j;
        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}
Enter fullscreen mode Exit fullscreen mode

JavaScript example:

selectionSort = arr => { 
    for (let i = 0; i < arr.length-1; i++) {
        let min = i; 
        for (let j = i+1; j < arr.length; j++)
            if (arr[j] < arr[min]) min = j;
        let temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
    return arr;
}
Enter fullscreen mode Exit fullscreen mode

Selection sort algorithm's

  • Worst case scenario:
    Having to repeat the sorting process n times to iterate each of the n elements of the array to find the smallest unsorted element and sort it. Only one element gets sorted on each pass.
    In Big O notation, it translates to O(n²).

  • Best case scenario:
    The same as the worst case scenario as there is no way to guarantee the array is sorted until the sorting process iterates over all of the elements of the array.
    In Big O notation, it translates to Ω(n²).

Insertion Sort

To build a sorted array in place; shifting elements out of the way to make room if necessary as the array is being built.

Pseudocode example #1:

Call the first element of the array sorted
Repeat until all elements are sorted:
    Insert next unsorted item into sorted part shifting the required number of items
Enter fullscreen mode Exit fullscreen mode

Pseudocode example #2:

For i from 1 to n–1
    Insert next unsorted item into sorted part shifting i items
Enter fullscreen mode Exit fullscreen mode

C example:

void insertionSort(int arr[], int n) 
{ 
    for (int i = 1; i < n; i++) { 
        int key = arr[i]; 
        int j = i-1; 
        while (j >= 0 && arr[j] > key) { 
            arr[j+1] = arr[j]; 
            j = j-1; 
        } 
        arr[j+1] = key; 
    } 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript example:

insertionSort = arr => { 
    for (let i = 1; i < arr.length; i++) { 
        let key = arr[i]; 
        let j = i-1; 
        while (j >= 0 && arr[j] > key) { 
            arr[j+1] = arr[j]; 
            j = j-1; 
        } 
        arr[j+1] = key; 
    } 
    return arr;
}
Enter fullscreen mode Exit fullscreen mode

Insertion sort algorithm's

  • Worst case scenario:
    Having to shift each of the n elements from n positions each time to make an insertion because the array is in reverse order.
    In Big O notation, it translates to O(n²).

  • Best case scenario:
    The array is already sorted. Only gotta keep moving between unsorted and sorted elements as we iterate over each of them.
    In Big O notation, it translates to Ω(n).

Recursion

To code elegantly. 🌹

Recursion is related to how an algorithm or a function is implemented, it isn't an algorithm itself.

A recursive function invokes itself as part of its execution.

Detailed example using the factorial function:

  • n! is defined over all positive integers
  • n! equals all of the positive integers less than or equal to n, multiplied together
  • n! as fact(n):

Pseudocode example #1:

fact(1) = 1
fact(2) = 2 * 1
fact(3) = 3 * 2 * 1
…
Enter fullscreen mode Exit fullscreen mode

Pseudocode example #2:

fact(1) = 1
fact(2) = 2 * fact(1)
fact(3) = 3 * fact(2)
…
Enter fullscreen mode Exit fullscreen mode

The basis for a recursive definition of the factorial function:

fact(n) = n * fact(n-1)
Enter fullscreen mode Exit fullscreen mode

Recursive function has two cases that can apply given any input:

  • Base case: terminates the recursive process when triggered
  • Recursive case: where the recursion happens 
int fact(int n) 
{
    // base case
    if (n == 1)
        return 1;
    // recursive case
    else
        return n * fact(n-1);
}
Enter fullscreen mode Exit fullscreen mode

There can be multiple base cases.
Example the fibonacci number sequence where:

  • 1st element is 0
  • 2nd element is 1
  • nth element is the sum of (n-1)+(n-2)

There can be multiple recursive cases.
Example the collatz conjecture.

The next C and JavaScript examples define a collatz function that calculates how many steps it takes to get "back to 1":

C example:

int collatz(int steps) 
{
    // base case
    if (steps == 1) return 0;
    // recursive case: even numbers
    else if ((steps % 2) == 0) return 1+collatz(steps/2);
    // recursive case: odd numbers
    else return 1+collatz(3*steps+1);
}
Enter fullscreen mode Exit fullscreen mode

JavaScript example:

collatz = steps => {
    // base case
    if (steps == 1) return 0;
    // recursive case: even numbers
    else if ((steps % 2) == 0) return 1+collatz(steps/2);
    // recursive case: odd numbers
    else return 1+collatz(3*steps+1);
}
Enter fullscreen mode Exit fullscreen mode

Merge Sort

To divide an array into smaller arrays to sort and then, combine those sorted arrays back together in sorted order.

Pseudocode example #1:

If only one element
  Return
Else
    Sort left half of elements
    Sort right half of elements
    Merge sorted halves
Enter fullscreen mode Exit fullscreen mode

Pseudocode example #2:

Sort the left half of the array (assuming n > 1)
Sort right half of the array (assuming n > 1)
Merge the two halves together
Enter fullscreen mode Exit fullscreen mode

C example (recursive):

// merges two subarrays of arr[]
void merge(int arr[], int leftIndex, int mid, int rightIndex) 
{ 
    int n1 = mid-leftIndex+1; 
    int n2 =  rightIndex-mid; 

    // temp arrays
    int Left[n1], Right[n2]; 

    // copy data to temp arrays
    for (int i = 0; i < n1; i++) 
        Left[i] = arr[leftIndex+i]; 
    for (int j = 0; j < n2; j++) 
        Right[j] = arr[mid+1+j]; 

    // merge the temp arrays back into arr[]
    int i = 0; // init index of 1st subarray 
    int j = 0; // init index of 2nd subarray 
    int k = leftIndex; // init index of merged subarray 
    while (i < n1 && j < n2) 
    { 
        if (Left[i] <= Right[j]) 
        { 
            arr[k] = Left[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = Right[j]; 
            j++; 
        } 
        k++; 
    } 

    // copy the remaining elements of Left[], if any
    while (i < n1) 
    { 
        arr[k] = Left[i]; 
        i++; 
        k++; 
    } 

    // copy the remaining elements of Right[], if any
    while (j < n2) 
    { 
        arr[k] = Right[j]; 
        j++; 
        k++; 
    } 
} 

void mergeSort(int arr[], int leftIndex, int rightIndex) 
{   
    if (leftIndex < rightIndex) 
    { 
        // instead of (l+r)/2 to avoid overflow
        int mid = leftIndex+(rightIndex-leftIndex)/2; 
        // sort first and second halves 
        mergeSort(arr, leftIndex, mid); 
        mergeSort(arr, mid+1, rightIndex); 
        // merge them back together
        merge(arr, leftIndex, mid, rightIndex); 
    } 
}
Enter fullscreen mode Exit fullscreen mode

JavaScript example (recursive):

// to merge left subarray and right subarray
merge = (left, right) => {
    let resultArray = [], leftIndex = 0, rightIndex = 0;

    // concat values into the resultArray in order
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex]);
            leftIndex++;
        } else {
            resultArray.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // concat remaining element from either left OR right
    return resultArray
        .concat(left.slice(leftIndex))
        .concat(right.slice(rightIndex));
}

mergeSort = arr => {
    // if array has one element or is empty, no need to sort
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length/2);
    // divide the array into left and right
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    // merge back together using recursion
    return merge(mergeSort(left), mergeSort(right));
}
Enter fullscreen mode Exit fullscreen mode

Merge sort algorithm's

  • Worst case scenario:
    Having to split n elements up before recombining them effectively, doubling the sorted sub-arrays as they are built.
    In Big O notation, it translates to O(n log n).

  • Best case scenario:
    The array is already sorted, but still gotta be split and recombined back together to know it is sorted.
    In Big O notation, it translates to Ω(n log n).

Resources:

Top comments (12)

Collapse
 
codemouse92 profile image
Jason C. McDonald • • Edited

I enjoyed the video immensely, by the way!

You may also consider looking into two more, both of which are among the fastest known sorting algorithms in existence.

  • Dual-Pivot Quick Sort (Yaroslavisky, Vladamir)
  • Timsort (Peters, Tim)
Collapse
 
hexangel616 profile image
Emilie Gervais •

Thank you, I'll look into them! 😊👍

Collapse
 
jinglescode profile image
Jingles (Hong Jing) •

It's encouraging to see you summarize what learn from courses, at the same time others can learn from you as well. Keep doing it 👍🏻

Collapse
 
jlohani profile image
Jayant Lohani • • Edited

The best thing to test whatever you have learnt/studied is to share and explain others about it. It boosts confidence as well as help understand it better.
Came across these algorithms a year ago while studying C/C++. Thanks for refreshing these algorithms. Great notes for revision. ✌

Collapse
 
hexangel616 profile image
Emilie Gervais •

I agree, but find it hard to find the time to do so in an interesting way sometimes. I guess it's an habit to take up as part of a learning & sharing routine. Like it should be done right after and/or before starting to learn something else.
Thanks to you for the positive comment. =)

Collapse
 
jlohani profile image
Jayant Lohani •

Yeah that true. Its difficult to take out time. I am a beginner so trying my best to implement this habit from the beginning. The good thing about doing this is that the work is done more systematically and with focus. No one would work lazily or just for formality if he/she has to deliver that to a bunch of people afterwards. Also the quality will be maintained. And the best thing is that it would act as a revision /summary for him/her and others who would come across it. Its a win win situation for everyone. 🙂
Thanks for these notes. Hope to read more in future and gain knowledge. Great job and all the best.✌

Thread Thread
 
hexangel616 profile image
Emilie Gervais •

Totally agree once again. 🙂
Thanks to you and all the best as well! 💮

Collapse
 
mah_khalafallah profile image
Mahmoud Khalafallah •

I didn't get avoid overflow part

Collapse
 
hexangel616 profile image
Emilie Gervais • • Edited

To prevent integer overflow for large numbers which could end up being too big to fit the integer's storage space.
en.wikipedia.org/wiki/Integer_over...
fresh2refresh.com/c-programming/c-...

Collapse
 
mah_khalafallah profile image
Mahmoud Khalafallah •

Aha, I see
So we get the difference first and divide it by 2 then add it to the start.
instead of adding the start and the end.
But why we didn't do the same with the js example ?!

Thread Thread
 
hexangel616 profile image
Emilie Gervais •

To highlight both possibilities? You don't always have to worry about overflow; When you do, it's nice to know there's a simple solution. These are just notes.

Collapse
 
heyrohit profile image
Rohit Gupta •

:)

View full discussion (12 comments)

Read next

colindickson_78 profile image

Using Weak Pointers in Go

Colin Dickson -

hitesh_developer profile image

Angular vs Next.js: A Detailed Comparison

Hitesh Chauhan -

pvsdev profile image

Brain debugging. Interview with Anders Schau Knatten, author of "C++ Brain Teasers: Exercise Your Mind"

Anastasiia Vorobeva -

mikeyoung44 profile image

AI System Learns How Objects Interact in Images to Generate New Scenes with Same Relationships

Mike Young -