W1352 Bubble Sort

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Reflection in a soap bubble

Background

• Read Bubble Sort (Wikipedia)
• View Bubble Sort 1- Algorithm (YouTube)
• View Bubble Sort Algorithm (YouTube)

Algorithm

The bubble sort algorithm is one of the simplest sorting algorithms. Here's an overview of how it works:

1. Iterate, with an index, over all array elements.
2. If the element on the left is greater than the element on the right, swap the elements.
3. Repeat steps 1 & 2 until there are no more swaps to complete.

Implementation

Although the algorithm is simple, the implementation takes a bit more thought. Here are some things to keep in mind:

• You'll need a variable to count the number of swaps you've made, in total and after each pass.
• Before a swap, you'll need to store one of the values in a temporary variable.
• You'll need a nested loop (the outer loop to continue until the array is sorted, and the inner loop to iterate over the array).
• Consider which type of loop is the best option. (Hint: you'll need the outer loop to always run at least once.)

Swaps

You can write the swap implementation within the nested loop or within a separate function. Note that if you choose to write a separate function, you'll want to pass the array into the function by reference to avoid making a copy of the array each time you need to make a swap. However, you choose to implement the swap, you'll need to store at least one of the values (the left or the right) outside the array. If you just swap without storing one of the values:

integers[index-1] = integers[index]
integers[index] = integers[index-1]

After the above code executes, the elements/integers at index and index - 1 would be equal to whatever the element/integer at index originally was. To solve this, you'll need to store either initial element into a temporary variable, swap the elements, then assign the remaining element to your stored value.

Example

Here's an example of a bubble sort for an array with 3 elements:

Array: [42, 82, 40] | Initial, Pass: 0 
Array: [42, 40, 82] | Swaps: 1, Pass: 1
Array: [40, 42, 82] | Swaps: 1, Pass: 2
Array: [40, 42, 82] | Swaps: 0, Pass: 3
Sorted in 3 iterations

Iteration #

1. The array was initially set to [42, 82, 40]. Remember that we compare each element with the one before it, so the algorithm compares 42 and 82 first. Since 42 < 82, there's nothing to swap. However, for the next two elements 82 and 40, 82 > 40, so the elements are swapped.
2. For the second iteration, the array starts at [42, 40, 82]. The first two elements, 42 and 40 are compared. Because 42 > 40, the first two elements are swapped. Then, the next two elements: 42 and 82 are compared. Because 42 < 82, they are already in order and no swaps need to be made.
3. For the third iteration, the array start at Array: [40, 42, 82]. The first two elements, 40 and 42 are compared. Because 40 < 42, no swaps need to be made. Then, the next two elements, 42 and 82 are compared. Because 42 < 82, no swaps need to be made. Because no swaps were made at all in this iteration, we know the array is sorted and we can exit the loop.

Performance

Although bubble sort is a simple algorithm to implement, it is rarely used for real-world applications because of its poor performance ( O(n^2) ) and is usually seen in an academic environment.

Quiz

1 Bubble sort is too slow and impractical for most problems.

	True
	False

2 Bubble sort is most practical if:

	The set of elements is very large
	Elements are already sorted in reverse order
	Doubles (floating point types) are used rather than integers
	Elements are in nearly sorted order

3 One advantage of bubble sort is that the ability to detect that the list is sorted is built into the algorithm.

	True
	False

4 An element that must move toward the end of the list can move quickly because it can take part in successive swaps.

	False
	True

5 An element that must move toward the beginning of the list can move faster than one step per pass.

	True
	False

6 Elements move toward the beginning of the list very quickly.

	True
	False

7 Consider the list: 5 1 4 2 8
After the first swap, the list will be:

	1 5 4 2 8
	1 4 2 5 8
	1 2 4 5 8
	1 4 5 2 8

8 Consider the list: 5 1 4 2 8
After the second swap, the list will be:

	1 2 4 5 8
	1 4 5 2 8
	1 4 2 5 8
	1 5 4 2 8

9 Consider the list: 5 1 4 2 8
After the third swap, the list will be:

	1 4 2 5 8
	1 4 5 2 8
	1 5 4 2 8
	1 2 4 5 8

10 Consider the list: 5 1 4 2 8
After the first pass, the list will be:

	1 4 2 5 8
	1 5 4 2 8
	1 4 5 2 8
	1 2 4 5 8

11 Consider the list: 5 1 4 2 8
After the second pass, the list will be:

	1 2 4 5 8
	1 4 2 5 8
	1 4 5 2 8
	1 5 4 2 8

12 Consider the list: 5 1 4 2 8
How many passes are required before the algorithm terminates?

	Four
	Three
	Two
	Five

Exercises

Exercises

•  M1352-10  Complete  Merlin Mission Manager  Mission M1352-10.