Selection Sort

COMP108 Lectures 2021-03-11

Method

1. Find minimum key from the input sequence.
2. Delete it from input sequence.
3. Append it to resulting sequence.
4. Repeat until nothing is left in the original sequence.

Example

34	10	64	51	32	21	To Swap
34	10	64	51	32	21	34, 10
10	34	64	51	32	21	34, 21
10	21	64	51	32	34	64, 32
10	21	32	51	64	34	51, 34
10	21	32	34	64	51	64, 51
10	21	32	34	51	64
10	21	32	34	51	64

Underlined is the current position, bold is the current smallest, and italic is sorted.

Pseudo-Code

This will give the following code when using while loops:

i = 1
while i <= n do
begin
	loc = i
	j = i + 1
	while j <= n do
	begin
		if A[j] < A[loc] then
			loc = j
		j++
	end
	swap A[i] and A[loc]
	i++
end

and the following for for loops:

for i = 1 to (n - 1) do
begin
	loc = i
	for j = (i + 1) to n do
		if A[j] < A[loc] then
		loc = j
	swap A[i] and A[loc]
end

Time Complexity

The nested for loops give the following table:

$i$	N° of > Comparisons
$1$	$n-1$
$2$	$n-2$
$\vdots$	$\vdots$
$n-1$	$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)\]

Using Linked Lists

Pseudo-Code

if head ==  NIL then 
	Empty list and STOP
curr = head
while curr.next =/= NIL do
begin
	min = curr
	node = curr.next
	while node =/= NIL do
	begin
		if node.data < min dataq then
			min = node
		Node = node.next
	end 
	swapnode(curr,min)
	curr = curr.next
end

Time Complexity

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

\[O(n^2)\]

Cases

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