# Basic Maths question regarding the selection sort formula.

I'm training to be a software developer and use Stack Overflow a lot, but I'm afraid some basic Maths has gotten in my way. I apologise in advance for a question that may be too easy to be posted here - if so, just tell me!

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. 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. It effectively works its way from left to right, leaving it sorted as it goes.

Our lecturer has told us that it is sorted in the following way.

To find the smallest, visit n elements + 2 visits for the swap.
To find the next smallest, visit (n-1) elements + 2 visits for the swap.
The last term is 2 elements visited to find the smallest + 2 visits for the swap.


This translates into

$n + 2 + (n-1) + 2 + (n-2) + 2 + \ldots + 2 + 2$

Up until now I'm fine and following it. Then however, he simplifies it to this:

$\displaystyle \frac{n^2}{2} + \frac{5n}{2} - 3$

I have no idea how he has gotten to this. Could anybody explain to me?

-
$n+(n-1)+(n-2)+\cdots+2$ is the sum of an arithmetic progression with $n-1$ terms, first term $n$, common difference $1$. The other summands in your sum are all twos, and there are $n-1$ of them. – Gerry Myerson Feb 18 '13 at 23:30
I see from looking online that the sum of an arithmetic progression with first term a1 is: Sn = n(a1 + an) / 2 However, I still don't see how I get from that to the simplification (apologies - don't know how to make the formula all neat and tidy like your lettering!) – Andrew Martin Feb 18 '13 at 23:41
The sum of an arithmetic progression with First term $F$, Last term $L$, and Total number of terms $T$, is $T(F+L)/2$. In $n+(n-1)+(n-2)+\cdots+2$, what is the first term? what is the last term? what is the total number of terms? and then what is the sum? – Gerry Myerson Feb 19 '13 at 0:01
Thanks for your help (so far!) – Andrew Martin Feb 19 '13 at 0:21
@GerryMyerson: Simple query. I assume that T(F+L)/2 is a rewriting of: Sn = ½ n [ 2a + (n - 1)d ] (which is what I was using). – Andrew Martin Feb 19 '13 at 13:13

If we split off every other $2$ we get two different sums: $$2 + 2 + \cdots + 2$$ and $$n + (n - 1) + \cdots + 3 + 2$$
The first is just $2(n - 1)$. For the second we add: $$x = n + (n - 1) + \cdots + 3 + 2$$ with $$x = 2 + 3 + \cdots + (n - 1) + n$$ (add down the columns, so $n + 2, (n - 1) + 3$, etc.) to get $$2x = (n + 2) + (n + 2) + \cdots + (n + 2) + (n + 2) = (n - 1)(n + 2)$$ so $x = \frac{1}{2}(n - 1)(n + 2)$. If you add these two totals together: $$2(n - 1) + \frac{1}{2}(n - 1)(n + 2)$$ you'll get the expression your professor gave you.
The last $4$ digits of the sum are $\cdots + 3 + 2 + 2 + 2$, when I take away every other two the last two digits are $\cdots + 3 + 2$. When you expand that expression the constant term is definitely $-3$. – Jim Feb 19 '13 at 0:14