4

I have a list of unsorted numbers and i want an algorithm such that I can get sorted list of first R elements but since this R can be different for different test cases I dont want to sort the array each time for the first R elements. Is there a Way by which i can get this done . One way possible is to maintain vector array such that I have first 1 number sorted then first 2 numbers sorted then first 3 numbers sorted and so on but it will take 1log1 + 2log2 + 3log3 + .... + nlogn time which is N^2logN complexity. Is faster way to this possible?

Improve this question
6
  • 5
    Are you perhaps looking for std::nth_element ? Commented Jun 3, 2018 at 18:17
  • 6
    Sorting the whole list and being done with it is impractical? Commented Jun 3, 2018 at 18:20
  • Basically if R is say 6 and I have a list of say 25 numbers then I should be able to apply all the operations of sorted array such as finding smallest no greater than a given number say S on the sorted list of first 6 elements so in short i need the sorted list of first R elements where R can be different in different test cases so if the whole list is sorted already i would not be able to get correct result of the smallest number greater than S because if say we have s=13 and in first 6 elements I have 1,2,3,17,18,20 then ans is 17 but later if 15 is added as 8th elemnt ans is 15 now ie wrong Commented Jun 3, 2018 at 18:30
  • @kunalgupta I don't understand the issue... If 15 is added, you just have to insert it in the right place? You should add examples of what you are trying to achieve because it's far from clear... Commented Jun 3, 2018 at 19:05
  • 1
    You could make a list of std::pair<int, int> where first is the number and second is the index in the unsorted list. Then after you sort it you can retrieve the first R numbers where second < R to get your list. Will save you a lot of sorting, but might not be any faster depending on the data. Commented Jun 3, 2018 at 19:21

3 Answers 3

Reset to default
2

It seems that the good old insertion sort will do better than O(N^2 lg N) in this case, because you don't need to sort elements from scratch for each  R. Imagine you have a copy of the sorted first n elements of the array for n in 1..R-1. Just insert the R-th element in a copy of the sorted array of the R-1 first elements (that's O(R)) and you get your sorted array of the R first elements.

That's O(N^2) if you want the result for every R in 1..N, but that will be less than O(N^2) in practice, because you can produce sorted arrays on demand, starting from the last sorted array with less elements than R.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Note that it's O(R) provided we already produced the sorted list of the first R-1 elements. The upper bound for an arbitrary R with this method is O(R^2).
2

We could take O(n log n) space to keep the partial results of a merge sort. Then the upper bound for returning the first R elements sorted would be akin to merging log n sorted lists. I found one reference for merging k sorted lists of total length n at O(n * log k), which would make ours O(n * log log n), but hopefully many of the queries would be even more efficient.

13,15,12,4,18,1,23,17,6,2 ->

| 1   2   4   6   12   13   15   17   18   23 |
| 4   12   13   15   18 | 1   2   6   17  23  | 
| 13  15  | 4   12   18 | 1   23 | 2   6  17  |
| 13 | 15 | 12 | 4 | 18 | 1 | 23 | 17 | 6 | 2 |
Improve this answer

Comments

1

You can try quicksort, but not do it entirely. I heard that Haskell does it in a similar way.

It's almost the usual quicksort, but you postpone work which can be postponed.

For the first element it will be just quickselect where you skip ranges irrelevant for the first element. But for every next element you should look for ranges which were not partitioned yet, but are needed for it and partition them.

Time for the first element will be O(n) (and you will unlikely get anything better), the entire time will be O(n * log n).

Additional memory for storing range positions seems to be O(log n), but I haven't thought about this enough to be sure.

Correction: if you need to output the entire subarray every time, that will make O(n^2), only if you output on number at a time - that will be O(n * log n).

Improve this answer

1 Comment

The expected output you seem to be answering to is the OPs vector array with 1 + 2 + 3...+ n or O(n^2) elements. We cannot bind the time lower than O(n^2) in that case, as you are suggesting. Did I misunderstand the output you are attempting to achieve?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.