Find the average number of steps to sort an array by randomly selecting two elements I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = [7, 5, 3, 4, 2, 6, 10, 1, 9, 8]). I can choose two random number and if the list from left number larger then right number I swap them (for example 2 and 5  list[2] larger then list[5] so I'll swap them and etc).
Need to find average number of all choosings to order the sequence.
The algorithm should executed less then 1 second.
Can anybody help me?
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).