CODEWITHSUNDEEP
c++algorithmsorting
kunal gupta
kunal gupta

Reputation: 57

Algorithm to sort an array for first element then first 2 elements then first 3 elements and so on

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?

Upvotes: 4

Views: 529

Answers (3)

maxim1000
maxim1000

Reputation: 6365

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).

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23955

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 |

Upvotes: 2

jferard
jferard

Reputation: 8180

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.

Upvotes: 2

Related Questions