0

The question goes like this-

Assuming I have an Array of real numbers X[x1,...,xn] and a natural constant k such that for every i X[i]<X[i+k]. Write a sorting algorithm with time complexity better than O(nlogn). For the purpose of the question I am allowed to use quick sort, counting sort, Radix sort, bucket sort, heaps and so on.

All I've figured out so far is that if I take sublists by the remainder of the indecies (after dividing with K), those sublists are sorted. But merging them in the right complexity seems impossible. I also tried using min heaps after realizing the i smallest value must be in the first k*i places but it took me O(n^2) which is too much. I'd appreaciate any guidance/help/references. Thank you!

Improve this question
3
  • When you say "unique array" do you mean that all the values in the array are unique (i.e. no duplicates)? Commented Dec 1, 2022 at 22:30
  • All I am given is that for every i X[i]<X[i+k] and that's what I meant by unique. Commented Dec 1, 2022 at 22:46
  • 1
    Shell sort is probably simpler code, although it's worstcase time complexity isn't as good as the minheaps solution. In practice, it might well be faster and it doesn't require any auxiliary memory. Commented Dec 2, 2022 at 21:16

1 Answer 1

Reset to default
2

Something to note here is that you essentially have k sorted arrays that you could merge directly. That is, the sequence [x[i],x[i+k],x[i+2k],x[i+3k]...] is sorted. As is [x[i+1],x[i+k+1],[x[i+2k+1]...]

So you have to merge k sorted sequences. The basic idea is:

  1. Initialize a priority queue of size k with the first item from each sorted sequence. That is, add x[0], x[1], x[2], x[3] ... x[k-1] to the priority queue. In addition, save the index of the item in the priority queue structure.
  2. Remove the first item from the queue and add the next item from that sequence. So if the first item you remove from the queue is x[3], then you'll want to add x[3+k] to the queue.
  3. You'll of course have to make sure that you're not attempting to add anything from beyond the end of the array.
  4. Continue in that fashion until the queue is empty.

Complexity is O(n log k). Basically, every item is added to and removed from a priority queue of size k. Both addition and removal are, worst case, O(log k).

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

2 Comments

Thank you very much! This is the direction I had in mind when I said I tried using min heaps but indeed you showed me something I was missing. I tried writing a pseudocose, do you think it describes well enough what you meant? ibb.co/cQn395C
@DR_2001 On a quick scan, that pseudocode looks right. It's certainly going in the right direction.

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.