Here, we define a nearly-sorted array with k-sized error, as this: Elements in the array may be in the wrong order, but only if they are not distanced by more than k indices. For example:

1, 2, 3, 6, 5, 4, 7, 8, 9

The 6 and the 4 are in the wrong order, and they are 2 indices apart from one another. The rest of the elements are in order, or of less than 2 indices apart. So the above array is nearly-sorted with an error size 2.

The question is, how to "tweak" the simple and basic version of the QuickSort algorithm, to have it produce a nearly-sorted array instead of a fully-sorted array, given a certain k, and thereby making it faster than O(nlgn)?

I've been thinking about this for days now, and I can't seem to understand how "ignoring" some of the elements while sorting, in any way, can ever change the run-time complexity of the algorithm, where k is constant?

I could easily just stop the recursion if size < k instead of size < 2, which would indeed make it faster by a tiny bit, and will indeed have possible errors, but wouldn't it still be O(nlgn)?

Any help or direction will be appreciated!


closed as off topic by Kaveh Nov 26 '12 at 22:46

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What is the motivation for your question? Is this an assignment? $\endgroup$ – Kaveh Nov 26 '12 at 22:36
  • $\begingroup$ @Kaveh Yes, it is. $\endgroup$ – SimpleVar Nov 26 '12 at 22:41
  • $\begingroup$ cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Assignment questions are generally off-topic here. $\endgroup$ – Kaveh Nov 26 '12 at 22:42

You can't do it. Suppose you start with an array where everything is sorted to distance $k$. Then, you can use a modified QuickSort to sort this array in time $n \log k$.

First, choose pivot elements every $k$ elements. Now, sort the array so everything is in place with respect to these elements. (You can do this in time $O(n)$ using a modified version of Quicksort. First, put everything to the left of the first pivot element on the correct side of this pivot element. This takes $O(k)$ time. Next, put everything between the first and second pivot elements on the correct side of the second pivot element. Repeat for the rest of the pivot elements, from left to right.) Finally, sort each of the sublists between the pivot elements.

This will take total time $O(n \log k)$. Now, if you could take an arbitrary array to a nearly-sorted array in time less than $o(n\log n - n \log k)$, we would sort in time $o(n \log n)$. We can't do this.

Thus, there is an $\Omega(n \log \frac{n}{k})$ time bound on near-sorting.

  • $\begingroup$ Isn't MergeSort an O(nlgn) algorithm? $\endgroup$ – SimpleVar Nov 26 '12 at 22:34
  • $\begingroup$ @Yorye: this isn't MergeSort. $\endgroup$ – Peter Shor Nov 26 '12 at 22:35
  • $\begingroup$ @Yorye: Why do you believe it's possible? $\endgroup$ – Peter Shor Nov 26 '12 at 22:39
  • 1
    $\begingroup$ In my highlighted algorithm above, we sort $n/k$ lists of size each at most $3k$. The total time required for this is $O(3k \log 3k \cdot n/k) = O(n \log k)$. $\endgroup$ – Peter Shor Nov 26 '12 at 22:43
  • 1
    $\begingroup$ @Yorye: Maybe you should read the assignment more carefully, or maybe you shouldn't trust them. $\endgroup$ – Peter Shor Nov 26 '12 at 22:46

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