Math Question for Fun!

[Debater Slayer]

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.

 

[ratiocinator]

No takers....? Okay.

Spoiler: My answer

You have n people, so you have to compare the first one with n-1 other people.

Once you've found the shortest you have n-1 people left.

You now pick your next in line and there are n-2 people to compare them with.

And so on. Hence, the total number of comparisons is

(n-1) + (n-2) + ... + 2 + 1.

So it's the sum of all positive integers less than n.

You could also look at it as building up from small numbers.

If you only have one person, there is no need to do any comparisons.

For 2 people, you have to do 1 comparison.

For 3, you need to compare the first with 2 others, then you've got 2 left, 1 more comparison, so 2 + 1. And so on.

There is actually a formula for the sum of all positive integers up to some number m, which is (m(m+1))/2, so for m = (n-1), we have the answer to your question, which is

(n(n-1))/2

The proof of the formula is the first on this page:

Sum of n, n², or n³ | Brilliant Math & Science Wiki

The series ...

brilliant.org

 

[Debater Slayer]

No takers....? Okay.

Spoiler: My answer

You have n people, so you have to compare the first one with n-1 other people.

Once you've found the shortest you have n-1 people left.

You now pick your next in line and there are n-2 people to compare them with.

And so on. Hence, the total number of comparisons is

(n-1) + (n-2) + ... + 2 + 1.

So it's the sum of all positive integers less than n.

You could also look at it as building up from small numbers.

If you only have one person, there is no need to do any comparisons.

For 2 people, you have to do 1 comparison.

For 3, you need to compare the first with 2 others, then you've got 2 left, 1 more comparison, so 2 + 1. And so on.

There is actually a formula for the sum of all positive integers up to some number m, which is (m(m+1))/2, so for m = (n-1), we have the answer to your question, which is

(n(n-1))/2

The proof of the formula is the first on this page:

Sum of n, n², or n³ | Brilliant Math & Science Wiki

The series ...

brilliant.org

Spoiler

Perfect! The algorithm in question is selection sort, which many people will already know:

Selection Sort Algorithm

Selection Sort Algorithm - Selection sort is a simple sorting algorithm. This sorting algorithm, like insertion sort, is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the...

www.tutorialspoint.com

 

[McBell]

Spoiler

I hate story problems

 

[ratiocinator]

Spoiler

Perfect! The algorithm in question is selection sort, which many people will already know:

Selection Sort Algorithm

Selection Sort Algorithm - Selection sort is a simple sorting algorithm. This sorting algorithm, like insertion sort, is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the...

www.tutorialspoint.com

Spoiler

Thought it looked familiar but did it from first principles because it seemed straightforward. IIRC it isn't the most efficient sort algorithm?

 

[Debater Slayer]

Spoiler

Thought it looked familiar but did it from first principles because it seemed straightforward. IIRC it isn't the most efficient sort algorithm?

Spoiler

Yes, its efficiency is not the best because it has the same time complexity in all cases: O(n²). It is also non-adaptive, so even if it receives an already-sorted array as its input, it will still make the same number of comparisons just as it would if every single element in the array were in the wrong place.