Printable Version of Topic

Posted by: KYA 18 Jul, 2008 - 03:48 PM

Selection Sorting

Selection sorting is an algorithm for sorting lists of data and is specifically an in place comparison sort. Generally it is inefficient in large lists and is not faster then an insertion sort on such a list. However, it outperforms (usually) bubble sorting on a relatively small list. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations. The steps are as follows:

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list (starting at the second position)


We again essentially divide the list into two halves (this comes up a lot doesn't it?) Selection sort can also be used on list structures that make adding and removing efficient, such as a linked list. In this case it's more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far (i.e. insertion sort).

Let's run through some example code. In this mini program we will initialize an array of 10 elements with random integers ranging between 1 and 100. We will then display the list for debugging purposes and then display it again after the sort has been performed:

srand(time(0));
	int arrayOne[10];
	for (int i = 0; i < 10; i++)
	{
		arrayOne[i] = rand() % 100 + 1; // generate random values to sort
	}
	//display values prior to sorting
	for (int i = 0; i < 10; i++)
	{
		cout << " " << arrayOne[i];
	}

Don't forget to include iostream and time.h if you wish to seed as above. The prototype for out SelectionSort() function is as follows:

void SelectionSort (int[], int);

We pass in the array and the length of that array. Without the length we would be able to use this type of sorting algorithm. We have now successfully set ourselves up to sort this list using a selection sort. Here is the algorithm:

void SelectionSort(int A[], int length)
{
    int i, j, min, minat;
	for(i = 0; i<(length-1); i++)
	{
		minat = i;
		min = A[i];

      for(j = i+1;j < length; j++) //select the min of the rest of array
	  {
		  if(min > A[j])   //ascending order for descending reverse
		  {
			  minat = j;  //the position of the min element 
			  min = A[j];
		  }
	  }
	  int temp = A[i];
	  A[i] = A[minat];  //swap 
	  A[minat]=temp;	
	}
}

The use of temporary values is crucial here, more so then other algorithms since we essentially have multiple "placeholders" so we can "select" and "sort". These sorts are so aptly named. Here is the entire code for you to experiment with:

#include <iostream>
#include <time.h>
using namespace std;

void SelectionSort (int[], int);

int main()
{
	srand(time(0));
	int arrayOne[10];
	for (int i = 0; i < 10; i++)
	{
		arrayOne[i] = rand() % 100 + 1; // generate random values to sort
	}
	//display values prior to sorting
	for (int i = 0; i < 10; i++)
	{
		cout << " " << arrayOne[i];
	}
	SelectionSort(arrayOne, 10);
	cout << endl;
	//display values after sorting
	for (int i = 0; i < 10; i++)
	{
		cout << " " << arrayOne[i];
	}
	cout << endl;
	return 0;
}

void SelectionSort(int A[], int length)
{
    int i, j, min, minat;
	for(i = 0; i<(length-1); i++)
	{
		minat = i;
		min = A[i];

      for(j = i+1;j < length; j++) //select the min of the rest of array
	  {
		  if(min > A[j])   //ascending order for descending reverse
		  {
			  minat = j;  //the position of the min element 
			  min = A[j];
		  }
	  }
	  int temp = A[i];
	  A[i] = A[minat];  //swap 
	  A[minat]=temp;	
	}
}

Efficiency

Average case: O(n^2), this is compared to insertion, bubble, or gnome sorts among similar sized lists

Worst case: O(n^2) Large lists where selection sort is vastly outperformed by other divide and conquer sorts such as the merge sort

Best case: O(n) (the list would have to be almost in order) , lists of 10-20 elements allow selection sort to operate very fast/efficient when compared to other algorithms.

It cannot be overstated that the programmer must chooser what "tools" to use for the job based on the parameters and needs of the project. Selection sort is of but many sorting methods that can allows you to get the job done. It can be done recursively or iteratively as in this tutorial. Happy coding!

Posted by: cmaster 24 Nov, 2008 - 12:29 PM

Take a look at http://simpleprogrammingtutorials.com/tutorials/sorts/selection-sort.php for illustrations and Java implementation.