Insertion Sort

Question 1

The sorting problem is;

Given an array of u_________ numbers, how can we sort them so that they end up in ascending order?

Answer 1

unsorted

Question 2

Why is sorting considered as the most fundamental problem in the study of algorithms?

a) Sometimes an application needs to sort information. E.g.
A banking app that sorts cheques by cheque number.

b) Algorithms often use sorting as a key s________________????

c) Historical interest. Many important techniques developed
over the years.

d) We can prove a n__________ lower bound for sorting?????

e) Many engineering issues come to the fore when implementing sorting algorithms. The fastest sorting program for a particular situation may depend on many factors, such as prior knowledge about the keys and satellite data, the memory hierarchy (caches and virtual memory) of the host computer, and the software environment. Many of these issues are best dealt with at the algorithmic level, rather than by “t_____________” the code.

Answer 2

subroutine
nontrivial
tweaking

Question 3

What does it mean by sorting in place?

Sorting in place refers to an algorithm that requires only a small, c_________ number of elements to be temporarily stored o________ of the array.

Answer 3

constant
outside

Question 4

Insertion Sort

Insertion Sort is of the comparison sort.
It determines the sorted order of an input array by c___________ elements.

Answer 4

comparing

Question 5

Insertion Sort

Insertion Sort is an efficient algorithm for sorting a s_______ number of elements.

Answer 5

small

Question 6

Insertion Sort - How it works

Let’s say we have an array of unsorted numbers A[1…n]

e.g. {3, 2, 5, 4, 1}

1) Start at index 1, pull out the element at Index 1 and store in a ‘temp’ variable.

e.g. 3, 5, 4, 1

                 2

2) Compare temp variable (2) to the element on the l_____ (3).
If 3 is bigger then 2, move 3 to the right and put 2 back in the
list where 3 was placed.

e.g. 2, 3, 5, 4, 1

3) Go to index 2 and repeat.

Answer 6

left

Question 7

Insertion Sort - Efficiency

There are 4 steps that occur in Insertion Sort:

1) Removals
2) C____________
3) S____________
4) Insertions

Answer 7

comparisons
shifts

Question 8

Insertion Sort - Efficiency

Comparisons
In the worst-case scenario, where the list is in reversed order (e.g. 5,4,3,2,1), we would have to make 1+2+3+4 (n-1) comparisons.

It works out to O(n^2)

Come back to this once you have learnt the maths!!!!