Bubble sort (C Plus Plus)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C++ | C# | Erlang | Java | Smalltalk

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

[edit] 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;
	}
}

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

<<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;
}
Download code
hijacker
hijacker
hijacker
hijacker