CSE310 Lecture 05: Insertion Sort and Operations CountTopics of this lectureSortingPowerPoint PresentationAlgorithm TraceRunning timeSlide 7Slide 8Slide 9Inverse Number of A SequenceSummaryReadings and [email protected] Lecture 05:CSE310 Lecture 05:Insertion Sort and Operations CountInsertion Sort and Operations CountGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureSortingThe problemAlgorithmsInsertion SortDescriptionExampleWorst-case time complexity•Operations count•Asymptotic [email protected]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 [email protected] SortInsertion-Sort(A)1 for j := 2 to length[A] do2 key := A[j]3 // insert A[j] into sorted A[1..j-1]4 i := j -15 while i > 0 and A[i] > key do6 A[i+1] := A[i]7 i := i - 18 A[i+1] := keyTrace the algorithm using inputs: 3 5 2 8 [email protected] TraceAlgorithm Trace3 5 2 85jikey33 5 2 82jikey32 3 5 8 32 3 5 88jikey32 3 5 83jikey32 3 3 5 [email protected]Number of time steps required for the algorithm to terminateIn 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)Running timeRunning [email protected]Worst case running time is an upper bound on running time for any input of size nBest case is often not very usefulAverage case: average over all possible combinations. It is often as bad as worst case.Worst, best and average case analysisTrace the insertion-sort algorithm using inputs:8 5 3 3 2 2 3 3 5 8 3 5 2 8 [email protected] Timenjjt2 njjt21Insertion-Sort(A[1..n]) times1 for j := 2 to n do n2 key := A[j] n-14 i := j -1 n-15 while i > 0 and A[i] > key do 6 A[i+1] := A[i]7 i := i - 18 A[i+1] := key n-1 njjt21where tj is the number of times while-loop repeats for [email protected] Time)1()1()()1()1()(827625421nctcctcncncncnTnjjnjjWorst Case: The array is in reverse order)(222222)(854287654212765ccccncccccccncccnT cbnan 2)(2nBest Case: The array is sorted)1()1()1()1()(85421 ncncncncncnTbanccccnccccc )()(854285421)(n[email protected] Number of A SequenceInverse Number of A SequenceLet 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 [email protected]Sorting: Problem and Algorithms.Insertion Sort, best case time complexity and worst-case time complexity.Inversion number and its relationship with the time complexity of insertion [email protected] and ExercisesReadings and ExercisesThe 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
View Full Document
Unlocking...