Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i and A[j] > A[i]. Give an optimal algorithm that computes the above array Inv_A. For example if A = [3,1,4,5,2] then Inv_A = [0,1,0,0,3]. Expected time complexity is O(nlogn).
3
-
$\begingroup$ What have you tried? Hint 1: try altering merge sort to compute the thing. Hint 2: or try using segment trees to compute the thing. $\endgroup$– GassaAug 9, 2022 at 18:39
-
$\begingroup$ What's your question? We are a question-and-answer site, so we require you to articulate a specific question about your situation. We're not particularly looking for posts that are just the statement of an exercise-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$– D.W. ♦Aug 9, 2022 at 20:04
-
$\begingroup$ What's the context where you encountered this task? Can you credit the original source? See cs.stackexchange.com/help/referencing $\endgroup$– D.W. ♦Aug 9, 2022 at 20:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Apply heap-sort for in-place sorting in $O(log(n))$ time. For a real application, it's better to use the simple randomized-quick-sort. You can get enough build-in routines in almost every popular language.
