If you had n objects in no particular order how many compari

If you had n objects in no particular order, how many comparisons would be needed to sort the objects by weight if you did nothing more sophisticated than nd the lightest object, then the second lightest...?

Solution

First we will try to see the number of comparisions required to find the lightest object. After we have sorted it out, we will use the similar procedure to find the second lightest object from the group of n-1 objects. This process will be carried out till we find the heaviest object.

First to find the lightest object we will keep all the n objects in a row. After that we will compare object 1 and 2 and which ever of them is lighter we will compare it with the third object in the row. This process will go on till we have compared with the nth ball. Thus it can be clearly seen that to find the lightest object among n objects we will need to carry out n-1 comparisions.

After the lightest one has been singled out, we will create another row and put this lightest one in the beginning of this second row. Now we carry out the same operation to find the second lightest object. This time we are going to need n-2 comparisions.

Similarly the comparisions will be carried out until the last of the balls is sorted.

Thus the total number of comparisions required = (n-1)+(n-2)+(n-3)........2+1 = n(n-1)/2