Selection Sort

• simple O(n²) sorting algorithm
• the method requires O(N2) comparisons and so it should only be used on small files.
• There is an important exception to this rule. When sorting files with large records and small keys, the cost of exchanging records controls the running time.
• In such cases, selection sort requires O(N) time since the number of exchanges is at most N.
• The selection sort works by selecting the smallest unsorted item remaining in the list, and then swapping it with the item in the next position to be filled. The selection sort has a complexity of O(n2).

Pros: Simple and easy to implement.

Cons: Inefficient for large lists, so similar to the more efficient insertion sort that the insertion sort should be used in its place.

Steps in Selection Sort:

1. Select the largest element of an array.

2. Swap the last element with the largest element.

3. Now do the same thing again, for an array that has one less element.

4. Keep doing this, until you are down to an array of 2 elements.

Example:

Repeatedly find the next largest (or smallest) element in the array and move it to its final position in the sorted array.

Empirical Analysis

Selection Sort Efficiency

The selection sort is the unwanted stepchild of the n2 sorts. It yields a 60% performance improvement over the bubble sort, but the insertion sort is over twice as fast as the bubble sort and is just as easy to implement as the selection sort. In short, there really isn't any reason to use the selection sort - use the insertion sort instead.

If you really want to use the selection sort for some reason, try to avoid sorting lists of more than a 1000 items with it or repetitively sorting lists of more than a couple hundred items.

Source Code

Below is the basic selection sort algorithm.

void selectionSort(int numbers[], int array_size)

{

int i, j;

int min, temp;

for (i = 0; i <>

{

min = i;

for (j = i+1; j <>

{

if (numbers[j] <>

min = j;

}

temp = numbers[i];

numbers[i] = numbers[min];

numbers[min] = temp;

}

}