C++: Sorting with Bubblesort

Sorting with Bubblesort

In this lesson, we give a C++ implementation of the bubblesort algorithm. We described the bubblesort in the General Algorithms Lesson 1. Here, we provide an implementation with downloadable code.

Sorting is used nearly everywhere, as it provides us with a convenient way to efficiently access data. For this reason, dictionaries sort words alphabetically: imagine the nightmare of having to search for the definition of a word in a dictionary without alphabetic ordering. Likewise, if we are making loans, we would like some way to sort, say a list of credit scores, in order to find the best borrowers easily.

Our code for the bubblesort is a function template, which looks like this:

The algorithm works by continually moving the next largest entry to the back of the array until the array is fully sorted. Notice that the outer loop sets the length over which the inner loop moves entries. This is because everything greater than the outer loop index value is sorted at the end of the array: the entries bubble up the array to the end.

Since the sort routine is a function template, we can call it to sort all different types of arguments. Here, we show it sorting a list of integer credit scores. If we were writing a program to handle mortgages, this would be a useful operation. The code for making the call to bubblesort, looks like this:

Of course, sorting lists of scores like this is only useful when we have associated data with the scores. For example, we would want a name, phone number, etc. together with each credit score.

In a simpler example, high score tables in a game have a name associate with each score, and we would need to keep the score together with the name in order to have a usable list. The easiest way to accomplish this is to use a more complex data type, a subject we will cover in future lessons.