Topic : Selection Sort
Author : Ilia Yordanov
Page : 1

    
The Selection Sort Algorithm


I.Legal

This tutorial is written by Ilia Yordanov, and can't be re-published without a written permission from the author!
If you want to contact me, mail me at: loobian@cpp-home.com

II.Assuming...

I am not assuming that you know C++, even not very good...! Generally, the algorithm that I will explain can be implemented and ran in any language. Anyway, all the code examples are in C++...


III.About the author...

My name is Ilia Yordanov. Me and Deyan Vitanov are the owners of www.cpp-home.com!
Contact Information:
E-mail: loobian@cpp-home.com
ICQ: 52958267
URL: http://www.cpp-home.com

If you have any suggestions, recommendations and so on, on how to improve this tutorial, please email me!

IV.Introduction

This is one of the simpliest algorithms for sorting... it is not recommended to use it with many numbers, as it will take long probably... it is good for sorting about 20-30 numbers approximately...


Selection Sort


This algorithm is very simple in fact! Here is how it works...

Imagine that you have these numbers:
10 32 4 43 12 65
which you want to sort...

This algorithm first finds the lowest number and puts it on first place. In this example, the lowest number is 4. So, after fining it and putting it on first place, the numbers should look like this:
4 32 10 43 12 65

Notice that on the place where the "4" was, it's now the first number...

Now, continuing in this order, the algorithm should find the lowest number from these:
32 10 43 12 65 /the line still has the "4", but it is already sorted so I won't write it here.../
We exclude "4" as we already found that it is the lowest in the previous case.
So, in the new search, the lowest number is 10, so our line should look like this:
10 32 43 12 65

After that you should find the lowest number from these:
32 43 12 65
It is- 12, so the new look is:
12 43 32 65

The next step is to find the lowest number from these:
43 32 65
It is- 32, so the new look is:
32 43 65

Now, we have only two numbers left, to compare- 43 and 65. We see that 43 is lower than 65, so it keeps this order.
So, after all, we have this:
4 10 12 32 43 65


Here is a sample C++ code that makes this sorting. The code is written by me. It uses a function that takes parameters, so you can implement it in other programs, too...


#include <iostream.h>

//Selection Sort function
//Takes two parameters:
//int *array- the array with the numbers to be sorted
//int size- the size of the array
void selsort(int *array,int size)
{
int min;
int b;

//This loop goes through the whole array
for(int a=0;a<size-1;a++)
{
  b=a;
  min=array[b]; //Get the current value

  //...and check if any of the rest numbers is lower
  for(int j=a+1;j<size;j++)
  {
   if(array[j]<min)
   {
    b=j; min=array[b]; //...and if yes, then get it
   }
  }

  //Switch the values...
  array[b]=array[a];
  array[a]=min;

}
}

//Main program function
void main()
{
beginning:
const int maxsize=100;
int count;
char answer;

cout << "How many numbers you want to sort?: ";
cin>> count;
if(count>maxsize)
{
  cout<<"Too many..."<<endl;
  cout<<"Your limit is: "<<maxsize<<endl;
  cout<<"Want to try again? (y/n): ";
  cin>>answer;
  if(answer=='y')
   goto beginning;
  else
   cout<<endl<<"Bye bye...!"<<endl;
}
else
{
  int *numbers;
  numbers=new int[count];

  for(int y=0;y<count;y++)
  {
   cout<<"Enter number #"<<y+1<<" : ";
   cin>>numbers[y];
  }
  
  selsort(numbers,count); //Sort the numbers...

  cout<<endl<<endl;

  //Print the results...
  cout<<"Result: "<<endl;
   for(int h=0;h<count;h++)
   cout << numbers[h]<<" ";

  cout<<endl;

  //Free the memory...
  delete [] numbers;
}
}



Please, let me know if you have any recommendations... I can be reached at loobian@cpp-home.com


Copyright 2001. All rights reserved!

Page : 1