Insertion Sort

COMP108 Lectures 2021-03-11

Method

1. Look up the elements one by one.
2. Build up sorted list by inserting the element in the correct location.

Example

34	10	64	51	32	21	Number shifted to right
34	10	64	51	32	21
10	34	64	51	32	21	34
10	34	64	51	32	21
10	34	51	64	32	21	64
10	32	34	51	64	21	34, 51, 64
10	21	32	34	51	64	32, 34, 51, 64

Bold is the number being considered and italic is the sorted list.

Pseudo-Code

for i = 2 to n do
begin
	key = A[i]
	loc = 1
	while loc < i AND A[loc] < key do
		loc++
	for j = i downto (loc + 1) do
		A[j] = A[j - 1]
	A[loc] = key
end

Time Complexity

The nested for loops give the following table:

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

From this we get the following big-O notation:

\[O(n^2)\]

Using Linked Lists

Pseudo-Code

head = NIL
while thereIsNewNumber do
begin
	input number * create node
	node.data = num
	if head == NIL OR head.data > node.data then
	begin
		node.next = head
		head = node
	end
	else begin
		curr = head
		while curr.next =/= NIL AND curr.next <= node.data do
			curr = curr.next
		node.next = curr.next
		curr.next = node
	end
end

Time Complexity

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

\[O(n^2)\]