UBER Coding Question – Solved

Count Swaps During Custom Sorting Analyze the efficiency of the following sorting algorithm by counting the number of swaps it performs: For an array arr of size n: 1. Find the smallest pair of indices 0 ≤ i < j ≤ n-1 such that arr[i] > arr[j], where "smallest" means lexicographical ordering of pairs (i1, j1) < (i2, j2) if i1 < i2 or (i1 = i2 and j1 < j2). 2. If no such pair exists, the algorithm stops. 3. Otherwise, swap arr[i] and arr[j] and search for the next pair. Your task is to determine how many swaps this algorithm performs to sort a given array. Example n = 4, the size of arr arr = [5, 1, 4, 2] The algorithm performs these swaps: [5, 1, 4, 2] → [1, 5, 4, 2] (swap indices 0 and 1) [1, 5, 4, 2] → [1, 4, 5, 2] (swap indices 1 and 2) [1, 4, 5, 2] → [1, 4, 2, 5] (swap indices 2 and 3) [1, 4, 2, 5] → [1, 2, 4, 5] (swap indices 1 and 2) The total number of swaps is 4. Function Description Complete the function howManySwaps in the editor with the following parameter(s): int arr[]: the array to sort Returns int: the number of swaps Constraints 1 ≤ n ≤ 10^5 1 ≤ arr[i] ≤ 10^9 All elements of arr are distinct. Input Format for Custom Testing Sample Case 0 Sample Input arr[] size n = 3 arr = [7, 1, 2] Sample Output 2 Explanation [7, 1, 2] → [1, 7, 2] → [1, 2, 7]