 # Swaps count during predefined sorting algorithm

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.

The problem is all about finding the number of inversions in the given array.

1 Like