Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn
Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn
What are algorithms? d A sequence of computational steps that transform the input into the output Sorting problem: Input: A sequence of n numbers <a1, a2,.,a Output: A permutation(reordering)<a,a2, ..., a'n such that a'1sa2≤….san Instance of sorting problem: Input:<32,45,64,28,45,58> Oupu:<28,32,45,45,58,64>
What are algorithms? A sequence of computational steps that transform the input into the output Sorting problem: Input: A sequence of n numbers < a1, a 2, …, a n > Output: A permutation (reordering) < a' 1, a' 2, …, a' n > such that a' 1 ≤ a' 2 ≤ … ≤ a' n Instance of sorting problem: Input: <32, 45, 64, 28, 45, 58> Output: <28, 32, 45, 45, 58, 64>
Example of insert sort 822222 8 433 44884 999986 333398 66666 done
Example of insert sort 8 2 493 6 2 8 493 6 24 8 93 6 24 89 3 6 23 489 6 23 468 9 done
Insertion sort INSERTION-SORT(A) I for j←2 to length[4] 2 do key←A 3 / Insert AG] into the sorted sequence All.j-1] 4 while i>0 and ai>key doA[i+11←A[ 7 8[i+1]←key A Sorted
Insertion sort INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ← A[j] 3 // Insert A[j] into the sorted sequence A[1 .. j − 1] 4 i ← j − 1 5 while i > 0 and A[i] > key 6 do A[i + 1] ← A[i] 7 i ← i − 1 8 A[i + 1] ← key A: 1 i j key n Sorted
Running time a The running time depends on the input: an already sorted sequence is easier to sort a Parameterize the running time by the size of the input, since short sequences are easier to sort than long ones a Generally, we seek upper bounds on the running time, because everybody likes a guarantee
Running time The running time depends on the input: an already sorted sequence is easier to sort. Parameterize the running time by the size of the input, since short sequences are easier to sort than long ones. Generally, we seek upper bounds on the running time, because everybody likes a guarantee