What are Sorting Algorithms?

Sorting algorithms are an essential part of computer science and are used to rearrange a collection of items into a particular order. In JavaScript, several sorting algorithms can be implemented to sort arrays of elements.

In this article, we will explore 5 of the most commonly known sorting algorithms and their implementation in JavaScript. We’ll cover:

1. Insertion Sort
2. Quick Sort
3. Merge Sort
4. Bubble sort
5. Selection Sort

Insertion Sort:

Insertion Sort is a straightforward sorting algorithm that builds the final sorted array by iteratively inserting each element into its correct position relative to the already sorted elements. Starting with the second element, it compares and inserts elements one by one, extending the sorted sublist until the entire array is sorted. While not as efficient as some advanced algorithms on large datasets, Insertion Sort is simple and has low overhead, making it suitable for small or partially sorted datasets.

Example:-

1function insertionSort(arr) {
2  for (let i = 1; i < arr.length; i++) {
3    let current = arr[i];
4    let j = i - 1;
5    while (j >= 0 && arr[j] > current) {
6      arr[j + 1] = arr[j];  
7      j--;
8    }
9    arr[j + 1] = current;
10  }
11  return arr;
12}
13const array = [9,8,2,4,6,7];
14const sortedArray = insertionSort(array);
15console.log(sortedArray);

Time Complexity:

• Best Case: O(n) when the array is nearly sorted; the insertionSort function only needs to make one pass through the array
• Worst Case: O(n^2), where n is the number of elements; the insertionSort function may need to pass through the array multiple times
• Average Case: O(n^2) when the array is sorted in reverse order; the insertionSort function will need to do the maximum amount of work, making multiple passes through the array

Quick Sort

QuickSort is a widely employed sorting algorithm that operates on the principle of divide and conquer. It selects a pivot element from the array, rearranges the elements so that those smaller than the pivot are on its left, and those larger are on its right. The pivot assumes its final sorted position, and the process is repeated recursively on the sub-arrays on the left and right of the pivot until the entire array is sorted.

It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Example:-

1function quickSort(arr) {
2  if (arr.length <= 1) return arr;
3  const pivot = arr[0];
4  const left = [];
5  const right = [];
6  for (let i = 1; i < arr.length; i++) {
7    if (arr[i] < pivot) left.push(arr[i]);
8    else right.push(arr[i]);
9  }
10  return [...quickSort(left), pivot, ...quickSort(right)];
11}
12const array = [23,87,4,8,23,1,7];
13const sortedArray = quickSort(array);
14console.log(sortedArray);

Time Complexity:

• Best Case: The most favorable scenario where an algorithm performs optimally.
•  Worst Case: O(n^2) where the pivot element is the smallest or largest element, which leads to unbalanced partitions.
• Average Case: O(n log n) where n is the number of elements; the array is divided into a balanced manner in most of the steps, leading to a highly efficient sorting time

Merge Sort

Merge Sort is a sorting algorithm that employs the divide-and-conquer strategy. It recursively divides an array into halves until each sub-array contains a single element, then merges the sorted sub-arrays to produce a fully sorted array. The key to its efficiency is the merging step, where two already sorted arrays are combined. Merge Sort has a stable time complexity of O(nlogn), making it suitable for large datasets, and it performs consistently well across various input scenarios, albeit with a slight overhead due to its recursive nature.

Merge sort is a more efficient sorting algorithm that uses the divide-and-conquer approach to sort an array. It divides the array into smaller sub-arrays, sorts them, and then merges them back together.

Example:-

1function mergeSort(arr) {
2  if (arr.length <= 1) return arr;
3  const middle = Math.floor(arr.length / 2);
4  const left = arr.slice(0, middle);
5  const right = arr.slice(middle);
6  return merge(mergeSort(left), mergeSort(right));
7}
8
9function merge(left, right) {
10  let result = [];
11  let leftIndex = 0;
12  let rightIndex = 0;
13  while (leftIndex < left.length && rightIndex < right.length) {
14    if (left[leftIndex] < right[rightIndex]) {
15      result.push(left[leftIndex]);
16      leftIndex++;
17    } else {
18      result.push(right[rightIndex]);
19      rightIndex++;
20    }
21  }
22  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
23}
24const array = [5,9,12,34,23,78,12,9];
25const sortedArray = mergeSort(array);
26console.log(sortedArray);

Time Complexity:

• Best Case: O(nlogn) when the input is already partially or completely sorted. 
• Average Case: O(nlogn) - consistently efficient across different scenarios. 
• Worst Case: O(nlogn) when the input is completely unsorted. Merge Sort's reliable and balanced performance makes it a popular choice for sorting large datasets.

Bubble sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated for each pair of adjacent elements until the entire list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list while larger elements "sink" to the bottom. Bubble Sort has a worst-case and average-case time complexity of O(n 2 ), making it less efficient compared to more advanced algorithms like QuickSort or Merge Sort. Despite its simplicity, Bubble Sort is not commonly used in practical applications for large datasets due to its inefficiency.

It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The process is repeated until the list is sorted.

Example:-

1function bubbleSort(arr) {
2    let n = arr.length;
3    for (let i = 0; i < n-1; i++)
4        for (let j = 0; j < n-i-1; j++)
5            if (arr[j] > arr[j+1]) {
6                let temp = arr[j];
7                arr[j] = arr[j+1];
8                arr[j+1] = temp;
9            }
10    return arr;
11}
12const array = [5,9,12,34,23,78,12,9];
13const sortedArray = bubbleSort(array);
14console.log(sortedArray);

Time Complexity:

• Best Case: O(n) when the array is already sorted. 
• Average Case: O(n 2 ) - generally less efficient for larger datasets. 
• Worst Case: O(n 2 ) when the array is in reverse order. Bubble Sort is simple but less practical for large datasets compared to more advanced sorting algorithms.

Selection Sort

Selection Sort is a simple sorting algorithm that repeatedly selects the minimum element from the unsorted portion of the array and swaps it with the first unsorted element. This process is iteratively applied until the entire array is sorted. Selection Sort has a worst-case, average-case, and best-case time complexity of O(n 2 ), making it less efficient for large datasets compared to more advanced sorting algorithms like Merge Sort or QuickSort. Despite its simplicity, Selection Sort is not commonly used for large-scale applications due to its quadratic time complexity.

It works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

Example:-

1function selectionSort(arr) {
2  let len = arr.length;
3  for (let i = 0; i < len - 1; i++) {
4    var min = i;
5    for (let j = i + 1; j < len; j++) {
6      if (arr[j] < arr[min]) {
7        min = j;
8      }
9    }
10    if (min !== i) {
11      let temp = arr[i];
12      arr[i] = arr[min];
13      arr[min] = temp;
14    }
15  }
16  return arr;
17}
18const array = [5,9,12,34,23,78,12,9];
19const sortedArray = selectionSort(array);
20console.log(sortedArray)

Time Complexity:

• Best Case: O(n 2 ) when the array is already sorted. 
• Average Case:O(n 2 ) - involves quadratic comparisons and swaps.
• Worst Case: O(n 2 ) when the array is in reverse order. While simple to implement, Selection Sort is less efficient for larger datasets compared to more advanced sorting algorithms.

FAQS - Javascript Algorithms

What is the fastest Javascript Algorithm ?

Quick sort is often one of the fastest sorting algorithms for general use cases. It has an average-case time complexity of O(n log n) and is efficient for large datasets

Is there a sort method in Javascript ?

In JavaScript, the sort() method is used to sort the elements of an array in place and returns the sorted array. By default, the sort() method sorts the elements of an array as strings, converting each element into a string and then comparing them based on their UTF-16 code units values.

How can I sort an array in JavaScript ?

You can use the Array.prototype.sort() method, which sorts the elements of an array in place and returns the sorted array.

What is a recursive function, and how can I use it in JavaScript algorithms ?

A recursive function is a function that calls itself. You can use recursion to solve problems that can be broken down into smaller, similar sub-problems.

What is the time complexity of common JavaScript array operations ?

The time complexity of common array operations in JavaScript, such as accessing elements, inserting elements, and deleting elements, is O(1) for operations that access or modify elements at a specific index and O(n) for operations that search for an element or iterate over the array.

Conclusion

In conclusion, sorting algorithms are fundamental tools in computer science and are essential for organizing and manipulating data. In JavaScript, developers have access to a variety of sorting algorithms, each with its own characteristics and performance considerations. Understanding the inner workings of sorting algorithms can empower JavaScript developers to make informed decisions about which algorithm to use based on the size of the data set, the distribution of the data, and the specific requirements of the application.

While some sorting algorithms, such as bubble sort and insertion sort, are straightforward to implement but may not be the most efficient for large data sets, others like merge sort, quick sort offer better performance at the cost of increased complexity. By familiarizing themselves with these sorting algorithms and their JavaScript implementations, developers can optimize the performance of their applications when working with arrays and data manipulation. In summary, a solid understanding of sorting algorithms in JavaScript is a valuable asset for any developer seeking to write efficient and scalable code.