Sorting/Slide6P=3:tmp=6434<64,sostopat3rdpositionand set3rdposition=64Afterthirdpass:83464513221(first3elementsaresorted)P=4; tmp=51;51<64,so wehave 8 34 64 64 32 21,34<51,sostopat2ndposition,set3rdposition=tmpAfterfourthpass:83451643221(first4elementsaresorted)P=5;tmp=32,32<64,s083451646421,32<51.S083451516421next32<34.so83434.516421next32>8,sostopat1stpositionandset2ndposition=32Afterfifthpass:83234516421P=6;tmp=21,64Aftersixthpass:821323451
Sorting I / Slide 6 P = 3; tmp = 64; 34 < 64, so stop at 3rd position and set 3rd position = 64 After third pass: 8 34 64 51 32 21 (first 3 elements are sorted) P = 4; tmp = 51; 51 < 64, so we have 8 34 64 64 32 21, 34 < 51, so stop at 2nd position, set 3rd position = tmp, After fourth pass: 8 34 51 64 32 21 (first 4 elements are sorted) P = 5; tmp = 32, 32 < 64, so 8 34 51 64 64 21, 32 < 51, so 8 34 51 51 64 21, next 32 < 34, so 8 34 34, 51 64 21, next 32 > 8, so stop at 1st position and set 2nd position = 32, After fifth pass: 8 32 34 51 64 21 P = 6; tmp = 21, . . . After sixth pass: 8 21 32 34 51 64
Sorting/Slide7Analysis: worst-case running timefor(int p=l;p<a.size(); p++)Comparable tmp=a[p];for(j=p;j>o&&tmpp<ali-lli--)alij=alj-ll;a[ j ］ = tmp;-Innerloopisexecutedptimes,foreachp=1..N= Overall: 1 +2 + 3 + . . . + N = O(N2)SpacerequirementisO(N)
Sorting I / Slide 7 Analysis: worst-case running time Inner loop is executed p times, for each p=1.N Overall: 1 + 2 + 3 + . . . + N = O(N2 ) Space requirement is O(N)