COMP171Fall 2005Insertion sortMerge sort
Insertion sort, Merge sort COMP171 Fall 2005
SortingI/Slide2Insertion sort1) Initially p = 12)Let thefirstp elements be sorted3)Insertthe(p+1)thelementproperlyinthelistsothatnowp+1elements are sorted4)incrementpandgoto step (3)
Sorting I / Slide 2 Insertion sort 1) Initially p = 1 2) Let the first p elements be sorted. 3) Insert the (p+1)th element properly in the list so that now p+1 elements are sorted. 4) increment p and go to step (3)
Sorting// Slide3Insertion Sort85132213464OriginalPositions Moved186451343221After p =1co03464513221After p=2816432213451Afterp=3835121323464After p = 46414834512132After p= 5
Sorting I / Slide 3 Insertion Sort
Sorting//Slide4Insertion Sort...for(intp=l:p<a.size);p++)Comparabletmp=a[p];for(j=p;j>o&tmp<aj-lJ;j--)a[j]=a[j-ll;a[j］=tmp;7see appletConsistsofN-1passesForpassp=1throughN-1,ensuresthattheelements inpositionsOthroughpareinsortedorderelementsinpositions0throughp-1arealreadysortedmovetheelementinpositionp leftuntil itscorrectplaceisfound amongthefirstp+ 1 elements
Sorting I / Slide 4 Insertion Sort. Consists of N - 1 passes For pass p = 1 through N - 1, ensures that the elements in positions 0 through p are in sorted order elements in positions 0 through p - 1 are already sorted move the element in position p left until its correct place is found among the first p + 1 elements
SortingI/Slide5Extended ExampleTo sortthefollowing numbers inincreasingorder:34864513221P=1;Lookatfirst elementonly,no changeP = 2; tmp = 8;34>tmp,sosecondelementissetto34We have reached the front of the list.Thus, 1st position=tmpAftersecondpass:83464513221(first2elementsaresorted)
Sorting I / Slide 5 Extended Example To sort the following numbers in increasing order: 34 8 64 51 32 21 P = 1; Look at first element only, no change. P = 2; tmp = 8; 34 > tmp, so second element is set to 34. We have reached the front of the list. Thus, 1st position = tmp After second pass: 8 34 64 51 32 21 (first 2 elements are sorted)