Bubble Sort - 2

COMP108 Lectures 2021-03-10

This time we will be looking at bubble sort in a linked list.

Linked List Pseudo Code

if head = NIL then
	Empty list and STOP
last = NIL
curr = head
while curr.next =/= last do
begin
	while curr.next =/= last do
	begin
		if curr.data > curr.next.data then
			swapnode(curr, curr.next)
		curr = curr.next
	end
	last = curr
	curr = head
end

Time Complexity Compared to Array

The time complexity is exactly the same as compared to using an array:

\[O(n^2)\]