Find the average number of steps to sort an array by randomly selecting two elements
The average number is hard, an upper bound isn’t.
You have n numbers, therefore n(n-1) / 2 pairs of numbers. On average half of those pairs are in the wrong order. You need to figure out the distribution for that.
Now if you have k pairs in the wrong order, the probability of picking two random numbers in the wrong order is 2k / n / (n-1). If you pick two numbers in the wrong order and exchange them, the number of incorrectly ordered pairs goes down at least by one. So you expect n(n-1)/2k picks to go from k inversions to k-1 or fewer. (The “fewer” makes it hard to analyse).