blog bg

August 27, 2024

Sorting Algorithms in JavaScript: Radix Sort, Merge Sort, and Quick Sort

test-img
Share what you learn in this blog to prepare for your interview, create your forever-free profile now, and explore how to monetize your valuable knowledge.

Sorting algorithms are essential for various applications in computer science. Among the most widely used sorting algorithms are Radix Sort, Merge Sort, and Quick Sort. Each of these algorithms has unique characteristics, benefits, and ideal use cases. In this blog, we'll explore these three sorting algorithms and provide JavaScript implementations for each.

 

Radix Sort

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It is particularly efficient for sorting numbers with a fixed number of digits.

 

How Radix Sort Works

  1. Determine the maximum number of digits in the largest number.
  2. Iterate from the least significant digit (LSD) to the most significant digit (MSD).
  3. Sort the array based on each digit using a stable counting sort.

 

JavaScript Implementation

function getMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

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

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

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

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

  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
}

function radixSort(arr) {
  let max = getMax(arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSort(arr, exp);
  }
}

// Example usage
let arr = [170, 45, 75, 90, 802, 24, 2, 66];
radixSort(arr);
console.log(arr);

 

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the array into smaller subarrays, sorts them, and then merges them back together.

 

How Merge Sort Works

  1. Divide the array into two halves.
  2. Recursively sort each half.
  3. Merge the two sorted halves into a single sorted array.

 

JavaScript Implementation

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)).concat(right.slice(rightIndex));
}

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

// Example usage
let arr = [38, 27, 43, 3, 9, 82, 10];
arr = mergeSort(arr);
console.log(arr);

 

Quick Sort

Quick Sort is another divide-and-conquer algorithm. It works by selecting a "pivot" element and partitioning the array into elements less than the pivot and elements greater than the pivot, and then recursively sorting the partitions.

 

How Quick Sort Works

  1. Choose a pivot element.
  2. Partition the array into two subarrays based on the pivot.
  3. Recursively sort the subarrays.

 

JavaScript Implementation

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high);

    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

// Example usage
let arr = [10, 7, 8, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr);

 

Conclusion

Each of these sorting algorithms—Radix Sort, Merge Sort, and Quick Sort—has its own strengths and use cases:

  • Radix Sort is efficient for fixed-digit numbers.
  • Merge Sort is stable and works well with large datasets.
  • Quick Sort is generally faster in practice with an average-case time complexity of O(n log n).

Understanding these algorithms and their implementations in JavaScript can help you choose the right one for your specific needs.

380 views

Please Login to create a Question

Posts

Questions

Blogs

Jobs