Title: Compare sorting algorithms in C#, part 3 of 5 (Selectionsort)

Selectionsort

Selectionsort is a very simple algorithm. First you search the list for the smallest item. Then you swap that item with the item at the top of the list. Next you find the second smallest item and swap it with the second item in the list. You continue finding the next smallest item and swapping it into its final position in the list until you have swapped all of the items into their final positions.

The following code shows the example program's implementation of Selectionsort.

// Selectionsort. private void Selectionsort(int[] values) { for (int i = 0; i < NumItems - 1; i++) { int best_value = values[i]; int best_j = i; for (int j = i + 1; j < NumItems; j++) { if (values[j] < best_value) { best_value = values[j]; best_j = j; } } values[best_j] = values[i]; values[i] = best_value; } }

If the list contains N items, then when you look for the K-th smallest item you must examine each of the N - K items that you have not yet placed in their final positions. That means the total number of steps the algorithm needs is:

N + (N - 1) + (N - 2) + ... + 1 = N * (N + 1) / 2

This function is on the order of N². That means if you increase the number of items in the list by a factor of 2, the run time of the algorithm increases by a factor of roughly 2² = 4.

Several other sorting algorithms require only about N * log(N) steps (Quicksort is one that I'll describe later), so Selectionsort is not a very fast algorithm for large lists.

Selectionsort is fine for small lists, however. It is very simple so it's easy to program, debug, and maintain over time. In fact it is so simple that it is actually faster than the more complicated algorithms if the list you are sorting is very small. If your list contains only a dozen or so items, Selectionsort is often competitive with other algorithms.

Download the example to experiment with it and to see additional details.