Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Selection Sort Insertion Sort STL sort() qsort() Performance Comparison

Algorithm Improvement through Performance Measurement: Part 2

Algorithm Improvement through Performance Measurement: Part 3

Sorting algorithms present some of the most interesting core challenges within computer science and engineering. A variety of sorting algorithms have been invented and studies over decades, with each algorithm providing a unique performance advantage over others, and some poor ones providing none at all. The web is a great resource for comparison and visualization (see [1], [2], [3], for example) and many algorithm text books are available.

In this multi-part series I explore these algorithms, but with a purpose of discovering how to optimize for the current generation of CPUs. In other words, we are going to explore some of the key aspects of today's CPUs. But there is nothing better than tuning real code to squeeze more performance and seeing how far it can go. This can be really addicting, but is one of the most enjoyable addictions of computer engineering.

So, let's dive right in and explore several of these sorting algorithms. A sorting algorithm takes an array of numbers as input and puts these numbers in order; for example, a[0] ≤ a[1] ≤ a[2] ≤ a[3] ≤ ≤ a[N] is the goal. To illustrate: Given a number sequence 5, 3, 7, 6, 4 a sorting algorithm would return 1, 3, 4, 5, 6, 7. In general, the items don't have to be numbers, but just need to be capable of being compared.

Selection Sort

Selection Sort is a classic approach that is described well in many textbooks on algorithms, as well as websites. Listing 1 provides two implementations: the first is the simplest to understand, which uses STL min_element() function to find the minimum, and the second implementation expands min_element().

// Listing1.cpp

#include <algorithm>

// Selection Sort algorithm using STL function min_element for clarity.
void selectionSortUsingSTL( float *a, unsigned long a_size )
{
	for ( unsigned long i = 0; i < a_size - 1; i++ )
	{
		float* minimum = std::min_element( a + i, a + a_size );	// find min within unsorted portion a[i] to end of a[]

		float swap = a[  i  ];
		a[  i  ]   = *minimum;		// this min value at the begining of currentl unsorted portion - at a[i]
		*minimum   = swap;
	}
}
// Selection Sort Algorithm adapted from Java example on Wikipedia
void selectionSortOriginalFromWikiInJava( float* a, unsigned long a_size )
{
	for ( unsigned long i = 0; i < a_size - 1; i++ )
	{
		unsigned long min = i;
		for ( unsigned long j = i + 1; j < a_size; j++ )	// Search for minimum and maximum value within current range
		{													// (within the unsorted portion)
			if ( a[ j ] < a[ min ] )
			{
				min = j;
			}
		}
		float swap = a[  i  ];
		a[  i  ]   = a[ min ];
		a[ min ]   = swap;
	}
}

The algorithm works by finding the minimum value in the entire array and moving that value to the beginning of the array. Then the next smallest value is searched for, not from the beginning of the array, but from the (beginning+1) array index to the end of the array. This minimum value is placed in array[ beginning+1 ] location. These steps continue, finding the minimum and reducing the search range by one element during each iteration of the loop, moving the minimum element to the front of the current search range. This process goes on until the search range is reduced to zero. The result is a sorted array with minimum value at the beginning of the array and maximum value at the end.

Another way to view Selection Sort, is that one sorted element is moved to the sorted portion of the array (at the beginning of the array) and the next iteration works on the unsorted portion of the array. As the algorithm progresses, the unsorted portion of the array gets progressively smaller, and the sorted portion gets progressively larger, until the sorted portion takes over the entire array.

Selection sort is an O(n²) algorithm, which can be seen from the number of comparisons in each iteration: (n-1) + (n-2) + (n-3) + + 3 + 2 + 1 = n(n-1)/2 comparisons.

Several nice animations of the Selection Sort and other sorting algorithms in action are provided on [2],[3] and [4]. Take a look at these, if only to muse about how many creative ways there are to sort. Selection Sort distinguishes itself by performing the least number of writes to the array of all sorting algorithms. It performs only n writes to the array. Few writes may be an important attribute in some environment, such as arrays stored in flash memory, where writes are very expensive. [4]

Note that our initial implementation for Selection Sort does not work properly for arrays size of zero. This is a common problem with corner cases and can be easily fixed with a single if statement at the front that checks the size to be one or more, and simply does nothing for smaller sizes. Sorting algorithms should work for arrays of size 0 and 1, and should do nothing in those cases, not even access any items within the array. The algorithm should not return an error in these two cases, since it's not wrong to have 0 or 1 elements in an array, there is just nothing to be done.

Selection Sort requires no additional storage and manipulates the array itself, swapping elements within the array -- this is "in-place behavior". Selection Sort always performs the same number of comparisons and writes to the array no matter what the data is, always doing n(n-1)/2 comparisons and 2(n-1) writes to the array. It is 2(n-1) writes because swapping takes two writes to the array -- the algorithms does two writes per loop. The (n-1) term comes from the fact that when the last element is reached no writes are necessary, since it's the only element left and is the maximum value within the entire array. In fact, the algorithm does not process the last element.

1 Selection Sort | 2 Insertion Sort | 3 STL sort() | 4 qsort() | 5 Performance Comparison Next Page

RELATED ARTICLES Logging In C++ : Part 2 OutSystems Updates Agile Platform SDK, .NET Controls Released for Communications Enabling Web Pages Welcome To the World of Cryptographic Voting recls 100% .NET		TOP 5 ARTICLES No Top Articles.