CSE310 Lecture 05 Insertion Sort and Operations Count Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Sorting The problem Algorithms Insertion Sort Description Example Worst case time complexity Operations count Asymptotic analysis 2 Guoliang Xue asu edu Sorting Sorting is the process of arranging a list of objects into order either increasing or decreasing There are many sorting algorithms Different sorting algorithms may have different time complexities The problem also has a complexity There is a difference between problem complexity and algorithm complexity 3 Guoliang Xue asu edu Insertion Sort Insertion Sort A 1 for j 2 to length A do 2 key A j 3 insert A j into sorted A 1 j 1 4 i j 1 5 while i 0 and A i key do 6 A i 1 A i 7 i i 1 8 A i 1 key Trace the algorithm using inputs 3 5 2 8 3 4 Guoliang Xue asu edu Algorithm Trace 5 key 8 key 3 5 2 8 3 2 3 5 8 3 i j i j 2 key 3 key 3 5 2 8 3 2 3 5 8 3 i j i j 2 3 5 8 3 2 3 3 5 8 5 Guoliang Xue asu edu Running time Number of time steps required for the algorithm to terminate In terms of the size of the input to the algorithm which is related to the amount of work to be done E g sorting 1000 numbers takes longer than sorting 3 numbers running time function input size 6 Guoliang Xue asu edu Worst best and average case analysis Worst case running time is an upper bound on running time for any input of size n Best case is often not very useful Average case average over all possible combinations It is often as bad as worst case Trace the insertion sort algorithm using inputs 85332 23358 7 35283 Guoliang Xue asu edu Running Time Insertion Sort A 1 n times 1 for j 2 to n do n 2 key A j n 1 4 i j 1 n 1 5 while i 0 and A i key do 6 A i 1 A i 7 i i 1 8 A i 1 key n 1 n t j 2 j t 1 t 1 n j 2 j n j 2 j where tj is the number of times while loop repeats for j 8 Guoliang Xue asu edu Running Time n n j 2 j 2 T n c1n c2 n 1 c4 n 1 c5 t j c6 c7 t j 1 c8 n 1 Best Case The array is sorted T n c1n c2 n 1 c4 n 1 c5 n 1 c8 n 1 c1 c2 c4 c5 c8 n c2 c4 c5 c8 an b n Worst Case The array is in reverse order c c c c c c T n 5 6 7 n 2 c1 c2 c4 5 6 7 c8 n c2 c4 c5 c8 2 2 2 2 2 2 an 2 bn c n 2 9 Guoliang Xue asu edu Inverse Number of A Sequence Let A 1 n be a sequence of n numbers For 1 i j n we say i j is an inversion if A i A j Note that i j is the inversion not A i and A j The inversion of number of A is the total of inversions for the sequence The running time of insertion sort is n Inversion A where Inversion A is the inversion number of A 10 Guoliang Xue asu edu Summary Sorting Problem and Algorithms Insertion Sort best case time complexity and worstcase time complexity Inversion number and its relationship with the time complexity of insertion sort 11 Guoliang Xue asu edu Readings and Exercises The materials covered in this lecture can be found in Section 2 1 You are encouraged to implement insertion sort using a programming language that you know and try it out with different input data Lecture 06 will be on quicksort 12 Guoliang Xue asu edu
View Full Document
Unlocking...