Algorithms and Complexity Analysis

Lecture Notes

UNIT 4: SORTING ALGORITHMS I

Dr Fatimah Adamu-Fika
Department of Cyber Security
Faculty of Computing
Air Force Institute of Technology
Kaduna, Nigeria

April 2023
© Since 2020. All rights reserved. No part of this document may be reproduced or
transmitted in any form or by any means, electronic or mechanical, including
photocopy, recording, or any information storage and retrieval system, without
permission in writing from the author.
CONTENT

Overview ................................................................................................................................ 1

Concepts and Terminology ............................................................................................. 1

Sorting Problem ................................................................................................................. 1

Selection Sort ......................................................................................................................... 2

Algorithm: How Selection Sort Works .............................................................................. 2

Correctness Proof .............................................................................................................. 5

Formal Proof using Loop Invariants .............................................................................. 5

Efficiency Analysis ............................................................................................................. 7

When to use Selection Sort............................................................................................... 8

Bubble Sort ............................................................................................................................. 8

Algorithm: How Bubble Sort Works .................................................................................. 8

Correctness Proof ............................................................................................................ 11

Formal Proof using Loop Invariants ............................................................................ 11

Efficiency Analysis ........................................................................................................... 12

When to use Bubble Sort ................................................................................................ 14

Insertion Sort......................................................................................................................... 14

Correctness Proof ............................................................................................................ 18

Formal Proof using Loop Invariants ............................................................................ 18

Efficiency Analysis ........................................................................................................... 19

When to use Insertion Sort .............................................................................................. 20

Summary .............................................................................................................................. 21

Unit Goals ............................................................................................................................. 21

Exercises ............................................................................................................................... 22

Bibliography and Resources .............................................................................................. 24

Textbooks.......................................................................................................................... 24

Websites ........................................................................................................................... 24

Algorithms and Unit 4 Dr F. Adamu-Fika

ii Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
OVERVIEW

Sorting is the permuting (rearranging or reordering) of a sequence of objects

(elements, also items) to put them in some sort of logical order, i.e., rearranging the
elements of an input object (usually an array) according to a well-defined ordering
rule. Sorting is a fundamental operation in computing because many programs use it
as an intermediate step.

There are two categories of sorting based on whether the objects that need to be
sorted can fit into the available memory all at once or not.

• Internal sorting: When all elements that need to be sorted are placed in
memory at the same time, then the sorting done is internal.
• External sorting: When all elements that need to be sorted cannot fit in memory
all at once, then the sorting is done in phases. The sorted data are put back
together. Such sorting is called external sorting. External sorting is used for a
massive amount of data, and some sort of external storage is used to hold the
large data and the sorted output files.

Concepts and Terminology

1. A sorting algorithm is an algorithm that places elements of a list into order, i.e.,
sorts the elements of a list. The most commonly used orders are numerical order
and lexicographical order, both can either be non-decreasing or non-
increasing.

2. A sorting problem is a computational problem that is solved by a sorting

algorithm.

3. An in-place sorting algorithm is a sorting algorithm that does not require an

auxiliary data structure when sorting. It, however, might require a small amount
of additional storage space for auxiliary variables. It requires no more than a
constant amount of additional memory beyond the input itself as it sorts the
elements of a list. An in-place algorithm sorts the list by swapping or replacing
the elements. An algorithm which does not sort in place is sometimes called a
not-in-place or out-of-place algorithm.

4. A stable sorting algorithm maintains the relative order of elements with equal
values. This means equal elements appear in the same order in the sorted
output as they do in the input.

Sorting Problem
The sorting problem requires the sorting of the items of a given list. Such a list can be
a list of numbers, character strings and records, similar to those maintained by AFIT
about you. In the case of sorting records, we need to choose a piece of information
to guide the sorting. For example, we chose to sort your last semester's results by your
matriculation number. Such chosen piece of information is called a key. Often, we
talk of sorting a list of keys even when we deal with items that are not records. The
sorted list must be in monotonic order, i.e., each element must not be smaller or larger
than the previous element as required by the ordering criterium. The sorted list must
retain all the original elements, i.e., the sorted list must be a permutation of the given
unsorted elements. In your semester results, the keys (your matriculation numbers) are

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 1
© Since 2020 Elementary Algorithms Lecture Notes
sorted so that each key is less than or equal to its successor. When we want to sort a
list in such non-decreasing order, we formally define our sorting problem as follows.

Input: A list of n items <a1, a2, a3, …, an>.

Output: A permutation (i.e., a reordering) <a´1, a´2, a´3, …, a´n> of the input
sequence such that a´1 ≤ a´2 ≤ a´3 ≤ … ≤ a´n.

The sorting problem is a problem of interest in computing for several reasons. We may
need to sort a list because it might be a required output for a task such as ranking
internet search results. Sorting can make it easier to answer questions about a list or to
retrieve information from a list, for example, sorted students’ records. Sorting can also
be an intermediary step in solving larger problems, for example, some greedy
algorithms require a sorted input.

Unless otherwise stated, the sorting algorithms we will be looking at will be solving the
defined sorting problem. We will be studying six common sorting algorithms:

1. The three elementary sorting algorithms: Selection sort; Bubble sort and
Insertion sort
2. Merge sort
3. Quicksort
4. Heapsort

This unit will focus on the three elementary sorting algorithms while the other three will
be discussed in the next unit.

SELECTION SORT

Selection sort uses a brute-force approach to sort a given list. Selection sort is a sorting
algorithm that selects the smallest element from an unsorted list in each iteration and
places that element at the beginning of the unsorted sublist.

Algorithm: How Selection Sort Works

Let’s explain selection sort with an instance of our sorting problem: [5, 3, 2, 4, 1].

At the start of our sort, before we begin our iterations our list looks like this:

5 3 2 4 1

The current element at index min is highlighted in red. The element at the index that
is being compared with the element at min is shown with a red border. Elements that
are in their final positions are shown in green.

Note: min stores the index of the smallest element and NOT its value!

1. Set the index of the first element of the list as a variable that holds the smallest
value, let’s call this variable min.
mi n
5 3 2 4 1
0

Algorithms and Unit 4 Dr F. Adamu-Fika

2 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
2. Compare the element at min with the second element. If the second element
is smaller than the element at min, it resets min and sets it to the index of the
second element, otherwise, it does nothing.

<

mi n
5 3 2 4 1
0

mi n
5 3 2 4 1
1
reset mi n

This process goes on until the last element at index n – 1.

< <

mi n mi n
5 3 2 4 1 5 3 2 4 1
1 2

mi n mi n
5 3 2 4 1 5 3 2 4 1
2 2
reset mi n mi n is unchanged

<

mi n
5 3 2 4 1
2

mi n
5 3 2 4 1
4
reset mi n

3. At the end of each pass (iteration), the element at index min is placed at the
front of the remaining unsorted elements. And the element that was previously
there will be placed at index min.

swap

mi n
5 3 2 4 1
4

1 3 2 4 5

Remember min stores the index of the smallest element and NOT its value!

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 3
© Since 2020 Elementary Algorithms Lecture Notes
4. For each pass, scanning (indexing) starts from the first unsorted element. Steps
1 through 3 are repeated until all the elements are placed in their correct
positions.

After the 1st pass (before i increases when i = 0), the list: [1, 2, 3, 4, 5]

1 3 2 4 5

After the 2nd pass (before i increases when i = 1), the list: [1, 2, 3, 4, 5]

1 2 3 4 5

After the 3rd pass (before i increases when i = 2) , the list: [1, 2, 3, 4, 5]

1 2 3 4 5

After the (n–1)th pass (before i increases when i = n – 2), the list: [1, 2, 3, 4, 5]

1 2 3 4 5

After the nth pass (before i increases when i = n – 1), the list: [1, 2, 3, 4, 5]

1 2 3 4 5

Generally, the algorithm maintains two sublists in the original list, (1) a sublist list
of elements in their final positions and (2) a sublist of the remaining elements in
the list waiting to be sorted. On each pass of the algorithm, it searches for the
smallest element in the unsorted sublist and places it at the front of that sublist.
For simplicity and explanation purposes, we assume the list is an array, with the
first index at 0 and the last index at n – 1. Let i be the current pass, the list scans
through the remaining n – i unsorted elements, and the smallest element A[min]
in the subarray A[i … n – 1] will be swapped with A[i] (i.e., the first element in
that subarray).

A[0] ≤ A[1] ≤ A[i – 1] | A[i], … , A[min], … , A[n – 1]

Elements in their The last n – i unsorted
final positions elements

From the example above we can see that after n – 1 passes the array will be fully
sorted. The last pass (nth pass) is redundant, as the element at index n – 1 will be at its
final position when every other element preceding it is put in its right position. This pass

Algorithms and Unit 4 Dr F. Adamu-Fika

4 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
if it happens will compare A[n – 1] with itself because i = n – 1and the subarray A[i …
n – 1] will only contain the elements A[n – 1]. Hence, our selection sort algorithm that
follows, indexes i up to n – 2.

Algorithm SelectionSort(A)
Input: an array, A[0 … n – 1], with n order-able items.
Output: The array, A, sorted in non-decreasing order.
START
1. for( i = 0; i < n - 1; i++ ) //for i = 0 to n – 2
2. min = i
3. for( j = i + 1; j < n; j++ ) //for j = i + 1 to n – 1
4. if( A[j] < A[min]
5. min = j
6. Swap( A, i, min ) //swap A[min] with A[i]
7. return A
END

Correctness Proof
Let A´ denote the output of SelectionSort(A).

To prove that SelectionSort is correct, we need to prove that it terminates and that:

A´[0] ≤ A´[1] ≤ A´[2] ≤ … ≤ A´[n – 1]

where n = A.length.

Formal Proof using Loop Invariants

Because there are two loops in our algorithm, we will prove the inequality above in
two parts:

a. We precisely state a loop invariant for the inner for loop in lines 3—5 and prove
that this loop invariant holds.

b. Using the termination condition of the loop invariant proved in part (a), we will
precisely state a loop invariant for the outer for loop in lines 1—6 that will allow
us to prove the inequality.

Theorem:
A´ consists of the elements in A but is sorted in non-decreasing order.

Proof:
Inner Loop invariant (for loop of lines 3–5)
At the start of each iteration of the inner for loop, A[min] is smaller than or equal
to the elements in the subarray A[i … j – 1], i.e., A[min] is the smallest item in
that subarray.

Initialisation: Initially, j = i + 1, and so the subarray A[i … j – 1] contains only the

element, A[i], which is trivially the smallest element is the subarray A[i … j – 1].
Since line 2 of the algorithm set min = i, we have min indexing the smallest
element (the only element) in the subarray A[i … j – 1]. Hence the loop invariant
holds.

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 5
© Since 2020 Elementary Algorithms Lecture Notes
Maintenance: At the start of each iteration, we assume that A[min] indexes the
smallest element in the subarray A[i … j – 1]. In each iteration, we compare A[j]
with A[min] and make min hold the index of the smallest amongst the two.
Because, during each iteration we have two cases: either (1) A[j] < A[min] or
A[j] ≥ A[min]. In case (2) the if statement on line 4 is not true, so nothing happens
(line 5 does not execute). However, in case (1), line 5 reassigns min to index
location j since A[j] is the smaller element. So, if min indexes an element less
than or equal to the elements in the subarray A[i … j – 1] and A[j] < A[min], then
it must be the case that A[j] is less than or equal to the elements in subarray A[i
… j – 1]. And since line 5 switches min to index this new location, at the end of
the current iteration, it follows at the beginning of the next iteration that min
indexes the smallest element in subarray A[i … j – 1]. Hence, the loop invariant
holds.

Termination: The loop terminates when j = n. According to the statement of the

loop invariant, min indexes an element less than or equal to all elements in
subarray A[i … j – 1]. So, at the termination of the loop, min indexes an element
less than or equal to all elements in subarray A[i … n – 1]. Hence, the loop finds
the smallest element in this subarray, which is useful in the outer loop because
the element at min can then be moved into its final position.

Outer Loop invariant (for loop of lines 1–6)

At the start of each iteration of the outer for loop, the subarray A[0 … i – 1]
consists of the i smallest elements in A[0 … n – 1] sorted in non-decreasing
order. The subarray A[i … n – 1] consists of the n – i remaining elements in A[0
… n – 1].

Initialisation: Initially, i = 0 and so the subarray A[0 … i – 1] is empty, which

trivially holds. The subarray is empty because i – 1 = 0 – 1 = -1 is a non-existing
index.

Maintenance: From the proof of the inner loop, after the execution of the inner
loop, A[min] will be the smallest element of the subarray A[i … n – 1]. And at
the beginning of the outer loop, the subarray A[0 … i – 1] contains i elements,
in sorted order, that are smaller than the elements of A[i … n – 1]. After the
execution of the outer loop, A[i] becomes the smallest element in the subarray
A[i … n – 1], and the subarray A[0 … i] will consists of elements, in sorted order,
that are smaller than the elements of A[i + 1 … n – 1]. This implies that at the
end of the loop:

A[i] < A[k] for i < k

Termination: The loop terminates when i = A.length – 1. At that point, array A[0
… n – 1] will contain all the elements sorted in non-decreasing order. Because,
from the maintenance phase of the loop invariant we know that at the end of
an iteration of the outer loop, the subarray A[0 … i] consists of sorted elements.
Substituting n – 1 for i, we have the subarray A[0 … n – 1] which consists of the
original elements, but in sorted order. This is the entire array, so the entire array
is sorted. Hence, the loop invariant holds.

Algorithms and Unit 4 Dr F. Adamu-Fika

6 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
Note, the steps above in proving the loop invariants constitute an induction proof,
which shows that when the program leaves the loop:

A´[0] ≤ A´[1] ≤ A´[2] ≤ … ≤ A´[n – 1]

Efficiency Analysis
The selection sort has a straightforward analysis. The input size is given by the number
of elements in the array (list), n; the basic operation is the key comparison A[j] < A[min]
(on line 4). The number of times it is executed depends only on the input size and is
given by the following sum:
!"( !"#

𝐶(𝑛) = ' ' 1

&%) $%&'#

We start solving the summations from the innermost loop:

!"#

' 1 = (𝑛 − 1) − (𝑖 + 1) + 1
$%&'#

=𝑛−1−𝑖−1+1=𝑛−1−𝑖
!"(

∴ 𝐶(𝑛) = '(𝑛 − 1 − 𝑖)
&%)

!"( !"( !"(

= '𝑛− '1− '𝑖

&%) &%) &%)

!"( (!"()'# !"#

'𝑛= ' 𝑛 = ' 𝑛 = (𝑛 − 1) ⋅ 𝑛

&%) &%# &%#

!"( (!"()'#

'1= ' 1 = (𝑛 − 1)
&%) &%#

!"( !"(
(𝑛 − 2) ⋅ [(𝑛 − 2) + 1] (𝑛 − 2)(𝑛 − 1)
'𝑖 = '𝑖 = =
2 2
&%) &%#

!"(
(𝑛 − 2)(𝑛 − 1)
∴ '(𝑛 − 1 − 𝑖) = [𝑛(𝑛 − 1)] − [𝑛 − 1] − 1 2
2
&%)

(𝑛 − 2)(𝑛 − 1)
= [(𝑛 − 1)(𝑛 − 1)] − 1 2
2
[2(𝑛 − 1)(𝑛 − 1)] − [(𝑛 − 2)(𝑛 − 1)]
=
2
(𝑛 − 1)[2(𝑛 − 2) − (𝑛 − 2)]
=
2

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 7
© Since 2020 Elementary Algorithms Lecture Notes
(𝑛 − 1)(2𝑛 − 2 − 𝑛 + 2)
=
2

(𝑛 − 1)𝑛 1 1
= 1= 𝑛( − 𝑛2
2 2 2
Thus, selection sort is 𝑂(𝑛( ) on all inputs. Note, however, that the number of swaps is n
–1, exactly one swap for each iteration of i. Thus, the complexity of swaps is 𝑂(𝑛).

If we want to sort in non-decreasing order and the array is in non-increasing order

then, the worst case occurs. The best case occurs when the array is already sorted.
The average case occurs when the elements of the array are in jumbled order (neither
non-decreasing nor non-increasing). The time complexity of the selection sort is the
same in all cases. Because, at every pass, you have to find the smallest element and
put it in the right place. The smallest element is unknown until the end of the array is
reached. Thus, the time complexities for selection sort are:

• Worst Case Complexity: Θ(𝑛( )

• Best Case Complexity: Θ(𝑛( )
• Average Case Complexity: Θ(𝑛( )

Space complexity is 𝑂(1) because the sorting happens in place and only an extra
variable is used.

The insertion sort is an unstable algorithm, it does not preserve the relative ordering of
the equal elements in the original list when sorting.

When to use Selection Sort

The selection sort is used when:

• a small list is to be sorted;

• cost of swapping does not matter;
• checking of all the elements is compulsory;
• cost of writing to memory matters like in flash memory (number of writes/swaps
is 𝑂(𝑛).

BUBBLE SORT

The bubble sort is another brute force approach to sorting order-able lists. The bubble
sort compares adjacent elements of the list and swaps them if they are out of order.
By repeatedly doing so, we end up ‘bubbling up’ the largest element to its final
position in the list.

Algorithm: How Bubble Sort Works

To explain the working of bubble sort, let’s use the problem instance from our selection
sort, [5, 3, 2, 4, 1].

Algorithms and Unit 4 Dr F. Adamu-Fika

8 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
First Iteration
At the start of the first iteration, our list looks like this:

5 3 2 4 1

The elements that are being compared are highlighted in red and elements in their
final positions are shown in green.

1. Starting from the first index, compare the first two elements. If the first element
is greater than the second element, exchange them.

>

5 3 2 4 1

3 5 2 4 1

swap

2. Next, compare the second and third elements and swap them if the second
element is larger.

>

3 5 2 4 1

3 2 5 4 1

swap

This process goes on till the end of the unsorted list when the last and second
to the last elements in the list are compared.

> >

3 2 5 4 1 3 2 4 5 1

3 2 4 5 1 3 2 4 1 5

swap swap

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 9
© Since 2020 Elementary Algorithms Lecture Notes
After the 1st pass (before i increases when i = 0), the list: [3, 2, 4, 1, 5]

3 2 4 1 5

The Remaining Iterations

1. The same process goes on for the remaining iterations. However, the
comparisons and swaps stop at the last unsorted element in the list (i.e., the last
element that is not in its final position).
2. After each iteration, the largest element among the unsorted elements is
placed at the end of that sublist.

After the 2nd pass (before i increases when i = 1), the list: [2, 3, 1, 4, 5]

2 3 1 4 5

After the 3rd pass (before i increases when i = 2) , the list: [2, 1, 3, 4, 5]

2 1 3 4 5

After the (n–1)th pass (before i increases when i = n – 2), the list: [1, 2, 3, 4, 5]

1 2 3 4 5

After the nth pass (before i increases when i = n – 1), the list: [1, 2, 3, 4, 5]

1 2 3 4 5

Bubble sort works by progressively maintaining two sublists until the entire list is sorted:
(1) consists of the largest elements already sorted, at the back of the list and (2)
consists of the remaining elements that need sorting, at the front of the list.

Again, we assume the list as an array with the first index at 0 and the last index at n –
1. On the ith pass, the list scans from the start of the array through the remaining n – i
unsorted elements and finds the largest element among them. Whatever element is
found to be the largest element is pushed to its final position at the end of the unsorted
subarray.

?
A[0], …, A[j] ↔A[j + 1], …, A[n – 1 – i] | A[n – i] ≤ A[n – i + 1] ≤ … ≤ A[n – 1]

The remaining n – i unsorted Elements in their final positions

elements

Algorithms and Unit 4 Dr F. Adamu-Fika

10 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
Similar to the selection sort, we can see that after n – 1 passes the array will be fully
sorted. The last pass (nth pass) is redundant, as the element at index 0 will be at its final
position when every other element succeeding it is put in its right position. This pass
compares A[0] with itself, and thus, our selection sort algorithm follows only indexes i
up to n – 2.

Algorithm BubbleSort(A)
Input: an array, A[0 … n – 1], with n order-able items.
Output: The array, A, sorted in non-decreasing order.
START
1. for( i = 0; i < n - 1; i++ ) //for i = 0 to n – 2
2. for( j = 0; j < n – 1 - i; j++ ) //for j = 0 to n – 2 – i
3. if( A[j + 1] < A[j] )
4. Swap( A, j, j + 1 ) //swap A[j+1] with A[j]
5. return A
END

Correctness Proof
Let A´ denote the output of BubbleSort(A).

To prove that BubbleSort is correct, we need to prove that it terminates and that:

A´[0] ≤ A´[1] ≤ A´[2] ≤ … ≤ A´[n – 1]

where n = A.length.

Formal Proof using Loop Invariants

Like with our selection sort algorithm, because there are two loops in our bubble sort
algorithm, we will prove the inequality above in two parts:

a. We precisely state a loop invariant for the inner for loop in lines 2—4 and prove
that this loop invariant holds.

b. Using the termination condition of the loop invariant proved in part (a), we will
precisely state a loop invariant for the outer for loop in lines 1—4 that will allow
us to prove the inequality.

Theorem:
A´ consists of the elements in A but is sorted in non-decreasing order.

Proof:
Inner Loop invariant (for loop of lines 2–4)
At the start of each iteration of the inner loop, (1) the subarray A[0 … j] consists
of the elements originally in A[0 … j] before entering the inner loop but possibly
in a different order and (2) the last element A[j] of the subarray is the largest in
it.

Initialisation: Initially, j = 0 and so the subarray A[0 … j] contains only one

element, A[j], which is the first element of A, and is trivially the largest element
of the subarray.

Maintenance: In each iteration, we compare A[j] to A[j + 1] and make A[j + 1]

the largest among them. Because we are only adding the next element and

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 11
© Since 2020 Elementary Algorithms Lecture Notes
possibly swapping two values, claim (1) of the loop invariant holds. Since A[j +
1] becomes the largest among A[j] and A[j + 1], at the end of the iteration, the
length of the subarray increases by one and the last element is the largest of
the subarray. So, claim (2) of the loop invariant holds.

Termination: The loop terminates when j = n – i – 1. According to the statement

of the loop invariant, A[j] is the largest element in A[0 … j] and the subarray
contains the elements originally in A[0 … j] before entering the loop.

Outer Loop invariant (for loop of lines 1–4)

At the start of each iteration of the outer loop, the subarray A[n – i … n – 1]
consists of the i largest elements in A[0 … n – 1] sorted in non-decreasing order.
The subarray A[0 … n – i – 1] consists of the n – i remaining elements in A[0 …
n – 1].

Initialisation: Initially, i = 0 and so the subarray A[n – i … n – 1] is empty, which

trivially holds. The subarray is empty because n – i = 5 – 0 = 5], which is an index
that does not exist in the array.

Maintenance: From the proof of the inner loop, after the execution of the inner
loop, A[n – 1 – i] will be the largest element of the subarray A[0 … n – 1 – i].
And at the beginning of the outer loop, the subarray A[n – i … n – 1] contains
elements, in sorted order, that are larger than the elements of A[0 … n – 1 – i].
After the execution of the outer loop, the subarray A[n – 1 – i … n – 1] will
consists of elements, in sorted order, that are larger than the elements of A[0 …
n – i – 2]. This implies that at the end of the loop:

A[k] < A[n – 1 – i] for k < n – 1 – i

Termination: The loop terminates when i = A.length – 1. At that point, array A[0
… n – 1] will contain all the elements sorted in non-decreasing order. Because,
from the maintenance phase of the loop invariant we know that at the end of
an iteration of the outer loop, the subarray A[n – 1 – i … n – 1] consists of sorted
elements. Substituting n – 1 for i (n – 1 – (n – 1) = n – 1 – n + 1 = 0), we have
that the subarray A[0 … n – 1] consists of the original elements, but in sorted
order. This is the entire array, so the entire array is sorted.

Note, the steps above in proving the loop invariants constitute an induction proof,
which shows that when the program leaves the loop:

A´[0] ≤ A´[1] ≤ A´[2] ≤ … ≤ A´[n – 1]

Efficiency Analysis
The bubble sort, like the selection sort, has a straightforward analysis. The input size is
given by the number of elements in the array (list), n; the basic operation is the key
comparison A[j+1] < A[j] (on line 3). The number of times it is executed depends only
on the input size and is given by the following sum:
!"( !"("&

𝐶(𝑛) = ' ' 1

&%) $%)

We start solving the summations from the innermost loop:

Algorithms and Unit 4 Dr F. Adamu-Fika

12 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
!"("& (!"("&)'# !"#"&

' 1= ' 1= ' 1

$%) $%# $%#

=𝑛−1−𝑖
!"(

∴ 𝐶(𝑛) = '(𝑛 − 1 − 𝑖)
&%)

!"( !"( !"(

= '𝑛− '1− '𝑖

&%) &%) &%)

!"( (!"()'# !"#

'𝑛= ' 𝑛 = ' 𝑛 = (𝑛 − 1) ⋅ 𝑛

&%) &%# &%#

!"( (!"()'#

'1= ' 1 = (𝑛 − 1)
&%) &%#

!"( !"(
(𝑛 − 2) ⋅ [(𝑛 − 2) + 1] (𝑛 − 2)(𝑛 − 1)
'𝑖 = '𝑖 = =
2 2
&%) &%#

!"(
(𝑛 − 2)(𝑛 − 1)
∴ '(𝑛 − 1 − 𝑖) = [𝑛(𝑛 − 1)] − [𝑛 − 1] − 1 2
2
&%)

(𝑛 − 2)(𝑛 − 1)
= [(𝑛 − 1)(𝑛 − 1)] − 1 2
2
[2(𝑛 − 1)(𝑛 − 1)] − [(𝑛 − 2)(𝑛 − 1)]
=
2
(𝑛 − 1)[2(𝑛 − 2) − (𝑛 − 2)]
=
2
(𝑛 − 1)(2𝑛 − 2 − 𝑛 + 2)
=
2

(𝑛 − 1)𝑛 1 1
= 1= 𝑛( − 𝑛2
2 2 2
Thus, bubble sort belongs to the complexity class 𝑂(𝑛( ). However, the number of key
swaps depends on the input. In the worst case of a non-increasing sorted array, it is
the same as the number of key comparisons. Thus, the complexity of swaps is 𝑂(𝑛( ).

If we want to sort in non-decreasing order and the array is in non-increasing order

then, the worst case occurs. The best case occurs when the array is already sorted.
The average case occurs when the elements of the array are in jumbled order (neither
non-decreasing nor non-increasing). The worst-case time complexity of the bubble
sort is Θ(𝑛( ), because, in each pass, a swap will occur after each key comparison. In
the best case, the time complexity is Θ(𝑛) because no key swap will occur, as larger
elements will always be in an index after smaller elements. The time complexity in the

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 13
© Since 2020 Elementary Algorithms Lecture Notes
average case is the same as in the worst case, Θ(𝑛( ). Thus, the time complexities for
bubble sort are:

• Worst Case Complexity: Θ(𝑛( )

• Best Case Complexity: Θ(𝑛)
• Average Case Complexity: Θ(𝑛( )

Space complexity is 𝑂(1) because the sorting happens in place and only an extra
variable is used.

The bubble sort is a stable algorithm, it maintains the original ordering of the identical
elements when sorting.

When to use Bubble Sort

The bubble sort is used when:

• complexity does not matter;

• short and simple code is preferred.

As is often the case when using a brute-force strategy, the first version of an algorithm
obtained can often be improved upon with a modest amount of effort. Considering
our bubble sort algorithm above, we can improve on it by exploiting the following
observation: if a pass through the list makes no swaps, then the list has been sorted
and we can stop the algorithm. Though this improved version runs faster on some
inputs, it is still in Θ(𝑛( ) in the worst and average cases. Also, even among elementary
sorting methods, bubble sort is an inferior choice.

INSERTION SORT

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place
in each iteration. Insertion sort applies the decrease and conquer approach to sort a
list. Specifically, it uses the decrease-by-one technique, it assumes a smaller problem
of the list has already been solved, leveraging this solution to the smaller problem, for
the next unsorted element, it finds its appropriate place among the sorted elements,
and it inserts it there.

Algorithm: How Insertion Sort Works

Let’s use our earlier problem instance [5, 3, 2, 4, 1] to explain how insertion sort works.

5 3 2 4 1

Elements in their final positions (in the sorted sublist) are highlighted in green. The
element currently stored in key is highlighted in red. The element that is currently being
compared to key is shown with a red-bordered. The hole (empty slot) created by
shifting an element to the right is shown as greyed out. A red bar indicates the division
between the sublist being sorted (to the left) and the remaining elements that have
not been considered yet.

Algorithms and Unit 4 Dr F. Adamu-Fika

14 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
1. The first element is assumed to be sorted. And the second element is copied
separately in a variable, let’s call this variable, key. key is the element being
inserted.

key key
5 3 2 4 1 5 3 2 4 1
3
copy

2. Compare key with the first element. If the first element is greater than key, then
key is placed in front of the first element otherwise key is placed behind it. Now
the first two elements are sorted.

key key
5 3 2 4 1 5 5 2 4 1
3 3
>
move

key
3 5 2 4 1
3

insert

At end of the 1st pass (before i increases when i = 1), the list: [3, 5 | 2, 4, 1]

key
3 5 2 4 1
3

3. Now, the next unsorted element (the third) is taken as the new key, and we
compare it to the elements to the left of it, starting with the one immediately
preceding it. If we find an element smaller than it, we place it just behind that
element. Otherwise, if there is no element smaller than it, we then place it at
the beginning of the array.

key
3 5 2 4 1
2
copy

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 15
© Since 2020 Elementary Algorithms Lecture Notes
key key
3 5 5 4 1 3 3 5 4 1
2 2

>
move

key key
3 5 2 4 1 3 5 5 4 1
2 2
>
move

key
2 3 5 4 1
2

insert

At the end of 2nd pass (before i increases when i = 2), the list: [2, 3, 5 | 4, 1]

key
2 3 5 4 1
2

4. We continue, repeating the process in step 3 until every unsorted element is

placed in its final position.

key
2 3 5 4 1
4
copy

key key
2 3 5 4 1 2 3 5 5 1
4 4
>
move

key key
2 3 5 5 1 2 3 4 5 1
4 4
> insert

At the end of 3rd pass (before i increases when i = 3), the list: [2, 3, 4, 5 | 1]

key
2 3 4 5 1
4

Now, we do the 4th pass.

Algorithms and Unit 4 Dr F. Adamu-Fika

16 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
key
2 3 5 4 1
1
copy

key key
2 3 4 5 1 2 3 4 5 5
1 1

>
move

key key
2 3 4 5 5 2 3 4 4 5
1 1
>
move

key key
2 3 4 4 5 2 3 3 4 5
1 1

>
move

key key
2 3 3 4 5 2 2 3 4 5
1 1

>
move

key
1 2 3 4 5
1

insert

At the end of the 4th pass, i.e., the (n – 1)th pass (before i increases when i = 4
i.e., i = n – 1), the list: [1, 2, 3, 4, 5 |]

key
1 2 3 4 5
1

It is clear to see that insertion sort is based on a recursive idea, however, it is more
efficient to implement this iteratively. Starting with A[1] and ending with A[n – 1], A[i] is
inserted in its appropriate place among the first i elements of the array that have
already been sorted. However, unlike selection sort, these are generally not their final
positions.

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 17
© Since 2020 Elementary Algorithms Lecture Notes
A[0] ≤ … ≤ A[j] ≤ A[j + 1] ≤ … ≤A[i – 1] | A[i], … , A[n – 1]
Smaller or Greater than
equal to A[i]
A[i]

Following is our pseudocode for this algorithm.

Algorithm InsertionSort(A)
Input: an array, A[0 … n – 1], with n order-able items.
Output: The array, A, sorted in non-decreasing order.
START
1. for( i = 1; i < n; i++ ) //for i = 1 to n – 1
2. key = A[i]
3. j = i – 1
4. while( j >= 0 && A[j] > key)
5. A[j + 1] = A[j]
6. j = j – 1
7. A[j + 1] = key
8. return A
END

Correctness Proof
Let A´ denote the output of InsertionSort(A).

To prove that InsertionSort is correct, we need to prove that it terminates and that:

A´[0] ≤ A´[1] ≤ A´[2] ≤ … ≤ A´[n – 1]

where n = A.length.

Formal Proof using Loop Invariants

Like with our previous sorting algorithms, there are two loops in our insertion sort
algorithm. Hence, we will prove the above inequality in two parts:

a. We precisely state a loop invariant for the inner while loop in lines 4—6 and
prove that it holds.

b. Using the termination condition of the loop invariant proved in part (a), we will
precisely state a loop invariant for the outer for loop in lines 1—7 that will allow
us to prove the inequality.

Theorem:
A´ consists of the elements in A but is sorted in non-decreasing order.

Proof:
Inner Loop invariant (while loop of lines 4–6)
At the start of each iteration of the inner loop, each element of the subarray
A[j … i] is greater than or equal to key, A[j … i] ≥ key.

Initialisation: Initially, j = i – 1 and so the subarray A[j … i] contains only two

elements, A[j, i]. By explicit testing A[j] ≥ key (execution condition of the while

Algorithms and Unit 4 Dr F. Adamu-Fika

18 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
loop) and A[i] = key (from line 2). Hence, the loop invariant holds upon
initialisation.

Maintenance: In each iteration, line 5 moves A[j], a value that is known to be

greater than key, into A[j + 1], which also held a value that was at least equal
to (greater than or equal to) key. Hence the loop invariant A[j … i] ≥ key is
maintained.

Termination: The loop terminates when j < 0 (i.e., when j is indexing an

undefined location) or when A[j] ≤ key (i.e. when elements of A[0 … j] are
smaller or equal to key). Before j was decremented, the loop invariant, i.e., A[j
+ 1 … i] ≥ key, is true. And elements in the subarray are sorted. After j was
decremented, the subarray A[0 … j] is sorted and consists of elements that are
at most equal to (smaller than or equal to) key, i.e., A[0 … j] ≤ key, which trivially
is true if j < 0 and is true, if j ≥ 0, because A[0 … j] is sorted and A[j] ≤ key. This
also means that A[j + 2 … i] is sorted and consists of elements that are at least
equal to key, i.e., A[j + 2 … i] ≥ key.

Outer Loop invariant (for loop of lines 1–7)

At the start of each iteration of the outer loop, the subarray A[0 … i – 1] is a
sorted permutation of the original subarray A[0 … i – 1].

Initialisation: Initially, i = 1 and so the subarray A[0 … i – 1] contains only one

element A[0], the loop invariantly trivially holds.

Maintenance: From the proof of the inner loop, after the execution of the inner
loop, A[0 … j] is sorted and is at most equal to key, A[0 … j] ≤ key and A[j + 2
… i] is sorted and is at least equal to key, A[j + 2 … i] ≥ key. The inner loop does
not destroy data in A, because, in the first iteration of the outer loop, A[i] is
copied into key. On line 7, key is copied into A[j + 1]. Hence, we get A[0 … i],
which is a sorted permutation of the original i + 1 elements of A. Because key
is restored to A, after the execution of the outer loop, we maintain the invariant
A[0 … i – 1] contains the first i elements of the original array.

Termination: The loop terminates when i = A.length. At that point, array A[0 …
n – 1] will contain all the elements sorted in non-decreasing order. Because,
from the maintenance phase of the loop invariant we know that at the end of
an iteration of the outer loop, the subarray A[0 … i – 1] consists of sorted
elements. Substituting n for i, we have that the subarray A[0 … n – 1] consists
of the original elements, but in sorted order. This is the entire array, so the entire
array is sorted.

Note, the steps above in proving the loop invariants constitute an induction proof,
which shows that when the program leaves the loop:

A´[0] ≤ A´[1] ≤ A´[2] ≤ … ≤ A´[n – 1]

Efficiency Analysis
The input size is given by the number of elements in the array (list), n; the basic
operation is on line 4. We go with key comparison A[j] > key instead of j ≥ 0. The reason
why we did this is simple, j ≥ 0 will execute faster than A[j] > key in an actual
implementation because the latter will require indexing a memory location to

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 19
© Since 2020 Elementary Algorithms Lecture Notes
complete its operation. Secondly, the key comparison is more relevant to the nature
of the algorithm.

The number of times the basic operation is executed depends on the nature of the
input because the number of key comparisons, A[j] > key, depends on the nature of
the input. We do not know exactly how many times this will be, so let's assume line 4 is
executed t number of times. Since we are interested in finding the big-oh of the basic
operation, we will derive an upper bound for t. So, for fixed i, i.e., for one iteration of
the outer loop, let ti be the maximum number of times line 4 can be executed. If the
array is in decreasing sorted order, it results in the worst case. We must compare each
element A[i ] with each element in the entire sorted subarray A[0 … i – 1], and so ti = i
for i = 1, 2, 3, …, n – 1.

Thus, the cost for running the basic operation is given by the following sum:
!"#

𝐶(𝑛) = ' 𝑖
&%#

(𝑛 – 1) ⋅ 7(𝑛 − 1) + 18 1
= = 𝑛(𝑛 − 1)
2 2
Thus, insertion sort belongs to the complexity class 𝑂(𝑛( ). However, the number of
moving keys depends on the input. In the worst case of a non-increasing sorted array,
it is the same as the number of key comparisons. Thus, the complexity of moving
elements is Θ(𝑛( ). The best case occurs when the array is already sorted. In the best
case, the comparison A[j] > key is executed only once in each iteration of the outer
loop. Thus, ti = 1 for i = 1, 2, 3, …, n – 1. Therefore, for sorted arrays, the number of
key comparisons is
!"#

𝐶(𝑛) = ' 1 = 𝑛 − 1
&%#

Thus, in the best case, insertion sorts belong to the complexity class Θ(𝑛). The average
case occurs when the array elements are in jumbled order (neither non-decreasing
nor non-increasing). The time complexity in the average case is the same as in the
worst case, Θ(𝑛( ). Thus, the time complexities for insertion sort are:

• Worst Case Complexity: Θ(𝑛( )

• Best Case Complexity: Θ(𝑛)
• Average Case Complexity: Θ(𝑛( )

Space complexity is 𝑂(1) because the sorting happens in place and only an extra
variable is used.

Insertion sort is a stable algorithm, it maintains the original ordering of the identical
elements when sorting.

When to use Insertion Sort

The insertion sort is used when:

• the array has a small number of elements;

• there are only a few elements left to be sorted.

Algorithms and Unit 4 Dr F. Adamu-Fika

20 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
Note: Insertion is an online sorting algorithm. An online algorithm can accept new
input while sorting is in progress because it can process its input sequentially one by
one. Thus, online sorting algorithms can sort data without having the entire data
available at the beginning

SUMMARY

• The three elementary algorithms presented here are mainly used for the
internal sorting of small data and are comparison-based. In comparison-based
sorting algorithms, we compare elements to determine the order of elements
in the final sorted output.
o Selection sort compares elements to place the smallest elements at the
front of the list.
o Bubble sort compares elements to push the largest elements to the end
of the list.
o Insertion sort compares elements to decide the position of an element
in a partially sorted subarray.
• In addition to the comparison operations, other types of operations are also
performed in these sorting algorithms. But the number of times these operations
execute would always be less than that of the comparison operations. That is
why comparison operation is the determining factor of the time complexity.
o Bubble sort and selection sorts perform swap operations.
o Insertion sort performs shift operations.
• The table below summarises the properties and complexities of these
algorithms.

Bubble Sort Selection Sort Insertion Sort

Time Overall O(𝑛! ) Θ(𝑛! ) O(𝑛! )
Complexity Best Θ(𝑛) Θ(𝑛! ) Θ(𝑛)
Average Θ(𝑛! ) Θ(𝑛! ) Θ(𝑛! )
Worst Θ(𝑛! ) Θ(𝑛! ) Θ(𝑛! )
Swaps or Best Θ(1) Θ(1) Θ(1)
Movements Worst Θ(𝑛! ) Θ(𝑛) Θ(𝑛! )
Auxiliary Space O(1) O(1) O(1)
Algorithmic Paradigm Brute Force Decrease-and-
conquer
(Incremental)
Sorting Method Swapping Swapping Shifting
Sorting in place? Yes Yes Yes
Stability Stable Not stable Stable
o Note: The naïve selection sort discussed here does not have a best case,
a swap always occurs at the end of each pass even if 𝑚𝑖𝑛 and 𝑖 are the
same. Selection sort that has been modified to detect when 𝑚𝑖𝑛 and 𝑖
are equal, and in the case does not do a swap has the best case
complexity. The best case is an already sorted array.

UNIT GOALS

At this point (after completing this unit) you should be able to:

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 21
© Since 2020 Elementary Algorithms Lecture Notes
• Learn, understand and describe the selection, bubble and insertion sorting
algorithms.
• Demonstrate how these three algorithms work and apply them to given
datasets.
• Analyse the correctness and compare the performance of these three
algorithms.
• Discern the appropriate algorithm to use depending on the scenario.
• Implement these three algorithms.

EXERCISES

1. The given list [6, 2, 3, 5, 1, 3, 4] is sorted using an elementary sorting algorithm.

The following shows the state of the list after each pass:
After Pass 1: [2, 3, 5, 1, 3, 4, 6]
After Pass 2: [2, 3, 1, 3, 4, 5, 6]
After Pass 3: [2, 1, 3, 3, 4, 5, 6]
After Pass 4: [1, 2, 3, 3, 4, 5, 6]
After Pass 5: [1, 2, 3, 3, 4, 5, 6]
After Pass 6: [1, 2, 3, 3, 4, 5, 6]
a. Which sorting algorithm is applied?
b. What is the overall complexity of the algorithm?
c. Give this algorithm's best-case and worst-case running times in Θ -
notation. (You do not need to show the efficiency analysis).
d. Why does it need to run for only the first n – 1 elements, rather than for
all n elements?
e. You can observe the algorithm was fully sorted after the fourth pass.
However, the iteration continues. How can we exploit the observation,
that if a pass through the list does not do an exchange, the list is sorted,
and we can stop the algorithm?
f. From (e), analyse the new version above:
i. does it run faster on some input?
ii. what is its complexity in the best and worst cases?

2. Given the following list:

[3, 4, 7, 5, 5, 2, 5, 6]
illustrate the operations of the elementary sorting algorithms on it.

3. Consider the following sorting algorithm:

Algorithm Sort(A)
Input: an array, A[0 … n – 1], of n order-able items.
Output: The array, A, sorted in non-decreasing order.
START
1. for( i = 1; i < n; i++ )
2. key = A[i]
3. j = i – 1
4. while( j >= 0 && A[j] > key)
5. A[j + 1] = A[j]
6. j = j – 1
7. A[j + 1] = key
8. return A

Algorithms and Unit 4 Dr F. Adamu-Fika

22 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020
END

a. How does the algorithm sort the elements, and what is the name of the
algorithm?
b. How many loop invariants does the algorithm maintain? State the loop
invariant(s).
c. Give this algorithm's best-case and worst-case running times in Θ–
notation.
4. Given an optimised bubble sort algorithm that can detect when a list a
completely sorted before (n-1)th pass and stop the sorting process in such
instance. In how many iterations would the algorithm sort the following lists?
a. [3, 4, 5, 2, 1]
b. [1, 2, 3, 4, 5]
c. How many iterations would it take to sort the lists in (a)–(b) using selection
sorting?
5. You have a small array on a flash drive to sort. However, the “memory-write” is
a costly operation.
a. Select an appropriate elementary sort algorithm to sort this small list.
b. What operations does this algorithm use to move numbers from the
unsorted sublist to the sorted list section?
c. How many movements would be needed to completely sort a list in the
worst-case and the best-case scenarios?
6. Given the following list: [7, 1, 6, 2, 4, 8, 5, 3]. Apply the sorting algorithms
indicated in (a) and (b) to the list and do as the questions instructed.
a. Show the state of the list after each swap during a selection sort. To the
right side of the state you provide, indicate all the candidates
considered for the relevant minimum value for the pass in question.
b. Show the state of the list after each “insertion” during an insertion sort.
To the right side of the state you provide, indicate how many shifts were
made to accomplish the insertion in question. You do not need to show
the movements, you only need to mention the total number of
movements that occur during the considered pass.
7. When is an insertion sort better than a selection sort?
8. When is a selection sort better than an insertion sort?
9. A new sorting algorithm, called “pair-sort”, is used to sort pairs of positive
integers by the magnitude of the product they form. For example, the pair (3,5)
form the product, 15 (i.e., 3 x 5).
“pair-sort” is applied to the following list of pairs: [(2,9), (7,3) (1,10) (3,6) (2,4),
(2,5)]. And the following list of pairs is the output produced: [(2,4), (2,5), (1,10),
(3,6), (2,9), (7,3)].
Is “pair-sort” a stable sort? Justify your answer.

Dr F. Adamu-Fika Unit 4 Algorithm and

Cyber Security Dept. AFIT Sorting Algorithms I: Complexity Analysis 23
© Since 2020 Elementary Algorithms Lecture Notes
BIBLIOGRAPHY AND RESOURCES

Textbooks

[1] A. Levitin, Introduction to the Design and Analysis of Algorithms, Boston: Pearson,
2012.

[2] T. H. Cormen, C. E. Leiserson, R. L. Ronald and C. Stein, Introduction to Algorithms,

Cambridge, MA: MIT Press, 2009.

[3] R. Sedgewick and K. Wayne, Algorithms, Boston: Pearson, 2011.

Websites

[1] “Khan Academy,” [Online]. Available:

https://www.khanacademy.org/computing/ap-computer-science-
principles/algorithms-101. [Accessed 30 April 2022].

Algorithms and Unit 4 Dr F. Adamu-Fika

24 Complexity Analysis Sorting Algorithms I: Cyber Security Dept. AFIT
Lecture Notes Elementary Algorithms © Since 2020