Thread: Explanation of selection sort, which uses arithmetic progression

I'm training to be a software developer but I'm afraid some basic Maths has gotten in my way.
We're learning about sorting right now, the first of which is a basic selection sort algorithm. Take the following numbers:

[ 9, 5, 17, 11, 12 ]

It takes the first number and sets it as the minimum number and compares it to everything after it. As 5 is smaller than it, it swaps the two numbers around and moves on. This leaves us with:

[ 5, 9, 17, 11, 12 ]

Next, it takes 5 as the minimum number. If searches the numbers after it and as none are smaller than 5, it stays in position and so on. This leaves us with the same terms:

[ 5, 9, 17, 11, 12 ]

The sort effectively works its way from left to right, leaving the numbers sorted as it goes.
Our lecturer has told us that it is sorted in the following way.

To find the smallest, visit n elements and make 2 visits to perform the swap.
To find the next smallest, visit (n-1) elements and make 2 visits to perform the swap.
To find the last term, visit 2 elements and make 2 visits to perform the swap.

This translates to:

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

I know this equation then simplifies to this:

n2/2 + 5n/2 - 3

However, for the life of me, I cannot see how the top equation translates to this. I know that the formula to find the sum of terms in an arithmetic progression is this:

n/2 [2a + (n-1)d] OR n/2 [a + l] where a = first term d = common difference and l = last term.

Despite using this, I don't get the right answer. Could somebody please walk me through, STEP BY STEP!!, as to how I get to the answer?

Kind regards and many thanks in advance.

Edit: Wanted to add that I posted this in the pre-university forum as I remember studying this at A Level - just can't remember the outcome!!

So you have [n + 2] + [(n-1) + 2] + [(n-2) + 2] + ... ... + [1+ 2] + [0+ 2] and want to know how that is equal to n^2/2+ 5n/2- 3? Well, it's NOT! If n= 2, that would be [2+ 2]+ [1+ 2]+ [0+ 2]= 4+ 3+ 2= 9. That is NOT 2^2/2+ 5(2)/2- 3= 2+ 5- 3= 4.

To sum [n + 2] + [(n-1) + 2] + [(n-2) + 2] + ... ... + [1+ 2] + [0+ 2], note that you have n+ 1 terms (from n down to 0), so you are adding 2 n+ 1 times and that sums to 2(n+1)= 2n+ 1. The sum 1+ 2+ ...+ (n-1)+ n is, as you say, an arithmetic progression and sums to n(n+1)/2. So your sum is 2n+1+ n(n+1)/2= 2n+ 1+ n^2/2+ n/2= n^2/2+ 3n/2+ 1.

Could I ask you then a slightly strange follow up question. This is the website I originally posted this question on (and didn't understand the answer!)
algorithms - Basic Maths question regarding the selection sort formula. - Mathematics

Could I ask you what the person did wrong in the answer here? The reason why I'm asking is because both he and my lecturer have come up with the n^2/2 + 5n/2 - 3. I've also googled the formula, and the -3 one is the one that is generally listed. Please note - I'm not for a moment suggesting that your answer isn't correct. Rather I'm just trying to emphasize how confused I've gotten over this formula and how, as I can't find consensus on the outcome, I can't figure out how to get there! Thank you for the very clear answer you have given so far.

Edit: To actually explain my post further, I'm not sure your formula would work. You asked how it would work if 2 were substituted in to the formula. But as the collection of numbers is random and unsorted, it would be impossible to find any particular nth term - all that I can find is the sum of all terms? I think? ... Possibly lol. I really don't know.

Okay, my lecturer has emailed it to me and explained it like this. It's a weird sequence. Because it takes a collection of random, unsorted numbers the formula only tells the number of processes that are needed to sort a collection of numbers.

The formula is effectively broken into two separate sequences:

1. n + (n-1) + (n-2) + (n-3) + (n-4) + ... + 2
2. 2 + 2 + 2 + 2 etc.

The first part can be rearranged to look like this:

1. 2 + 3 + 4 + 5 + 6 ... + n. This is effectively the same as 1 + 2 + 3 + 4 ... + n.

However, in our sequence, we are not starting at 1, but rather 2, this 1 must be taken off the output of this one row of sums.

The formula to calculate this line is: n/2 [2a + (n-1)d]. This gives n/2 [2*1 + (n-1)*1]. This gives n/2 [2 + n - 1]. Which is: n/2[n + 1]. Which is: n2/2 + n/2.
When we remember to take our 1 off, we get the final formula for the first part of the sum:

(n2/2 + n/2) - 1

The second line contains all 2s, and (n-1) of them are needed. This gives the formula 2(n-1), which is: 2n - 2

Putting the two formulae together gives: n2/2 + n/2 - 1 + 2n - 2.

Simplified, this is: n2/2 + n/2 - 3 + 2n

Multiply the 2n by 2 so it is over the number 2 as well gives the final output:

n2/2 + n/2 - 3 + 4n/2, which is: n2/2 + 5n/2 - 3

Any thoughts folks? I'm still fairly confused!