Bubble Sort - 1

COMP108 Lectures 2021-03-10

Method

1. Starting from the first element, swap adjacent items if they are not in ascending order.
2. When last item is reached, the last item is the largest.
3. Repeat the above steps for the remaining items to find the second largest item.
4. When there is no change the list is sorted.

Example

Each table is one iteration:

34	10	64	51	32	21
10	34	64	51	32	21
10	34	64	51	32	21
10	34	51	64	32	21
10	34	51	32	64	21
10	34	51	32	21	64

10

34

32

21

51

64

10

32

21

34

51

64

10

21

32

34

51

64

10

21

32

34

51

64

No change, list is sorted.

Bold are being considered, italic are sorted.

Pseudo-Code

for i = n downto 2 do
	for j = 1 to (i - 1) do
		if (A[j] > A[j + 1]) then
			swap A[j] & A[j+1]
	end
end

Swapping Variables

Generally you need a temporary variable, otherwise you will overwrite your original data:

tmp = x
x = y
y = tmp

You can also recover the data this way without using a temporary variable:

x += y
y = x - y
x -= y

This method is less readable and may overflow if you have two very large numbers.

Time Complexity

The nested for loops give the following table:

$i$	N° of > Comparisons
$n$	$n-1$
$n-1$	$n-2$
$\vdots$	$\vdots$
2	1

This gives the following simplified equation:

\[\frac{n^2-n}{2}\]

We keep the highest power which gives the following big-O notation:

\[O(n^2)\]

Cases

• In the best case bubble sort takes 0 swaps.
• In the worst case, bubble sort takes $O(n^2)$ times.