DEV Community: CONRAD

Insertion Sort

CONRAD — Fri, 31 Mar 2023 08:55:19 +0000

Insertion sort builds the final sorted array one item at a time by comparisons. works best on small datasets and is much less efficient than quicksort, mergesort.

My understanding on this is that insertion sort removes one item from the input array/list, finds the location it belongs within the sorted list, and inserts it there. it repeats until no input elements remain.

below is the solution, using a recursive approach:

const insertionSort = (arr, n) => {
    if(n > 0) {     //base case
        insertionSort(arr, (n - 1))

        let x = arr[n];
        let j = (n - 1);

        while (j >=0 && arr[j] > x) {
            //swap 
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = x;

        console.log(arr, '\n');
    }
}
const inputArr = [5,10,1,25];
insertionSort(inputArr, (inputArr.length - 1));  // [1, 5, 10, 25]

Worst/Average case: O(n^2)
However insertion sort is the fastest in sorting small datasets, even faster than quicksort. but terrible with large datasets.

Bubble sort algorithm

CONRAD — Thu, 30 Mar 2023 09:18:25 +0000

The Bubble sort algorithm is a simple sorting algorithm that operates by comparing pairs of values in an array. It works by iterating through the array and comparing adjacent values, swapping them if the value on the left is greater than the value on the right. This process is repeated until there are no more values that are greater than the highest value in the array, resulting in a sorted list/array in ascending order.

While Bubble sort is a straightforward algorithm, it can be slow and inefficient for large arrays. Despite its limitations, it is still a useful algorithm to understand as it forms the foundation for more complex sorting algorithms.

In summary, the Bubble sort algorithm compares pairs of values and swaps the greatest with the least until the array is sorted in ascending order.

so the steps are simple:

nested loop to run through input array, using 2 variables (i and j). such that 0≤i≤(n-1) and 0≤j≤(n-i-1)
if arr[j] is greater than arr[j+1] then swap the adjacent value else so on.
return sorted array.

Below is the solution in javascript.

const swap = (arr, pos1, pos2) =>  {
    //swap pos2 val with pos1 val
    let temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}

const bubbleSort = (arr = []) => {
    let len = arr.length;

    for(let i=0; i<len; i++) {
        for(let j=0; j<(len - i - 1); j++ ) {  

            //swap arrayValue with its adjacent if its greater than it.
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1); 
            }
        }
    }
    return arr;
}

The Best case scenario is when the input array is sorted in ascending order, worst case scenario is when the input array is sorted in descending order.
Time complexity for Best case O(n);
Time complexity for Worst case O(n^2);

Worst case scenario analysis:
If the input array is in descending order, that means that many iterations/passes will be required to swap elements
total number of iterations on an input array (n-1)

At iteration 1: Number of comparisons = (n-1)
Number of swaps = (n-1)

At iteration 2: Number of comparisons = (n-2)
Number of swaps = (n-2)

At iteration 3: Number of comparisons = (n-3)
Number of swaps = (n-3) .... and so on
= (n-1) + (n-2) + (n-3) + . . . 2 + 1
= (n-1)*(n-1+1)/2 { using sum of n natural Number formula }
= n(n-1)/2

= n^2
therefore Total number of swaps = Total number of comparisons
Worst case scenario: O(n^2)

Input:
[6,4,1]
Output:
[1, 4, 6]

Bubblesort is relatively easy to implement but due to its time complexity of O(n^2) it can be very slow for large datasets.

Learning Datastructure & algorithms all over again.

CONRAD — Thu, 30 Mar 2023 08:16:51 +0000

I completed my undergraduate studies in computer science with honors six years ago. However, due to my professional work in various projects for over five years, I did not have frequent exposure to theories on data structures and algorithms. Consequently, I did not deem it necessary to refresh my knowledge or skills in this area. Regrettably, I now realize that this decision has had a negative impact on my job search for software development positions, as many tech companies require such knowledge.

To address this gap in my knowledge, I have decided to embark on a journey to re-learn and practice various algorithms. Blogging is an excellent platform for me to document my learning process and share my experiences with others.

In particular, I intend to focus on a variety of algorithms such as sorting algorithms, search algorithms, and graph algorithms. My goal is to provide detailed explanations and code snippets for each algorithm that I research. I plan to post daily updates on my progress towards achieving this objective.

Here are some of the algorithms that I will be exploring in detail:

Sorting Algorithms:

- Bubble sort
- Insertion sort
- Merge sort
- Quick sort
- Heap sort

Search Algorithms:

Linear Search
Binary Search

Graph Algorithms:

Depth-First-Search(DFS) & Breadth-First-Search algorithms
Dijkstra's Algorithm

I hope that this blogging endeavor will not only help me to refresh my knowledge of algorithms but also aid others who may be in a similar situation.