Compare sorting algorithms in C#, part 3 of 5

Selectionsort

[sorting]

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 N2. 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 22 = 4.

[Book: Essential Algorithms]

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 Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, performance and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *