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
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
Any help or direction will be appreciated!