Learn How to Write a Quick Sort Algorithm Using JavaScript

Sort in programming involves placing the elements in a list or array in a specific order. Efficient sorting is important for optimizing other algorithms that require input data to be placed in sorted lists.

Although it may not be necessary, it is not necessary to implement an algorithm classification in your daily life, Nowadays, as a software developer, it is important to know how some of these algorithms work internally. They are common in programming interviews and will make you a more effective developer.

In today’s article, we will explore two of the most popular sorting algorithms: Merge Sort and Sorting quick. . They are essential for your foundation in computer science and code optimization.

Today we will learn:

• Introduction to classification algorithms
• Algorithm Union Sorting Algorithm
• Fast Sorting Algorithm
• What You Should Learn Next

Introduction to Sorting Algorithms union sort

A sort algorithm is an algorithm used to rearrange the elements of a list or array based on a specific requirement. For example, sorting algorithms can arrange a series of elements from smallest to largest.

An effective sorting algorithm is important to improve the efficiency of other algorithms (e.g. search). .optimize). and compression algorithms).

Classification algorithms consist of a series of instructions. Take an array or list as input, perform operations, and generate a sorted array.

There are several popular sorting algorithms. The nine most popular are:

• Bubble sort
• Insertion sort
• Merge sort
• Quicksort
• Selection sort
• Counting sort
• Bucket sort
• Radix sort
• Heapsort

Related: What Are Some Real Life Uses Of Merge Sort, Insertion Sort, Quick Sort And Heap Sort Algorithms?

Merge Sort Algorithm

Merge Sort is an efficient, generic, comparison-based sorting algorithm. It works by recursively splitting an array into two equal halves, sorting them, and then merging each sorted half.

Take an array [10, -1, 2, 5, 0, 6, 4, -5]. Here’s how merge sort would work.

The merge sort and quick sort implementations are examples of a divide and conquer algorithm. In general, a divide and conquer algorithm consists of the following parts:

• Divide: involves dividing the problem into subproblems.
• Conquer: recursive processing of subproblems until each is solved
• Combine: Combine solved subproblems to obtain a solution to the original problem

Combined classification can be used for all types of problems. The three most common uses of merge sort are O(nLogn-time) linked list sorting, an inverse counting problem, and external sorting.

JavaScript Implementation

Below is the code implementation of a merge sort algorithm in JavaScript. The algorithm consists of two functions:

The mergeSort() function, which is responsible for partitioning the arrays

The merge function, which joins separate tables

function mergeSort(array) {
  if (array.length === 1) {
    return array;
  }
  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.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)).concat(right.slice(rightIndex));
}

Let’s try to detail what is happening:

• If the array has only one element, we return the array and the game is done ( Base case )
• Otherwise, we divide the array into two halves that have the same possible length (division)
• Using recursion, we sort both arrays using the mergeSort( function ). (Conquer)
• Finally, we merge the two sorted arrays and return the result. (Merge)

So let’s take the table we used in the previous example. Let’s see how to implement merge sort in JavaScript code.

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

  const middle = Math.floor(unsortedArray.length / 2);

  const left = unsortedArray.slice(0, middle);
  const right = unsortedArray.slice(middle);

  return merge(
    mergeSort(left), mergeSort(right)
  );
}

Time and space complexity

Merge sort has a guaranteed time complexity of O(nlogn)

, which is significantly faster than average and, in the worst case, most part of the cases, various other algorithm classifications. The union order is a stable order with a space complexity of O(n).

• Auxiliary space: O(n)
• Merge sorting algorithm: parts and prevail
• In-place sorting: No
• Stable: Yes

Comparison with other sorting algorithms

Sorting after merging is slightly slower in practice than Quicksort. It also doesn’t take up as much space as the local Quicksort implementation. Due to the difference in memory allocation, MergeSort is generally preferred over QuickSort for linked lists.

QuickSort Algorithm

QuickSort, like Merge Sort, is a divide and conquer algorithm, but it works slightly differently. Quicksort begins by selecting a pivot element in the array and dividing the other elements into two subarrays based on whether they are smaller or larger than the pivot element. The subarrays are then sorted recursively.

The Quicksort algorithm does not consume additional space because the sorting is performed in place.

There are several ways this algorithm can select a pivot element.

• Select the first element as the pivot element
• Select last element as pivot
• Select random element as pivot
• Select median as pivot

JavaScript Implementation

The next key process is our partition function, which selects our pivot. In this implementation, this is done using the Hoare partitioning scheme, where two indices are initialized starting from the ends of the array. The indices approximate each other until an inversion is found.

An inversion is a pair of elements, one greater than or equal to the Pivot, one less than or same as Pivot.

which are in the wrong order with each other. The inverted values ​​are then swapped and the process is repeated.

Selecting a good pivot is the key to a quick Quicksort implementation. In practice, Quicksort algorithms use a random pivot whose expected time complexity is O(nlogn).

function partitionHoare(array, left, right) {
  const pivot = Math.floor(Math.random() * (right - left + 1) + left);
  while (left <= right) {
    while (array[left] < array[pivot]) { 
       left++;
    } 
    while (array[right] > array[pivot]) {
      right--;
    }
    if (left <= right) {
      [array[left], array[right]] = [array[right], array[left]];
    }
  }
  return left;
}

function quicksort(array, left, right) {
  left = left || 0;
  right = right || array.length - 1;
  const pivot = partitionHoare(array, left, right);
 
  if (left < pivot - 1) {
     quicksort(array, left, pivot - 1);
  }
  if (right > pivot) {
     quicksort(array, pivot, right);
  }
  return array;
}

Time Complexity

Quicksort algorithm has a time complexity of O(nlogn). In the worst case, this becomes O(n2). The space used by Quicksort depends on the version used.

The in-place version of Quicksort has a space complexity of O(logn), even in the worst case, while the average-case space complexity is O(n)O(n).

• Algorithmic Paradigm: Divide and Conquer
• Sorting in Place: Yes
• Stable: Default is not stable

Comparison with other sorting algorithms

While the average and best-case run time of Quicksort is equal to that of other algorithms such as Merge Sort, a well-implemented Quicksort will have much lower constant factors than other sorting algorithms.

In the case of Quick Sort, in its general form is an in-place sort (i.e. it doesn’t require any extra storage). Merge sort requires O(N) extra storage, where N denotes the array size which may be quite large.

What to learn next

Sorting is the basis of many complex programming solutions. Though it may seem like a simple concept, sorting is one of the many types of algorithms tested in coding interview.

In practice, a sorting algorithm’s efficiency or speed may sometimes depend on the type of data-set being sorted. You should look into the following algorithms next:

• Insertion Sort
• Bubble Sort
• Selection Sort
• Heapsort
• Bucket Sort

To get started with these concepts, check out Educative’s learning path Ace the Front end Interview. You’ll review all the key concepts you need to be familiar with in CSS, HTML, and JavaScript, practicing and diving deep into dozens of real questions. By the time you’re done, you’ll be able to tackle anything that comes your way on the front-end interviews.