/

Efficient Searching with Quicksort in JavaScript

Efficient Searching with Quicksort in JavaScript

Quicksort is a highly efficient algorithm for searching and sorting arrays in JavaScript. It makes use of recursion, which involves calling a function from within the same function. This technique helps streamline the search process and improve performance.

Generally, Quicksort outperforms other algorithms like selection sort, especially in scenarios where the data set is large. The algorithm’s time complexity is generally O(n log n), which falls between O(n) and O(n^2). However, it’s worth noting that in the worst-case scenario, Quicksort can take the same time as selection sort, resulting in a time complexity of O(n^2).

The working principle of Quicksort involves selecting a pivot item from the array and dividing the remaining items into two subarrays - one with items smaller than the pivot and another with items larger than the pivot. This process is then recursively repeated on the two subarrays until the entire array is sorted.

Let’s take a look at the JavaScript code implementation of Quicksort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const quickSort = (originalList) => {
 const list = [...originalList]

 if (list.length < 2) {
 return list
 }

 const pivot = list[0]

 const smaller = list.filter((item) => item < pivot)
 const bigger = list.filter((item) => item > pivot)

 return [...quickSort(smaller), pivot, ...quickSort(bigger)]
}

In the code snippet, the pivot is initially set to the first item of the array. However, you can also choose other pivot options, such as the item in the middle of the array. Remember to make a copy of the array before calling quickSort() to prevent modifying the original array.

1
const pivot = list[Math.floor(list.length / 2)]

To demonstrate how Quicksort works, consider the following example:

1
2
3
4
5
6
7
const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a))
//[0, 1, 1, 3, 4, 4, 5, 6, 8

console.log(a)
//[1, 6, 3, 4, 5, 1, 0, 4, 8]

In this example, the array a is sorted using the quickSort() function, which returns a new sorted array without modifying the original array.

By leveraging the power of recursion and choosing an efficient pivot strategy, Quicksort provides a reliable and fast sorting solution for JavaScript arrays.

tags: [“JavaScript”, “algorithms”, “searching”, “sorting”, “Quicksort”]