FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaScript/Sorts/QuickSortRecursive.js at master · TheAlgorithms/JavaScript · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
TheAlgorithms
/
JavaScript
Public
Uh oh!
There was an error while loading.
Please reload this page
.
Notifications
You must be signed in to change notification settings
Fork
5.8k
Star
34.2k
Code
Issues
21
Pull requests
192
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaScript
/
Sorts
/
QuickSortRecursive.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
65 lines (60 loc) · 2.16 KB
Breadcrumbs
JavaScript
/
Sorts
/
QuickSortRecursive.js
Copy path
File metadata and controls
65 lines (60 loc) · 2.16 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
Quicksort is the most popular sorting algorithm and there have
lots of different implementations but the "recursive" or "Partition in place"
is one of the most efficient implementations below we have discussed how to
implement it.
Partition in place => "in place" Partition in place indicates that we
do not need any other space to store the auxiliary array and the term
"partition" denotes that we split the list into two parts one is less
than the pivot and the other is greater than the pivot and repeats this
process recursively and breaks the problem into sub-problems and makes
it singular so that the behavior or "divide and conquer" get involved
too.
Problem & Source of Explanation => https://www.cs.auckland.ac.nz/software/AlgAnim/qsort1a.html
*/
/**
* Partition in place QuickSort.
*
@param
{
number[]
} inputList list of values.
*
@param
{
number
} low lower index for partition.
*
@param
{
number
} high higher index for partition.
*/
const
quickSort
=
(
inputList
,
low
,
high
)
=>
{
if
(
!
Array
.
isArray
(
inputList
)
)
{
throw
new
TypeError
(
'Please input a valid list or array.'
)
}
if
(
low
<
high
)
{
// get the partition index.
const
pIndex
=
partition
(
inputList
,
low
,
high
)
// recursively call the quickSort method again.
quickSort
(
inputList
,
low
,
pIndex
-
1
)
quickSort
(
inputList
,
pIndex
+
1
,
high
)
}
return
inputList
}
/**
* Partition In Place method.
*
@param
{
number[]
} partitionList list for partitioning.
*
@param
{
number
} low lower index for partition.
*
@param
{
number
} high higher index for partition.
*
@returns
{
number
} `pIndex` pivot index value.
*/
const
partition
=
(
partitionList
,
low
,
high
)
=>
{
const
pivot
=
partitionList
[
high
]
let
pIndex
=
low
for
(
let
index
=
low
;
index
<=
high
-
1
;
index
++
)
{
if
(
partitionList
[
index
]
<
pivot
)
{
// swap variables using array destructuring
;
[
partitionList
[
index
]
,
partitionList
[
pIndex
]
]
=
[
partitionList
[
pIndex
]
,
partitionList
[
index
]
]
pIndex
+=
1
}
}
;
[
partitionList
[
pIndex
]
,
partitionList
[
high
]
]
=
[
partitionList
[
high
]
,
partitionList
[
pIndex
]
]
return
pIndex
}
export
{
quickSort
}
Back
|
FazBrowse Home
|
New Git URL