Algorithm Execution Insertion Sort Algorithm Execution We will study the execution of an algorithm on a given instance and predict the execution process We will use Insertion Sort as an example Sorting Sorting is the process of arranging a sequence 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 4 Insertion Sort insert A i into sorted A 1 i 1 j i 1 Insertion Sort A n 1 for i 2 to n do 2 key A i 3 4 5 while j 0 and A j key do 6 7 8 A j 1 key Trace the algorithm using inputs 3 5 2 8 3 A j 1 A j j j 1 5Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 6Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 i 2 key 5 7Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 5 i 2 j 1 8Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 5 i 2 j 1 j 0 Yes 9Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 5 i 2 j 1 j 0 A j key Yes No 10Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 5 i 2 j 1 j 0 A j key Yes No A j 1 key 11Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 5 i 2 j 1 j 0 A j key Yes No A j 1 key Array A is overwritten 12Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 i 2 key 5 13Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 i 3 key 2 14Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 2 i 3 j 2 15Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 2 i 3 j 2 j 0 Yes 16Walk through example A 3 1 5 2 2 3 8 4 3 5 6 7 n 5 key 2 i 3 j 2 j 0 A j key Yes Yes 17Walk through example A 3 1 5 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 2 j 0 A j key Yes Yes A j 1 A j Array A is overwritten 18Walk through example A 3 1 5 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 1 19Walk through example A 3 1 5 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 1 j 0 Yes 20Walk through example A 3 1 5 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 1 j 0 A j key Yes Yes 21Walk through example A 3 1 3 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 1 j 0 A j key Yes Yes A j 1 A j Array A is overwritten 22Walk through example A 3 1 3 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 0 23Walk through example A 3 1 3 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 0 j 0 No 24Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 2 i 3 j 0 j 0 No A j 1 key Array A is overwritten 25Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 i 3 key 2 26Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 i 4 key 8 27Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 8 i 4 j 3 28Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 8 i 4 j 3 j 0 Yes 29Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 8 i 4 j 3 j 0 A j key Yes No 30Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 8 i 4 j 3 j 0 A j key Yes No A j 1 key Array A is overwritten 31Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 i 4 key 8 32Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 i 5 key 3 33Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 3 i 5 j 4 34Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 3 i 5 j 4 j 0 Yes 35Walk through example A 2 1 3 2 5 3 8 4 3 5 6 7 n 5 key 3 i 5 j 4 j 0 A j key Yes Yes 36Walk through example A 2 1 3 2 5 3 8 4 8 5 6 7 n 5 key 3 i 5 j 4 j 0 A j key Yes Yes A j 1 A j Array A is overwritten 37Walk through example A 2 1 3 2 5 3 8 4 8 5 6 7 n 5 key 3 i 5 j 3 38Walk through example A 2 1 3 2 5 3 8 4 8 5 6 7 n 5 key 3 i 5 j 3 j 0 Yes 39Walk through example A 2 1 3 2 5 3 8 4 8 5 6 7 n 5 key 3 i 5 j 3 j 0 A j key Yes Yes 40Walk through example A 2 1 3 2 5 3 5 4 8 5 6 7 n 5 key 3 i 5 j 3 j 0 A j key Yes Yes A j 1 A j Array A is overwritten 41Walk through example A 2 1 3 2 5 3 5 4 8 5 6 7 n 5 key 3 i 5 j 2 42Walk through example A 2 1 3 2 5 3 …
View Full Document
Unlocking...