current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
stack overflow careers
Sign up ×
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other. Join them; it only takes a minute:
up vote 9 down vote favorite
3

I had this question recently in an interview and I failed, and now search for the answer.

  1. Let's say I have a big array of n integers, all differents.

  2. If this array was ordered, I could subdivide it in x smaller arrays, all of size y, except maybe the last one, which could be less. I could than extract the nth subarray and return it, already sorted.

Example : Array 4 2 5 1 6 3. If y=2 and I want the 2nd array, it would be 3 4.

Now what I did is simply sort the array and return the nth subarray, which takes O(n log n). But it was said to me that there exists a way to do it in O(n + y log y). I searched on internet and didn't find anything. Ideas ?

share|improve this question
1  
Is the array starting from 1 in increasing order (just that it is shuffled) (e.g. 3,1,2,4)? Or is it random numbers which jumps? (e.g. 1,12,3,5) – user3437460 19 hours ago
1  
From what I undestood, it is random numbers, the only prerequisite is that they are all different. – Bene Tleilax 18 hours ago
    
Think about how quicksort works and then think how you would use it to make sure that say the array elements 101 to 150 are sorted. Hint: That means you don't need to sort say elements 1 to 100 when quicksort would do so. – gnasher729 14 hours ago

2 Answers 2

up vote 14 down vote accepted

The algorithm you are looking for is Selection Algorithm, which lets you find k-th order statistics in linear time. The algorithm is quite complex, but the standard C++ library conveniently provides an implementation of it.

The algorithm for finding k-th sorted interval that the interviewers had in mind went like this:

  • Find b=(k-1)*y-th order statistics in O(N)
  • Find e=k*y-th order statistics in O(N)
  • There will be y numbers between b and e. Store them in a separate array of size y. This operation takes O(N)
  • Sort the array of size y for O(y * log2y) cost.

The overall cost is O(N+N+N+y * log2y), i.e. O(N+y * log2y)

share|improve this answer
up vote 5 down vote

You can combine std::nth_element and std::sort for this:

std::vector<int> vec = muchData();
// Fix those bound iterators as needed
auto lower = vec.begin() + k*y;
auto upper = lower + y;

// put right element at lower and partition vector by it
std::nth_element(vec.begin(), lower, vec.end());
// Same for upper, but don't mess up lower
std::nth_element(lower + 1, upper - 1, vec.end());
// Now sort the subarray
std::sort(lower, upper);

[lower, upper) is now the k-th sorted subarray of length y, with the desired complexity on average.

To be checked for special cases like y = 1 before real world use, but this is the general idea.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.