Stack Overflow
Stack Overflow

Questions tagged [quickselect]

Use this tag with questions about the Quickselect algorithm, an algorithm to find the nth smallest member in a list.

Links

See Also

85 questions
312
votes
33 answers

Write a program to find 100 largest numbers out of an array of 1 billion numbers

I recently attended an interview where I was asked "write a program to find 100 largest numbers out of an array of 1 billion numbers." I was only able to give a brute force solution which was to sort the array in O(nlogn) time complexity and take…
userx
  • 3,713
  • 5
  • 32
  • 38
32
votes
6 answers

QuickSelect Algorithm Understanding

I've been poring over various tutorials and articles that discuss quicksort and quickselect, however, my understanding of them is still shaky. Given this code structure, I need to be able to grasp and explain how quickselect works. // return the kth…
Edge
  • 2,456
  • 6
  • 32
  • 57
17
votes
4 answers

Quickselect time complexity explained

From https://en.wikipedia.org/wiki/Quickselect it says "However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from…
ealeon
  • 12,074
  • 24
  • 92
  • 173
7
votes
1 answer

Quick select with repeat values

Is it possible to perform searching kth elment in O(n) over multiset (values can repeat)? Because as far as I understand the idea of quick select I have to partition input using some pivot. Then I have 2 arrays, which I choose for recursive…
abc
  • 2,371
  • 3
  • 25
  • 36
6
votes
1 answer

"quick select" (or similar) implementation on Linux? (instead of sort|uniq -c|sort -rn|head -$N)

PROBLEM: Frequently I face a need to see what are the most-frequently-repeated "patterns" within last day of specific logs. Like for a small subset of tomcat logs here: GET /app1/public/pkg_e/v3/555413242345562/account/stats 401 954 5 GET…
Vlad
  • 1,157
  • 8
  • 15
4
votes
1 answer

numpy.partition in JavaScript

Is there a readily available equivalent to numpy.partition in JavaScript, via a library or built in? It does not seem like any of the popular relevant libraries such as underscore.js provide such a function. I am asking because I would like to be…
Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
4
votes
1 answer

Efficient algorithm of partial sorting into N unsorted groups

I'm looking for an efficient algorithm to perform the following: given an array of N items, sort it in a way so that items come as M equal groups, where each group is unsorted, but groups are sorted between each other (all elements in one group are…
Mourner
  • 3,171
  • 24
  • 21
3
votes
2 answers

Fastest way to multithread doing quickselect on all columns or all rows of a matrix in Rcpp - OpenMP, RcppParallel or RcppThread

I was using this Rcpp code to do a quickselect on a vector of values, i.e. obtain the kth largest element from a vector in O(n) time (I saved this as qselect.cpp): // [[Rcpp::depends(RcppArmadillo)]] #include using namespace…
Tom Wenseleers
  • 7,535
  • 7
  • 63
  • 103
2
votes
1 answer

How to implement duplicates in QuickSelect

I have made the quick select algorithm, which is to find the kth smallest number in an array. My problem is, it only works with an array without duplicates. If I have an array arr = {1,2,2,3,5,5,8,2,4,8,8} It will say that the third smallest…
user7722505
2
votes
1 answer

quick select is not working for all indexes

I am trying to implement quick select referring to a algorithm given in the following link http://www.cs.yale.edu/homes/aspnes/pinewiki/QuickSelect.html But the program crashes for many k values, and works fine for only few. Kindly guide me where i…
user2805439
  • 45
  • 1
  • 6
2
votes
1 answer

QuickSelect vs. linear search

I am wondering why QuickSelect is supposed to be such a good performing algorithm for finding an arbitrary element out of an n-sized, unsorted set. I mean, when you go through all elements one by one, until you find the desired one it took O(n)…
wodzu
  • 3,004
  • 3
  • 25
  • 41
2
votes
1 answer

can we prove that the algorithm to extarct the median must partition the set?

Extracting the median of, say, 51 element, consists of splitting the 51 in a H(ead) group of 25, followed by the median, followed by a T(ail) of 25. All the algorithms that I know end up with the additional property that H and T are such that…
quickbug
  • 4,708
  • 5
  • 17
  • 21
2
votes
1 answer

interpreting a laconic ruby 'nil' error

I've been at this for a couple of days now, and I can't crack this error: [3] pry(main)> my_list = (1..10).to_a.sample(10) => [3, 5, 9, 2, 7, 6, 10, 4, 1, 8] [4] pry(main)> linear_select(my_list,4) NoMethodError: undefined method `-' for…
bright-star
  • 6,016
  • 6
  • 42
  • 81
1
vote
1 answer

OutOfMemoryError when trying to find the largest kth element in a large array

I am trying to solve a task that asks me to find the largest kth element in an unsorted array of length n (n might be as large as 5,000,000; elements in the array are distinct). Due to the task limits, I cannot use any sorting method, PriorityQueue,…
user18512699
  • 11
  • 1
1
vote
0 answers

Divide an array into 2 subarray considering keys and weights

Let there be an array A with n elements. Every element in A has a key, and a weight. Divide A into 2 subarrays (does not have to be of equal size), where every key in group 1 is smaller than every key in group 2, and the total weight of both…
Nati Shen-Gordon
  • 25
  • 5
1
2 3 4 5 6