CODEWITHSUNDEEP
arraysalgorithmsortingapproximation
Abdullah Raya
Abdullah Raya

Reputation: 61

approximate sorting Algorithm

Does anyone know an Algorithm that sorts k-approximately an array?

We were asked to find and Algorithm for k-approximate sorting, and it should run in O(n log(n/k)). but I can't seem to find any.

K-approx. sorting means that an array and any 1 <= i <= n-k such that sum a[j] <= sum a[j] i<=j<= i+k-1 i+1<=j<= i+k

Upvotes: 5

Views: 2457

Answers (1)

John Devitt
John Devitt

Reputation: 736

I know I'm very late to the question ... But under the assumption that k is some approximation value between 0 and 1 (when 0 is completely unsorted and 1 is perfectly sorted) surely the answer to this is quicksort (or mergesort).

Consider the following array:

[4, 6, 9, 1, 10, 8, 2, 7, 5, 3]

Let's say this array is 'unsorted' - now apply one iteration of quicksort to this array with the (length[array]/2)th element as a pivot: length[array]/2 = 5. So the 5th element is our pivot (i.e. 8):

[4, 6, 2, 1, 3, 9, 7, 10, 8]

Now this is array is not sorted - but it is more sorted than one iteration ago, i.e. its approximately sorted but for a low approximation, i.e. a low value of k. Repeat this step again on the two halves of the array and it becomes more sorted. As k increases towards 1 - i.e. perfectly sorted - the complexity becomes O(N log(N/1)) = O(N log(N)).

Upvotes: 3

Related Questions