Insertion Sort: Example of an Algorithm

What is an algorithm?
An algorithm is a sequence of computational steps to solve a well-defined computational problem.

What are the three things an algorithm should be?
The three things an algorithm should be are:

  1. Precise.
  2. Correct.
  3. Finite.

What does a problem specify?
The problem specifies the desired input / output relationship.

Note

What is the formal definition of the sorting problem?

What are the numbers to be sorted called?
The numbers to be sorted are called keys.

What is the data that is often connected to keys?
The data that is often connected to keys are satellite data.

What is the combination of a key and its satellite data called?
The combination of a key and its satellite data is called a record.

What are keys?
Keys are any information that can be used to compare two elements.

...

What are algorithms often written in?
Algorithms are often written in pseudocode.

...

What is a loop invariant used for?
A loop invariant is used for showing the correctness of an algorithm.

What is a loop invariant?
A loop invariant is a property of a program loop that is true before and after each iteration.

What are the three things a loop invariant needs to show?
The three things a loop invariant needs to show are:

  1. Initialization - It is true prior to the first iteration of the loop.
  2. Maintenance - If it is true before an iteration of a loop, it remains true before the next iteration.
  3. Termination - When the loop terminates, the invariant (and the reason the loop terminated) gives us a useful property to prove that an algorithm is correct.

What is the loop invariant of the insertion sort algorithm?
The loop invariant of the insertion sort algorithm is:

At the start of each iteration of the for loop of lines 1-8, the subarray consists of elements originally in , but in sorted order.

Why does the loop invariant hold of the insertion sort algorithm hold true prior to the first iteration of the main loop?
The loop invariant of the insertion sort algorithm holds true at the start of the main loop because:

At the start of the main loop, . The subarray contains just the single element . Since it is only one element, it is trivially sorted.

Why does the loop invariant of the insertion sort algorithm hold true before an iteration and before the next iteration of the main loop?
The loop invariant of the insertion sort algorithm holds true before an iteration and before the next iteration of the main loop because:

At the start of the -th iteration, the subarray is sorted. The algorithm then shifts , , and so on by one position to the right until it finds the right position for such that now .

Why does the loop invariant of the insertion sort algorithm hold true when the main loop terminates?
The loop invariant of the insertion sort algorithm holds true when the main loop terminates because:

When the loop terminates, . Thus, the invariant tells us that the array is sorted. Hence, the algorithm is correct.

...

Analyzing algorithms

What does it mean to analyze an algorithm?
To analyze an algorithm means to estimate the resources that the algorithm requires to finish.

What do the resources of an algorithm include?
The resources of an algorithm include:

  • Running time.
  • Memory.
  • Communication bandwidth.
  • Energy consumption.

What is the most useful measure of the running time of an algorithm?
The most useful measure of the running time of an algorithm is the input size .

Note

What is a random-access machine (RAM)?

Which runtime do you typically want to analyze?
The runtime you typically want to analyze is the worst-case scenario runtime.

...

The average-case is often as bad as the ...
The average-case is often as bad as the worst-case.

What is the most general technique for analyzing the runtime of an algorithm?
The most general technique for analyzing the runtime of an algorithm is counting the number of statements executed.

What variable do you use to represent the number of times an inner loop runs for the -th iteration of the outer loop?
The variable you use to represent the number of times an inner loop runs for the -th iteration of the outer loop is .

What are the costs and times for each line in the pseudocode for the insertion sort algorithm?
The costs and times for each line in the pseudocode for the insertion sort algorithm are:

INSERTION-SORT(A) Cost Times
for i = 2 to n
key = A[i]
// Insert A[i] into the sorted subarray A[1:i-1] 0
j = i - 1
while j > 0 and A[j] > key
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key

What is the full equation for the runtime of the insertion sort algorithm when the input is already sorted?
The full equation for the runtime of the insertion sort algorithm when the input is already sorted is:

What is the value of in the equation for the insertion sort algorithm if the input is already sorted?
If the input is already sorted, the value of in the equation for the insertion sort algorithm is 1.

What is the full equation for the runtime of the insertion sort algorithm when the input is sorted in reverse order?
The full equation for the runtime of the insertion sort algorithm when the input is sorted in reverse order is:

What is the value of in the equation for the insertion sort algorithm if the input is sorted in reverse order?
If the input is sorted in reverse order, the value of in the equation for the insertion sort algorithm is .