Title: Compare sorting algorithms in C#, part 2 of 5 (Bubblesort)

Bubblesort

Bubblesort is a specialized algorithm designed for sorting items that are already mostly in sorted order. If only one or two items in your list are out of order, Bubblesort is very fast. If the items in your list are initially arranged randomly, Bubblesort is extremely slow. For this reason you should be careful when you use Bubblesort.

The idea behind the algorithm is to scan through the list looking for two adjacent items that are out of order. When you find two such items, you swap them and continue down the list. You repeat this process until all of the items are in order.

Figure 1 shows a small list where the item 1 is out of order. During the first pass through the list, the algorithm finds that the items with values 4 and 1 are out of order so it swaps them. During the next pass it finds that the items with values 3 and 1 are out of order so it swaps them. During the third pass it swaps the items with values 2 and 1, and the list is sorted. The way in which the item with value 1 seems to bubble towards the top of the list is what gives Bubblesort its name.

You can improve the algorithm if you alternate upward and downward passes through the list. During downward passes an item that is too far down in the list, like the item with value 1 in the previous example, can move up only one position. In contrast, an item that is too far up in the list might move many positions. If you add upward passes through the list, items can quickly move many positions both up and down through the list.

If you study the algorithm for a while, you'll see that at least one new item reaches its final position during each pass through the list. If the items in your list begin mostly in sorted order, the algorithm will need only one or two passes through the list to finish the ordering. If you have a list of 1,000 items with only one out of order, the algorithm would require only 2 passes taking 2,000 steps to sort the list.

If the items begin arranged randomly, the algorithm may need one pass per item in the list. The algorithm would need up to 1 million steps to arrange a list of 1,000 items.

The following code shows the C# code for this Bubblesort algorithm.

// Bubblesort with: // - Alternating upward and downward passes // - Holding bubbled item in a temporary variable // - Updating min and max to narrow the search range private void Bubblesort(int[] values) { int min = 0; int max = NumItems - 1; while (min < max) { // Bubble up. int last_swap = min - 1; // For i = min + 1 To max int i = min + 1; while (i <= max) { // Find a bubble. if (values[i - 1] > values[i]) { // See where to drop the bubble. int tmp = values[i - 1]; int j = i; do { values[j - 1] = values[j]; j++; if (j > max) break; } while (values[j] < tmp); values[j - 1] = tmp; last_swap = j - 1; i = j + 1; } else { i++; } } // Update max. max = last_swap - 1; // Bubble down. last_swap = max + 1; // For i = max - 1 To min Step -1 i = max - 1; while (i >= min) { // Find a bubble. if (values[i + 1] < values[i]) { // See where to drop the bubble. int tmp = values[i + 1]; int j = i; do { values[j + 1] = values[j]; j--; if (j < min) break; } while (values[j] > tmp); values[j + 1] = tmp; last_swap = j + 1; i = j - 1; } else { i--; } } // Update min. min = last_swap + 1; } }

Bubblesort works quite well when the list of items has very few items out of order. Array.Sort is so fast, however, that it beats Bubblesort unless the list holds only a couple of items that are out of order.

Bubblesort is also quite fast for very small lists (3 or 4 items) and it often beats Array.Sort in that case. However in that situation the total time for sorting is so small that it may be better to just use Array.Sort so you don't have to worry about bugs in your Bubblesort code.

Download the example to experiment with it and to see additional details.