C++ - Selection Sort

I was showing someone how to do the selection sort in C++ a few weeks ago.  I thought I'd also post the explanation for everyone else to see.

This shows the process for sorting an array of five elements using the selection sort method:

The array of numbers are:

A selection sort behaves in the following way:

Pass One:

During pass one, we are going to find the LOWEST number and have it switch places with the first element in the array.  Now, here's how we start looking:


The green arrow is pointing at the second number in the list.  For now, we're going to assume that the first element is the lowest in the list.

Now, 5 is less than 21, so we make the black arrow point to the number 5 - to keep track of the lowest number we have so far.

The green arrow, now points at 2.  2 is less than 5, so again we move the black pointer and have it point at 2 to keep track of it as the lowest number.

Now, 16 is being compared with the number 2.  16 is not less than 2, so the black arrow doesn't change positions, only the green one does.  Keep in mind that the green arrow is the number we are comparing with to see if it is lower than the one pointed to by the black arrow.

The green arrow now points at 8, which is still not less than 2. Now, we have determined that the number 2 is the lowest number in the list - which the black arrow is pointing at.  What we do is have the number 2 swap places with the value of the first element in the list - 21, like so:

The value of the third element swaps places with the value of the first element.

This completes pass one.

Pass Two:

On pass two, we have already found the smallest number in the list and we've moved it to the beginning of the list.  Since we now know that 2 is at the start of the list, we can begin checking the elements starting from the second element in the list; we make the black arrow point to the second element in the list.

Notice that on Pass Two, we start from the second element in the list.  On pass one, we were finding out what the lowest value in the list was.  On this second pass, we are going to find out the second-lowest value in the list.  For now, we have the black arrow pointing at the number 5, and we are going to compare it with all the other numbers in the list.  As you know by now the green arrow will point to each number in turn to see which is less than 5.  Since none of the numbers are less than 5, no swap is needed - nothing happens.

This ends Pass Two.

Pass Three:

On the third pass, we start at the third element.

For now, we again assume that the number in the third position (21) is the lowest value we have so far.  The green arrow points to the next value, 16, and we compare it with 21.  Now, 16 is lower so we have the black arrow point at it, to "keep track" of the lowest value we've found so far.

This brings us to:

Now, we compare 8 with 16.  Of course, 8 is lesser, so we have the black arrow pointing at the lowest element we've found.

At the end of this THIRD pass, we will put the number 8, which is the third-lowest value into the third element of the array:

Pass Three: Third Lowest Element in the entire list is found.

This ends Pass Three.

Pass Four:

Pass four is fairly simple, now.  We now make the black arrow point to 16 - the fourth element in the list (Pass four, element four); the green arrow is pointing at the next element after that which holds 21.

Now, we compare 21 with 16.  No swap is needed.  The array is now sorted.  This ends pass four and also, the entire sorting process.  Keep in mind that even though we had 5 elements to sort, we only needed 4 passes.  This holds true for ANY array size.  If you have 100 elements to sort, you will only need 99 passes to fully sort the array.

The C++ code is shown below - the variable names are blackArrow and greenArrow, so that it will be easier to follow the code using the explanation I've written above.

int array[] = { 21, 5, 2, 16, 8 };

int blackArrow = 0; //Will hold the index of the lowest value in the list each pass
int greenArrow = 0; //Will hold the index of the element we are comparing with the black arrow

for (int pass = 0; pass < 4; pass++)
{
blackArrow = pass;

for (int greenArrow = blackArrow + 1; greenArrow < 5; greenArrow++)
{
if (array[greenArrow] < array[blackArrow])
{
blackArrow = greenArrow;
}
}

//If pass is 0, then the lowest value found will be swapped with the value in array[0].

//If pass is 1, then the second-lowest value found will be swapped with the value in array[1].
//If pass is 2, then the third-lowest value found will be swapped with the value in the third position - array[2].
//If pass is 3, then the fourth-lowest value found will switch places with the value in the array's fourth position.
int temp = array[pass];
array[pass] = array[blackArrow];
array[blackArrow] = temp;
}

That's it, folks!  I hope that helps the beginner understand the selection sort - even just a little bit.

If you have any questions, email me at: sparkprogrammer@gmail.com

-Joe

New Announcement - Java Tutoring

Hi all,

I recently started tutoring people in Java.  Although, I admit, I'm much more comfortable with C++, I also know quite a bit of Java and have begun tutoring people in it.  Sooner or later, I'll start posting Java posts here as well.  If you need help understanding Java, let me know and I'll give it a shot!

Joe

Operator Overloading

First off: What is operator overloading?  You are simply providing a version of an operator (+, -, ++, etc..) that will handle YOUR object types.

An operator is just a function that you can call with operator syntax.  So, remember that to call a method, you would go:

object.Plus(1);

With operators, you can use operator syntax:
object + 1;

Now, what your version of the + operator does is completely up to you.  (I don't recommend this, but if you wanted to be sneaky, you could overload the + operator to do subtraction and the - operator to do addition!)

So, when overloading operators, we can do it two ways:
1. - Have them as MEMBERS of a class - methods
2. - Just have them as regular operator functions that belong to no class and can be called by anyone.
There are differences, between the two, but we'll take a look at each one.

First off, let's have a look at operator overloading where you do NOT make it a class method.
An example would be:

1. Object operator + (const Object &leftOperand, const Object &rightOperand) const
2. {
3.   //Suppose that Class Object has two data members: x and y
4.   Object temp;
5.   temp.x = leftOperand.x + rightOperand.x;
6.   temp.y = leftOperand.y + rightOperand.y;
7.   return temp;
8. }

(Line numbers are for reference only.)

Now, what does this do?  It overloads the + operator to use it with variables (objects) of class Object.  It performs addition, by adding the x and y data members of each operand together and stores the results into a new Object variable which it then returns.

So, later on in main() you could do this:

Object left;
Object right;
Object result = left + right;

Now, notice that the Object 'left' will go into leftOperand and 'right' will go into the rightOperand parameter. That's how it is with operators that are NOT methods of a class.

If you decided to overload the + operator for a class, then it would look something like this:

1. class Object
2. {
3.   public:
4.   Object operator + (const Object &rightOperand) const;  
5.   //More code here  
6. };
7. 
   
8. Object Object::operator + (const Object &rightOperand) const
9. {
10.   Object temp;
11.   temp.x = x + rightOperand.x;
12.   temp.y = y + rightOperand.y;
13.   return temp;
14. }

Now, note that we only need a parameter for the right operand.  Where's the left operand?  The left operand is the object used to call the + operator.

So, if we do this:

objThree = objOne + objTwo;

You can imagine the statement as looking like this:
objThree = objOne.+(objTwo);

objTwo is passed in as the rightOperand and the + operator is using objOne's x and y data members and adding them to rightOperand's corresponding members.

The result is then stored in Object temp, which is then returned.

(I'll probably continue this in another blog post.)

Joe