Implementing Sorting Algorithms in JavaScript for better Performance
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:
- Insertion Sort
- Quick Sort
- Merge Sort
- Bubble sort
- 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:-
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
const array = [9,8,2,4,6,7];
const sortedArray = insertionSort(array);
console.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 and 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:-
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) left.push(arr[i]);
else right.push(arr[i]);
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const array = [23,87,4,8,23,1,7];
const sortedArray = quickSort(array);
console.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:-
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
const array = [5,9,12,34,23,78,12,9];
const sortedArray = mergeSort(array);
console.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:-
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n-1; i++)
for (let j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
return arr;
}
const array = [5,9,12,34,23,78,12,9];
const sortedArray = bubbleSort(array);
console.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:-
function selectionSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
var min = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min !== i) {
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
return arr;
}
const array = [5,9,12,34,23,78,12,9];
const sortedArray = selectionSort(array);
console.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.
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.
FAQS
.png)
WhatsApp
Call Us
Mail Us