DEV Community: Sudharsanan S R

QuickSort

Sudharsanan S R — Sun, 27 Sep 2020 13:08:01 +0000

It's been a while since I posted, today we will discuss QuickSort.

Before that, if you haven't seen my last post. Click on the below link.

Merge Sort

Sudharsanan S R ・ Aug 31 '20

#javascript #algorithms #sorting #arrays

The topic for today is QuickSort!

Quicksort is a divide & conquer algorithm.
It uses recursion to sort the elements.
It considers pivot element as a base value and sorts rest of the elements.

Pseudocode

Base condition: Return the array as it is if the array length is equal to 1.
Identify the pivot value
Get all the elements less than the pivot value on one side.
Get all the elements greater than the pivot value on another side.
Repeat steps 2,3 & 4
Return final sorted array

Click below link to view the pictorial representation of how the algorithm works

Source: https://www.geeksforgeeks.org/

Implementation in JavaScript

below is the result

Hope this is useful, will catch you soon on my next post!

Happy learning!

Thanks,
Sudharsanan Ravichandran

Merge Sort

Sudharsanan S R — Mon, 31 Aug 2020 13:13:14 +0000

Hope you read my previous article on the selection sort, and how it is similar to Insertion sort.

If not, check out this article below.

Selection Sort

Sudharsanan S R ・ Aug 24 '20

#javascript #algorithms #sorting

We will see the Merge Sort today.

Merge Sort is a divide and conquer sorting algorithms, which uses recursion to sort.

Here is a pictorial representation of how it works.

(Top -> Bottom)

In the above diagram, we are dissecting the elements of array based on a pivot value (depending on the length of the array).

Since the dissection happens back to back due to recursion, we would need a base condition. Here our base condition is to return the input if the "input.length" is less than or equal to 1.

Once the elements are dissected, the sorting happens.

Here we compare the values of 2 arrays dissected starting from the index "0". If the value on the left found to be smaller, we will push that element to the result array and increment the counter on the left array (only), same goes to the array on right.

We do it repeatedly until the counter value reaches the array length.

In the end, there will be one element either in right or the left array which needs to be pushed to the result (the largest element), so we concatenate that value while returning the result.

Video reference (Start from 3:08)

Below is the implementation in JavaScript for the Merge Sort algorithm

Here is the result.

Hope you find this helpful.

Please share your feedback, will see you again.

Thanks,
Sudharsanan Ravichandran

Selection Sort

Sudharsanan S R — Mon, 24 Aug 2020 13:51:58 +0000

As we continue to look into sorting algorithms we will learn what's Selection Sort today.

Selection Sort is another naive sorting approach, can be used for sorting smaller data sets.

First, let's look at the Pseudo code

For this example, let's imagine we are looking at an unsorted set of cards

Find the smallest card and swap it with the first element of the array.
Find the second smallest card and swap it with the second element of the array.
Repeat finding the next-smallest card, and swapping it into the correct position until the array is sorted.

Simple! isn't it?!

Below is the implementation of Selection Sort in JS

Once after you execute the function below is the response

As I mentioned earlier on the below article.

Insertion Sort

Sudharsanan S R ・ Aug 21 '20

#javascript #sorting #algorithms

this video reference was really good to understand how similar Insertion Sort & Selection Sort are.

Hope you like this article, please feel free to share your comments.

Thanks again for stopping by 😊

Insertion Sort

Sudharsanan S R — Fri, 21 Aug 2020 17:59:00 +0000

This is my second post on Sorting algorithms.

We will see how Insertion Sort works

Insertion sort is another naive sorting approach which can't be used for large data sets. But, if you understand the crux of how it works under the hood. It's easy to implement.

Below is the Pseudocode for the sorting algorithm

Pseudocode

Element at the very first index is assumed sorted
You pick the element at the second index
Compare the element with the sorted subarray list (one element at a time)
If element compared within the sorted subarray list is bigger than the current you will shift them one place to the right.
You will repeat the above process until either you reach the left end of the array or if the element compared with is less than the current element.
Repeat the process until all elements are sorted.

I got this beautiful visual representation of how it works in a nutshell.

Please click on the below reference link to check it out.

https://tutorialsbookmarks.com/wp-content/uploads/2019/08/Insertion-sort-example.gif

Below is the source code implemented in JavaScript.

This is not a pure function-based implementation!

Hope you like this, please share your comments and I am looking forward to any optimizations that can be done here.

On my next post, we will see the Selection Sort and also understand how it's similar to the Insertion sort we saw above.

For this content, I got an awesome video reference that I can't wait to share.

See you in the next post!

Thanks,
Sudharsanan Ravichandran

Bubble Sort

Sudharsanan S R — Thu, 20 Aug 2020 14:50:39 +0000

Hello Dev Community,

Happy to share my very first article. I recently started with #100DaysOfCode on Twitter. I got to meet awesome developers who were very good & unique.

Often saw many people sharing useful information for free to help fellow newbies & developers. This got me thinking, I haven't done much for the dev community and this article is just a brainchild.

I will try to go through one of the sorting algorithms (easiest to catch) that I learnt so far in the past few days.

Before we move on any further, I just want to say, it's easy!

We will start with the classic Bubble Sort algorithm

You can go through this video from HackerRank to get a hint on how it works?

https://www.youtube.com/watch?v=6Gv8vg0kcHc

In Bubble Sort, we compare two of the adjacent element and swap their places. Upon one successful iteration over the elements, you will get the largest of the number on the right-hand side of the array. We will not touch the sorted element (right-hand side) on the successive iteration.
You have to repeat the same until your array is sorted.

Below is a pure function based implementation

function bubbleSort(iterarr){

    if(!Array.isArray(iterarr)){ // Checking given input is a valid array
        console.error('Not an array!');
        return;
    }

    let arr = [...iterarr]; // Copied the array elements using spread operator

    if(arr.length == 1){
        return arr; //If array has only one element it's already sorted
    }

    let isSorted = false; //Assuming the array is not sorted

    while(!isSorted){ //Loop breaks if the array is sorted
        isSorted = true; //Assuming the array is sorted
        for(let i = 0; i < arr.length - 1; i++){ //Loop for iterating through elements
            if(arr[i] > arr[i+1]){ //Trying to check which of the element is bigger current(i) or the next element(i+1)
                let temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp; //Above 3 lines does the swapping using the temp variable
                isSorted = false; //If swap happens that means array is not sorted yet
            }
        }
    }
    return arr;
}

Though this is not an optimal sorting method, it's one of the easiest.

I hope you like this article. Please share any comments if you have, I will try to address them one step at a time.

Thanks,
Sudharsanan Ravichandran