未加星标

Quicksort implementation JavaScript

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二05 | 时间 2018 | 作者 红领巾 ] 0人收藏点击收藏
Quicksort

it is an efficient sorting algorithm for the larger datasets where it

performs faster than themerge sort and heap sort.

It was Developed by British computer scientist Tony Hoare in 1959 and published in 1961.

How does quicksort works? Array has 5 items [ 3 ,6 , 4, 1, 2 ]

1). first we need to choose the pivot value from the array we can choose any thing as a pivot value but we are choosing last item 2 as a pivot.

2). Next, we need to loop through the array and compare with pivot if any item which is less than pivot place on left-hand side else if any item is greater than the pivot place on the right-hand side.


Quicksort implementation JavaScript

3) We need to run the quickSort recursively on right part and left part


Quicksort implementation JavaScript
Quicksort algorithm

Let's implement a quicksort algorithm.

First, we are creating a function with three parameters which are arr, length and start.

arr: unsorted array

length: how many times we need to loop it means we already choosing the last item as pivot value so our loop needs to end before the pivot value.

start: loop starts from 0.

function quickSort(arr,length = arr.length-1,start=0){ if(arr.length < 2) return arr const pivot = arr[arr.length-1]; const left = [ ]; const right = [ ]; }

Next, we are using a while loop it helps us to loop over the items in the unsorted array and if any item which is less than pivot value push into the left array else push into the right array.

function quickSort(arr,length = arr.length-1,start=0){ if(arr.length < 2) return arr const pivot = arr[arr.length-1]; const left = [ ]; const right = [ ]; while (start < length) { if (arr[start] < pivot) left.push(arr[start]) else right.push(arr[start]) start++ } }

the final step we need to run the quickSort recursively on both left-hand side and right-hand side.

function quickSort(arr, length = arr.length - 1, start = 0) { if (arr.length < 2) return arr // base case const pivot = arr[arr.length - 1]; //pivot value const left = [ ]; const right = [ ]; while (start < length) { if (arr[start] < pivot) left.push(arr[start]) else right.push(arr[start]) start++ } return [...quickSort(left), pivot, ...quickSort(right)]; } console.log(quickSort([4, 9, 2, 6, 8, 10, 3, 1, 7, 5])) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Time complexity Quicksort

Average case - O(nlogn)

Best case - O(nlogn)

Tested using Mocha and chai

Hope you enjoyed...

In the next tutorial, we are going to learn radix sort.

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

代码区博客精选文章
分页:12
转载请注明
本文标题:Quicksort implementation JavaScript
本站链接:https://www.codesec.net/view/610751.html


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(63)