GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — JavaScript/Search/QuickSelectSearch.js at master · TheAlgorithms/JavaScript

Expand file tree

/

QuickSelectSearch.js

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
55 lines (49 loc) · 1.53 KB
/

QuickSelectSearch.js

Copy path

File metadata and controls

55 lines (49 loc) · 1.53 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
/*
* Places the `k` smallest elements in `array` in the first `k` indices: `[0..k-1]`
* Modifies the passed in array *in place*
* Returns a slice of the wanted elements for convenience
* Efficient mainly because it never performs a full sort.
*
* The only guarantees are that:
*
* - The `k`th element is in its final sort index (if the array were to be sorted)
* - All elements before index `k` are smaller than the `k`th element
*
* [Reference](http://en.wikipedia.org/wiki/Quickselect)
*/
export function quickSelectSearch(array, k) {
if (!array || array.length <= k) {
throw new Error('Invalid arguments')
}
let from = 0
let to = array.length - 1
while (from < to) {
let left = from
let right = to
const pivot = array[Math.ceil((left + right) * 0.5)]
while (left < right) {
if (array[left] >= pivot) {
const tmp = array[left]
array[left] = array[right]
array[right] = tmp
--right
} else {
++left
}
}
if (array[left] > pivot) {
--left
}
if (k <= left) {
to = left
} else {
from = left + 1
}
}
return array
}
/* ---------------------------------- Test ---------------------------------- */
// const arr = [1121111, 21, 333, 41, 5, 66, 7777, 28, 19, 11110]
// quickSelectSearch(arr, 5) // [ 19, 21, 28, 41, 5, 66, 333, 11110, 1121111, 7777 ]
// quickSelectSearch(arr, 2) // [ 19, 5, 21, 41, 28, 333, 11110, 1121111, 7777, 66 ]
// quickSelectSearch(arr, 7) // [ 19, 5, 21, 41, 28, 66, 333, 7777, 11110, 1121111 ]
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.