How to use Quickselect Algorithm In Javascript

Using Set() Method

Quickselect is a selection algorithm similar to Quicksort. It selects the kth smallest/largest element from an unsorted array in expected O(n) time complexity, where n is the number of elements in the array.

Follow the given steps to solve the problem:

Choose a pivot element from the array.
Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
Recur for the appropriate sub-array based on the position of the pivot after partitioning.
Repeat the process until the pivot element is the kth smallest/largest element.

Syntax:

function quickSelect(arr, left, right, k) { }

Example: Below is the implementation of the above approach.

JavaScript

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

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

function quickSelect(arr, left, right, k) {
    if (left === right) return arr[left];

    let pivotIndex = partition(arr, left, right);

    if (k - 1 === pivotIndex) {
        return arr[pivotIndex];
    } else if (k - 1 < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

let arr = [1, 3, 2, 4, 8, 7, 5, 6];
let k = 3;

console.log("N'th Smallest: ", quickSelect(arr.slice(), 0, arr.length - 1, k));
console.log("N'th Largest: ", quickSelect(arr.slice(), 0, arr.length - 1, arr.length - k + 1));

Output

N'th Smallest:  3
N'th Largest:  6

JavaScript Program to find the Nth smallest/largest element from an unsorted Array

In this article, we will see how to find Nth largest and smallest element from an unsorted array. The Nth smallest/largest element from an unsorted array refers to the element that ranks at the Nth position when the array is sorted either in ascending (smallest) or descending (largest) order. It represents the value at the Nth position when considering all unique values in the array.

Examples:

Input:  
arr[]={1, 3, 2, 4, 8, 7, 5, 6}, 
N=3
Output:
largest=6,
smallest=3

There are several methods that can be used to find the Nth smallest/largest element from an unsorted Array in JavaScript, which are listed below:

Table of Content

Using Sorting() Method
Using Set() Method
Using Quickselect Algorithm

We will explore all the above methods along with their basic implementation with the help of examples.

Tags:

#javascript-array #JavaScript #Web Technologies

Using Set() Method

How to use Quickselect Algorithm In Javascript

JavaScript Program to find the Nth smallest/largest element from an unsorted Array

Similar Reads

Contact Us