Bubble sort

The algorithm that we will implement in this chapter is well-known as bubble sort. The approach is very simple. Begin at the start of the cards and compare the first and the second card. If the first card is later in lexicographic order than the second one, then swap the two cards. Then repeat this for the card that is at the second place now, then the third, and so on. There is a card that is lexicographically the latest, say Wilson. When we get this card and start to compare it with the next one, we will always swap them; this way, Wilson's card will travel to the last place where it has to be after the sort. All we have to do is repeat this travelling from the start and do the occasional swapping of cards again, but this time only to the last but one element. This time, the second latest element will get to its place—say, Wilkinson will be right before Wilson. If we have n cards, and we repeat this n-1 times, all cards will get to their place.

In the following sections, we will create a Java project that implements this algorithm.