Compare sorting algorithms in C#, article 3 of 5

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 to 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 while looking 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. 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 will increase by a factor of roughly 22 = 4. There are several other sorting algorithms that require only about N * log(N) steps (Quicksort is one described 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 is 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.

   

 

What did you think of this article?




Trackbacks
  • No trackbacks exist for this post.
Comments
  • No comments exist for this post.
Leave a comment

Submitted comments are subject to moderation before being displayed.

 Name

 Email (will not be published)

 Website

Your comment is 0 characters limited to 3000 characters.