3

Problem -Nearly Sorted Array- Given an array of n elements , each of which is atmost K Position away from it's actual position in the sorted array , devise an algorithm that sorts in O(nLogK) time.

Approach - I divide the array in n/K elements each(n/k + 1 , if n%k!=0).

Then I run a loop n/k times ,inside which I sort eack n/k group using 
MergeSort(Complexity = KLogK).So complexity for the loop is O(nLogK).

Finally I merge the n/k groups using a Merge Function(similar to Merging 
K Sorted arrays, complexity = nLog(n/k)).

So overall complexity is between nLogK and nLog(n/K) but I have to 
achieve complexity O(nLogK).
Comparing K and n/K depends on values of n and K.

Can anyone help me with the final merging operation or a better approach.

PS : I do not know heaps or queues at the time so I am looking for a solution which does not involve these.

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
Armaan
  • 101
  • 10
  • i'm actually not sure, if merge-sort is the right approach here, maybe it's better to use some variation of bubble-sort, since bubble sort performs better, if input is already nearly sorted, like in your example – JohnnyAW Apr 10 '19 at 15:37
  • Insertion sort is an option but with greater complexity – Armaan Apr 10 '19 at 16:23
  • well, insertion sort has better performance if the input is nearly sorted, in best case(input is fully sorted) it's complexity is O(n) – JohnnyAW Apr 10 '19 at 16:35
  • If using only insertion sort the complexity will be O(nk) – Armaan Apr 10 '19 at 16:37
  • I don't tell you to use insert-sort instead of merge-sort, I tell you to overthink your whole algorithm and make it like a insert-sort with slightly modification – JohnnyAW Apr 10 '19 at 16:41
  • Consider a radically different algorithm, with an ancillary heap of size `k`. – user58697 Apr 10 '19 at 22:29

1 Answers1

5

First, divide the array into groups of at least k+1 elements. So that each element's rightful position is either within the group where the element currently is or within the group to the left or to the right, but not further. Then sort each group.

This step takes O((n/k) * k log k) = O(n log k).

Then, after sorting each group, you can merge ith group with the i+1 group, for i from 1 to n/(k+1) - 1.

By merge I understand the merge procedure from a merge sort. The groups do not unite. Their sizes remain the same.

Each merge takes O(n/k), in total this step is O(n).

Dave
  • 7,460
  • 3
  • 26
  • 39
ciamej
  • 6,918
  • 2
  • 29
  • 39
  • somehow i don't understand your merge, do you merge all groups into 1 big result? if so, you would need more time for every consecutive merge... – JohnnyAW Apr 10 '19 at 15:32
  • 2
    @JohnnyAW You only have to merge each group with its direct neighbours. That's because even before sorting each group, each element is at most k-elements away from its proper position. – ciamej Apr 10 '19 at 15:58
  • Ok, I've just noticed that my method requires that each element is at most k-1 positions away. But that's fine we can divide the array into slightly larger groups n/(k+1) elements each. – ciamej Apr 10 '19 at 16:19
  • wait, I think we would get 4 arrays with length 3 each for merge: [1,2,4][2,4,5][2,3,5][3,5,6] but still, after final merge we get 3 arrays with length 6? – JohnnyAW Apr 10 '19 at 16:22
  • n = 9, k = 2: [1,4,2,5,3,8,9,6,7] => [1,2,4][3,5,8][6,7,9] => [1,2,3][4,5,8][6,7,9] => [1,2,3][4,5,6][7,8,9] – ciamej Apr 10 '19 at 16:22
  • The last two steps are merge group 1 with 2, and merge group 2 with 3 – ciamej Apr 10 '19 at 16:23
  • @JohnnyAW, basically the merges just move the elements between the groups, but leave the groups' boundaries as they are. – ciamej Apr 10 '19 at 16:25
  • @ciamej Merging that way , the work done would be like 2k + 3k + 4k .. which will not be linear. It will turn out to be O(n^2 /K) – Armaan Apr 10 '19 at 16:28
  • @ciamej the second step doesn't make sense: [1,4,2,5,3,8,9,6,7] => [1,2,4][3,5,8][6,7,9] =>(I don't think you can merge like this...) [1,2,3][4,5,8][6,7,9] => [1,2,3][4,5,6][7,8,9] – JohnnyAW Apr 10 '19 at 16:30
  • @JohnnyAW Why is that? You take [4,5,8] and [6,7,9] merge it to [4,5,6,7,8,9] and leave it as it is [4,5,6][7,8,9]. The boundaries between groups are only imaginatory... – ciamej Apr 10 '19 at 16:33
  • @JohnnyAW if it's easier for you to understand, then each merge is followed by a split in half. This split is a no-op in reality. – ciamej Apr 10 '19 at 16:35
  • @ArmaanChugh no, each step is `O(k)` you always take two groups of the same size. In my example the size is 3. The size of groups does not increase with each merge. The groups remain the same size. – ciamej Apr 10 '19 at 16:37
  • @ciamej ok, I think I understand the merge, but what if n=8? do you have overlapping groups? – JohnnyAW Apr 10 '19 at 16:39
  • @JohnnyAW if the `n%(k+1) != 0` then the last group can be smaller. – ciamej Apr 10 '19 at 16:43
  • @ciamej wait, but then your merge complexity would be O(2*n/(k+1)) and not O(n/k) – JohnnyAW Apr 10 '19 at 16:48
  • @JohnnyAW Each merge takes `O(2 * (k+1)) = O(k)` steps. There is exactly `floor(n / (k+1))` merges, which gives us a total of `O(floor(n / (k+1)) * k) = O(n)` steps. – ciamej Apr 10 '19 at 16:54
  • @ciamej oh, right, merge is O(2k), but you can't simplify it to O(k) so in the end you get O(n/k*2*k) = O(2n) – JohnnyAW Apr 10 '19 at 17:00
  • 1
    @JohnnyAW `O(2k) = O(k)` by definition. – ciamej Apr 10 '19 at 17:01
  • @ciamej ok, I think I got it now :D – JohnnyAW Apr 10 '19 at 17:12
  • @ciamej why do you specify dividing the array into groups of at least k+1 elements? Why not k? – Jash Shah Jun 13 '22 at 10:19
  • 1
    @JashShah Honestly, I don't remember! When I think about it now, I think I made an error. Groups of size k should be fine. – ciamej Jun 14 '22 at 15:26