JavaScript Algorithms: Quicksort

Quicksort is a more efficient searching algorithm than selection sort, in most cases, and it makes use of recursion.

Recursion means we call a function from within the same function. It’s a very useful practice, sometimes, and this is o…


This content originally appeared on flaviocopes.com and was authored by flaviocopes.com

Quicksort is a more efficient searching algorithm than selection sort, in most cases, and it makes use of recursion.

Recursion means we call a function from within the same function. It’s a very useful practice, sometimes, and this is one of those cases.

I said “in most cases”, because as we’ll see, in the worst case bubble sort can take the same time of selection sort: O(n^2). But in the best case scenario, it will run at O(n log n), which is in the middle between O(n) and O(n^2).

How does it work? Given an array, we pick an item, called pivot. We then get all the items smaller than the pivot, and the items bigger than the pivot.

Then we run the same operation on the 2 array that compose the smaller and bigger items.

It’s easier to see the code than to describe it:

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 this case I chose the pivot to be the first item in the array, but it could also be the item in the middle, for example:

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

Notice how we first copy the array, so calling quickSort() does not modify the original array, it just returns a new sorted array:

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]


This content originally appeared on flaviocopes.com and was authored by flaviocopes.com


Print Share Comment Cite Upload Translate Updates
APA

flaviocopes.com | Sciencx (2020-11-23T05:00:00+00:00) JavaScript Algorithms: Quicksort. Retrieved from https://www.scien.cx/2020/11/23/javascript-algorithms-quicksort/

MLA
" » JavaScript Algorithms: Quicksort." flaviocopes.com | Sciencx - Monday November 23, 2020, https://www.scien.cx/2020/11/23/javascript-algorithms-quicksort/
HARVARD
flaviocopes.com | Sciencx Monday November 23, 2020 » JavaScript Algorithms: Quicksort., viewed ,<https://www.scien.cx/2020/11/23/javascript-algorithms-quicksort/>
VANCOUVER
flaviocopes.com | Sciencx - » JavaScript Algorithms: Quicksort. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2020/11/23/javascript-algorithms-quicksort/
CHICAGO
" » JavaScript Algorithms: Quicksort." flaviocopes.com | Sciencx - Accessed . https://www.scien.cx/2020/11/23/javascript-algorithms-quicksort/
IEEE
" » JavaScript Algorithms: Quicksort." flaviocopes.com | Sciencx [Online]. Available: https://www.scien.cx/2020/11/23/javascript-algorithms-quicksort/. [Accessed: ]
rf:citation
» JavaScript Algorithms: Quicksort | flaviocopes.com | Sciencx | https://www.scien.cx/2020/11/23/javascript-algorithms-quicksort/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.