Algorithm CH2 Getting Started
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
- recursive:
Merge sort
Analyse
by construct tree
Algorithm CH2 Getting Started
https://z-hwa.github.io/webHome/[object Object]/Algorithm/Algorithm-CH2-Getting-Started/