Bubble sort (C Plus Plus)

From LiteratePrograms

An implementation of bubble sort in c++.

<<bubblesort.cpp>>=
#include<iostream>
#include<algorithm>	// std::swap()
#include<vector>
bubble_sort
test_driver

[edit]

Overview

Bubble sort works by repeatedly iterating through a container, swapping adjacent items when the first item is larger than the second. When no swapping is done, the container is sorted.

This implementation uses the template-functionality in C++, allowing it to be used generically with different containers and data types. The IT template parameter can be any random-access iterator type (including raw pointers). A complete generic implementation would also include a comparison function parameter, so that the user could choose the sort order.

[edit]

Bubble sort

<<bubble_sort>>=
template<typename IT> 
void bubble_sort(IT begin, IT end)
{
	bool done(false);
	for(IT n=end-1; n>=begin && !done; --n) {
		done=true;
		for(IT it=begin; it!=n; ++it) {
			if(*it>*(it+1)) {
				std::swap(*it, *(it+1));
				done=false;
			}
		}
	}
}

[edit]

Testing

This test program will first run bubble_sort() on a vector of strings, and then do the same on an array of integers.
Note that sorting of strings (and other classes) implies calling copy-constructor and destructor many times, which might lead to bad performance.

[ A good implementation of 'swap' will eliminate the usual dynamic heap memory overheads of copy-constructors and destructors, by simply swaping the pointers to the heap memory. I expect most standard library implementations of std::string::swap are implemented this way. For vectors of user-defined classes, the user will need to provide their own overloaded implementation of swap, or else incur overhead of dynamic memory allocation and deallocation ]

<<test_driver>>=
template<typename T> void print(const T &data)
{
	std::cout<<" "<<data;
}

int main()
{
	std::vector<std::string> v(10);
	v[0]="Paris";
	v[1]="London";
	v[2]="Stockholm";
	v[3]="Berlin";
	v[4]="Oslo";
	v[5]="Rome";
	v[6]="Madrid";
	v[7]="Tallinn";
	v[8]="Amsterdam";
	v[9]="Dublin";

	std::cout<<"v before bubble_sort(): ";
	std::for_each(v.begin(), v.end(), print<std::string>);
	std::cout<<'\n';

	bubble_sort(v.begin(), v.end());

	std::cout<<"v after bubble_sort(): ";
	std::for_each(v.begin(), v.end(), print<std::string>);
	std::cout<<'\n';

	int a[]={3,8,0,6,7,4,2,1,9,3,1,8,3,9,2,0,9};
	int *a_end=a+sizeof a/sizeof(int);

	std::cout<<"a before bubble_sort(): ";
	std::for_each(a, a_end, print<int>);
	std::cout<<'\n';

	bubble_sort(a, a_end);
	
	std::cout<<"a after bubble_sort(): ";
	std::for_each(a, a_end, print<int>);
	std::cout<<'\n';

	return 0;
}