Bubble Sort

Notation

$\Omega (n)$

$\theta (n^2)$

$O(n^2)$

Step by Step

1. Compare the first value with the second

2. If the first is larger then swap

3. for each iteration the last element is sorted so ignore it

Pseudocode

a = list
n = size of list

bool swap;

for (i = 0; i < n; i++)
	swap = false;

	for (j = 0; j < n; j++)
		if (a[j] > a[j + 1])
			swap(a[j], a[j + 1]);
			swap = True;
	
	if (!swap)
		break;
 

Video