Algorithm Improvement through Performance Measurement: Part 1

Insertion Sort keeps performing swaps until it finds the proper place within the sorted portion of the array for the new element. These swaps perform two writes to the array within the inner loop, resulting in O( n2 ) number of writes. The exact number of writes in the worst case is 2*(1, 2, 3, … (n-1)) = 2n(n-1)/2 = n(n-1). In the best case, the number of writes is zero -- the array is already sorted and the inner for loop fails "a[j] < a[j-1]" comparison and never executes any swaps. This is a huge range for the number of writes — zero to n(n-1). For example, for 1000 element array the number of writes is between zero and 999,000, depending on the input data values.

Insertion Sort distinguishes itself by being adaptive — it adapts to the input data. Insertion Sort does not scan the entire sorted portion of the array, instead it stops when it finds the proper location for the insertion. Insertion Sort performs fewer comparisons in the best case than in the worst case: (n-1) comparisons in the best case, and n(n+1)/2 - 1 comparisons in the worst case.

STL sort()

One of the main accomplishments of STL sort() is being generic, thus working with different types of containers, such as native arrays, vector, deque. However, STL sort() works only on containers that can be randomly accessed, which excludes all other STL containers. The reason is most likely that containers with random access can be sorted in O ( n log n ) time — the best performance possible when using comparisons. These containers can hold a wide variety of types, such as char, short, int, long, double, float, string, as well as custom classes (as long as certain expected rules are followed and particular operations are implemented for these classes). Listing Three shows several examples of usage, using built-in arrays as well as STL containers such as vector, and deque.

Listing Three

// STLSortExamples.cpp
// Examples of STL sort() usage on various containers.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

// STL sort() works only on random access containers: vector and deque.
void STLsortExamples()
{
	cout << endl << "STL sort() Examples" << endl;

	const unsigned long array_size = 10;
	float fa[ 10 ] = { 5, 4, 7, 1, 0, 9, 3, 2, 6, 8 };
	vector< float > fvec(  fa, fa + array_size );
	deque<  float > fdq(   fa, fa + array_size );

	sort( fa,           fa + array_size );
	sort( fvec.begin(), fvec.end()      );
	sort(  fdq.begin(),  fdq.end()      );

	// Print all sorted containers

	cout << "Array:  ";
	for( unsigned long i = 0; i < array_size; i++ )
		cout << fa[ i ] << " ";
	cout << endl;

	cout << "Vector: ";
	vector< float >::const_iterator v_iter = fvec.begin();
	for( ; v_iter != fvec.end(); ++v_iter )
		cout << *v_iter << " ";
	cout << endl;

	cout << "Deque:  ";
	deque< float >::const_iterator dq_iter = fdq.begin();
	for( ; dq_iter != fdq.end(); ++dq_iter )
		cout << *dq_iter << " ";
	cout << endl;

}

STL sort() uses three different sorting algorithms within its structure — qsort, Heap Sort, and Insertion Sort at the lowest level. For now, STL sort() will be treated as a black box for comparison, and will be examined in detail in future articles.

qsort()

This sorting routine is part of the standard C language run-time library. Listing Four shows an example of its usage. The routine is fairly generic and expects as input a pointer to an array, number of elements in that array, size of each element in bytes, and a pointer to a comparison function. The pointer to an array is void, making it fairly generic. A thread-friendly version is also available qsort_s(), which takes an additional input of context pointer.

Listing Four

// qsortExamples.cpp
// Examples of qsort() function usage, which is in the C runtime library.

#include <stdlib.h>
#include <search.h>
#include <iostream>
#include <exception>

using namespace std;

// Comparison function used by qsort
// returns <0 if elem1 <  elem2
// returns  0 if elem1 == elem2
// returns >0 if elem1 >  elem2
int qsort_fCompare( const void * elem1, const void * elem2 )
{
	float f_elem1 = *( reinterpret_cast< const float * > ( elem1 ));
	float f_elem2 = *( reinterpret_cast< const float * > ( elem2 ));

	if ( f_elem1 <  f_elem2 )	return -1;
	if ( f_elem1 >  f_elem2 )	return  1;
	if ( f_elem1 == f_elem2 )	return  0;
	throw;									// Concerned that NaN's may cause trouble, but don't know how to handle it.
}

void qsortExamples()
{
	cout << endl << "qsort() Examples" << endl;

	const unsigned long array_size = 10;
	float fa[ 10 ] = { 5, 4, 7, 1, 0, 9, 3, 2, 6, 8 };

	try {
		qsort( (void *)fa, array_size, sizeof( float ), qsort_fCompare );
	}
	catch(...) {
		cout << "Error in qsort_fCompare()" << endl;
	}

	cout << "Array: ";
	for( unsigned long i = 0; i < array_size; i++ )
		cout << fa[ i ] << " ";
	cout << endl;
}