Algorithm CH2 Getting started

2.1 Insertion sort

the number that we wish to sort are known as the keys

Insertion sort

operation

Sorted in place:

• The numbers are rearranged within the array A, with at most a constant number of them sorted outside the array at any time.

Loop invariant:

• At the start of each iteration of the for loop of line 1-8, the subarray A[1,…, j – 1] consists of the elements originally in A[1,…, j – 1] but in sorted order.
• 陣列中的元素沒有發生變化，除了已經被排好

2.2 Analyzing algorithms

worst-case and average-case analyse

Usually, we concentrate on finding only on the worst-case running time.

Reason:

• It is an upper bound on the running time.
• The worst case occurs fair often.
• The average case is often as bad as the worst case. For example, the insertion sort. Again, quadratic function.

order of growth
In some particular cases, we shall be interested in average-case, or expect running time of an algorithm.

It is the rate of growth, or order of growth, of the running time that really interests us.

2.3 designing algorithms

There are many ways to design algorithms:

• Incremental approach: insertion sort
• Divide-and-conquer: merge sort
  • recursive:
    • divide
    • conquer
    • combine

Merge sort

Analyse

by construct tree