Bubble sort (C Plus Plus)

From LiteratePrograms

Other implementations: C | CLIPS | C++ | C# | Eiffel | Erlang | Io | Java | Lisp | Smalltalk

An implementation of bubble sort in c++.

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

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 bidirectional 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.

Bubble sort

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

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