Please provide the optimal code in CPP or Java for the below, I solved in brute force. Getting time limit exceed.
The following algorithm is proposed to be used to sort an array of distinct n integers:
For the input array arr of size n do:
-
Try to find the smallest pair of indices 0 \leq i < j \leq n-1 such that arr[i] > arr[j]. Here smallest means usual alphabetic ordering of pairs, i.e., (i1, j1) < (i2, j2) if and only if i1 < i2 or (i1 = i2 and j1 < j2).
-
If there is no such pair, stop.
-
Otherwise, swap a[i] and a[j] and search for the next pair.
Write a function that returns the number of swaps performed by the algorithm.
Constraints
- 1 \le n \le 10 5
- 1 \le arr[i] \le 10 9
Example
arr = [5, 1, 4, 2]
The algorithm first picks pair (5, 1) and swaps it:
[5, 1, 4, 2] rarr [1, 5, 4, 2] rarr [1, 4, 5, 2] rarr [1, 2, 5, 4] rarr [1, 2, 4, 5]. The number of swaps is 4.