Channels ▼
RSS

Parallel

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;
}


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video