Suppose you are looking to order a group of people from shortest to tallest and that no two people in the group have the same height. In order to do this, you start from left to right and compare the leftmost person to all of the rest. You do this even if you know that the first person is already the shortest. If they are not, you make them swap places with the shortest person you find among the rest.
Then you move on to the second person from left to right, comparing them to all of the rest—who are only the ones on the second person's right side (so the leftmost person is now out of the comparison). If they are the second-shortest, you leave them where they are. If not, you make them swap places with the second-shortest person.
You do this until you have sorted the whole group by height from shortest to tallest.
Suppose the number of people in the group is n. Given that you make the above comparisons whether or not the person you are currently comparing to those on their right side is the shortest, how many comparisons will this process involve to go over all of the group?
Please put any answers behind spoilers.
Then you move on to the second person from left to right, comparing them to all of the rest—who are only the ones on the second person's right side (so the leftmost person is now out of the comparison). If they are the second-shortest, you leave them where they are. If not, you make them swap places with the second-shortest person.
You do this until you have sorted the whole group by height from shortest to tallest.
Suppose the number of people in the group is n. Given that you make the above comparisons whether or not the person you are currently comparing to those on their right side is the shortest, how many comparisons will this process involve to go over all of the group?
Please put any answers behind spoilers.