Sorting is a fundamental operation in computer science and programming. It allows us to organize data in a specific order, making it easier to search, analyze, and present information effectively. In the world of web development, JavaScript is one of the most popular programming languages used for creating dynamic and interactive web applications. In this blog, we will explore various sorting algorithms and how to implement them in JavaScript.

Sorting is considered to be an important concept in many programming languages as it helps us locate elements in a faster and easier manner.

Now we will learn how to use sorting algorithms to sort an array. there are around 8 types of sorting algorithms in javascript, in this blog we will discuss the most common types of sorting algorithms we come across in JavaScript which are the following:

• Bubble Sort

• Insertion Sort

• Merge Sort

• Quick Sort

• Selection Sort

• Radix sort

---

Bubble Sort

A bubble sort algorithm is a very common algorithm and is usually one of the first things taught in a computer science class. This is because a bubble sort works in a very similar manner to how we human beings would sort through items.

Let’s start by creating a function named bubbleSort. This function will take in an array as an argument, which it will manipulate in order to sort and then return that array back to us.

In this algorithm, we will create a loop where we compare an item with the next one in the array. If the current item is greater than the next one, then they will get swapped. This loop will keep repeating itself until we come across the scenario where none of the current items are greater than the one next to it. This is why we will use the do while loop instead of a regular while loop.

The do while loop needs an argument that it will check before running. Let’s name this argument as swap and set its initial value as false.

Inside the loop, we will check if the current item is greater than the next one in the array. If it is, then we will first store it in a temporary variable, then perform the swap. To indicate that the swap is performed, we will set the value of swap to true.

To test this algorithm, simply create an array of numbers and pass it into the bubbleSort function as shown below:

const nums = [5, 10, 1, 9, 2, 8, 3, 7, 4, 6]
bubbleSort(nums)

In your output, you will notice that the algorithm prints out the end result multiple times before terminating. This is because the algorithm makes one last run across all the elements of the array to make sure that they are sorted properly.

Insertion Sort Algorithm

In the insertion sort algorithm, we make the code believe that an item in the array is a sorted list. The algorithm then compares all the items in the array before it and decides where that “sorted list” needs to be inserted in the array.

This may sound a little confusing to you. And it is justifiable since we need to you two loops, one inside another, in order to perform this algorithm.

To start, we will create a function called insertionSort that will take in the array as an argument. We will use nested loops to perform the sorting. Here’s how the loops will work.

First, we will take an element from the array and check if it's greater or smaller than the element next to it. The outer for loop will start from the second element of the array and will run for the entire length of the array.

The inner loop will start from the beginning of the array and will run until the current element of the outer loop. The inner loop will also reset every time the outer loop’s iterating variable’s value increases.

As for the actual sorting, we will compare the outer loop's element with the inner loop's element. If the outer loop’s element is smaller, then we will move it to the position of the inner loop’s element and vice versa. To do this we will use the array’s slice method.

Let’s use the same array that we used before and test this algorithm

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
insertionSort(numbers)

And that should work! If you consider the movement of 8, you will notice that starts to stay at the same position for a while, and the duration gets bigger with each iteration. That is because, the algorithm moves through all the items of the array, then increments the value of the outer loop’s iterator, and then when it comes across the element 8, it will work on it before moving on to the next element in the array.

Merge Sort Algorithm

Divide and Conquer! This is the principle behind the working of the merge sort algorithm. The algorithm breaks down an array into smaller arrays. It will then sort these smaller arrays as they are quicker due to their smaller size. Finally, the smaller arrays are brought together to give us the final sorted array.

While the bubble and insertion sort algorithms use iteration, merge sort uses recursion. Recursion is where the function calls itself. Iteration, on the other hand, involves something else in our code running a block of code multiple times.

Here we will divide the array into two parts, which will then be divided into smaller parts, until we get a set of arrays where each array contains only 2 elements. Then we will sort this small array simply by comparing which element is greater/smaller and join these arrays back again.

Let’s start by creating a function called divide which will receive an array as an argument. The function will then check if the length of the array is already less than 2, because if it is, then don’t need to divide anything, since less than 2 is 1, and you really don’t have anything else in the array to compare with. In this scenario, the algorithm will simply return the same array back to us.

If the array is longer than 2, then we will divide it into two parts. First, we need to find the middle number of the array. Once we get that, we will use the splice method to create the two smaller arrays.

We will create another function that does the actual sorting. I will call it…. sort. The sort function will take the two small arrays as arguments and sort each of them individually, and join them together. The function will contain an array where the sorted elements will be stored.

There will be a scenario where we have sorted both the smaller arrays, but there are still elements in the original array left. In such a case, we need to first join the two small arrays together and place the remaining elements in a new array.

You can test this algorithm by passing an array of numbers to the divide function.

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
console.log(divide(numbers))

Quick Sort

This is another algorithm that follows the “divide and conquer” method. The algorithm first creates two smaller arrays and also picks an index from the array. All the elements of the array are compared with this element and get pushed into one of the two arrays based on a comparison. The sorting is then done on one of the two arrays.

As with every other algorithm in this post, we will create a function that will take the array of numbers as an input argument. If the array has only one element, sorting can be ignored and the same array can be returned.

We will then choose the element of the array and store it in a separate variable. Then, we will create two arrays where the elements will be push after comparing with the last element of the array. For that, we will use a for loop that will iterate through every element in the array.

Similar to mergeSort, we will use the spread operator ( ... ) to insert the elements from the two arrays and the chosen element into a new and final array.

Testing this algorithm with an array of numbers should give us the following output:

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
quickSort(numbers)
// Output
5 6
3 4 5 6
1 2 3 4 5 6
8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 // Final Answer

Selection Sort

Selection Sort is a simple and intuitive comparison-based sorting algorithm. It works by repeatedly finding the minimum (or maximum) element from the unsorted part of the array and swapping it with the first unsorted element. This process continues until the entire array is sorted.

How Does Selection Sort Work?

The Selection Sort algorithm follows these steps:

1. Starting from the first element, assume it to be the smallest (or largest) element in the array.

2. Iterate through the unsorted part of the array to find the actual smallest (or largest) element. Swap this element with the first element.

3. Move the boundary between the sorted and unsorted parts one element to the right.

4. Repeat steps 1 to 3 until the entire array is sorted.

function selectionSort(arr) {
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;

        // Find the index of the smallest element in the unsorted part
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the found smallest element with the first element of the unsorted part
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }

    return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // Output: [11, 12, 22, 25, 34, 64, 90]

Selection Sort Algorithm Implementation

To implement Selection Sort in a computer program, you can use nested loops. The outer loop iterates through the array from the first element to the second-to-last element, and the inner loop finds the minimum element from the unsorted part of the array and swaps it with the current element of the outer loop.

Radix Sort

Radix Sort is a non-comparative sorting algorithm that operates by distributing elements into buckets based on their digits. It is particularly useful when sorting integers or strings of fixed length. Instead of comparing elements directly, Radix Sort exploits the positional representation of numbers or characters to achieve its sorting objective.

How does Radix Sort work?

The Radix Sort algorithm works in the following steps:

1. Determine the maximum number of digits (d) in the input array or strings. This value will determine the number of iterations needed to complete the sorting process.

2. Starting with the least significant digit (rightmost), perform a stable sort on the input array. A stable sort ensures that the relative order of elements with the same key remains preserved.

3. Move on to the next significant digit and repeat the sorting process. Continue this process until the most significant digit (leftmost) has been processed.

4. The input array is now sorted in ascending order.

Implementation of Radix Sort in JavaScript:

Let's implement the Radix Sort algorithm in JavaScript:

function countingSort(arr, exp) {
    const n = arr.length;
    const output = new Array(n).fill(0);
    const count = new Array(10).fill(0);

    for (let i = 0; i < n; i++) {
        count[Math.floor(arr[i] / exp) % 10]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = n - 1; i >= 0; i--) {
        output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
        count[Math.floor(arr[i] / exp) % 10]--;
    }

    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}
unction radixSort(arr) {
    const max = Math.max(...arr);
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSort(arr, exp);
    }
    return arr;
}

// Example usage:
const unsortedArray = [170, 45, 75, 90, 802, 24, 2, 66];
const sortedArray = radixSort(unsortedArray);
console.log(sortedArray); // Output: [2, 24, 45, 66, 75, 90, 170, 802]

---

Comparison between Sorts interms of thier time complexities:

• Bubble Sort - O(n^2)

• Insertion Sort - O(n^2)

• Selection Sort - O(n^2)

• Quick Sort - O(nlog(n))

• Merge Sort - O(nlog(n))

• Radix Sort - O(n)

---

Conclusion

Sorting is an essential skill for every JavaScript developer, as it helps optimize data processing and presentation. In this blog, we explored various sorting algorithms, including Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort, with examples of their implementations in JavaScript. Each algorithm has its advantages and use cases, so it's crucial to understand their strengths and weaknesses when choosing the appropriate sorting method for different scenarios. Happy coding! 😄