G Shells increment sequence h2=LN/2」,hk=Lhk+1/2」 void Shellsort( ElementType al], int N) int i, j, Increment; ElementType Tmp; for( Increment =N/2; Increment >0; Increment/=2) /h sequence " for(i=Increment; i< N; i++)[/ insertion sort * Tmp=Ali for(j=i; j>= Increment; j-= Increment if( Tmp <A[j-Increment A[J]=A[j-Increment] else break. A[j]=Tmp; 3/end for-I and for-Increment loops */
Shell’s increment sequence: ht = N / 2 , hk = hk+1 / 2 void Shellsort( ElementType A[ ], int N ) { int i, j, Increment; ElementType Tmp; for ( Increment = N / 2; Increment > 0; Increment /= 2 ) /*h sequence */ for ( i = Increment; i < N; i++ ) { /* insertion sort */ Tmp = A[ i ]; for ( j = i; j >= Increment; j - = Increment ) if( Tmp < A[ j - Increment ] ) A[ j ] = A[ j - Increment ]; else break; A[ j ] = Tmp; } /* end for-I and for-Increment loops */ }
G Worst-Case Analysis: (Theorem The worst-case running time of Shellsort using Shell's increments, is O(N2) Example〗 a bad case: 1921034 125 147158 16 8-sort 山。20|3m4s|3 14715 81 16 4sor[19213m412|513 14715816 2-sort192|10311412513614715816 I-sort 山234568|9omn2n314s|16 Pairs of increments are not necessarily relatively prime. Thus the smallerincrement can have little effect
Worst-Case Analysis: 【Theorem】The worst-case running time of Shellsort, using Shell’s increments, is ( N2 ). 〖Example〗A bad case: 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16 8-sort 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16 4-sort 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16 2-sort 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16 1-sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Pairs of increments are not necessarily relatively prime. Thus the smaller increment can have little effect
C Hibbard's Increment Sequence: h=2k-1 - consecutive increments have no common factors k (Theorem The worst-case running time of Shellsort using Hibbard's increments, is O(N3/2) Shellsortis a very simple CoNjectureS: algorithm, yet with an extremely complex analysis. It is good for sorting up to G Tavg-Hibbard(N)=O(N5/4) moderately large input (tens of thousands) G Sedgewick's best sequence is (1, 5, 19, 41,. in which the terms are either of the form 9x4'-9x2+1 or 4-3×2+1.T3y2(N)=0(N6) and worst(N)=0(N43
Hibbard’s Increment Sequence: hk = 2 k − 1 ---- consecutive increments have no common factors. 【Theorem】The worst-case running time of Shellsort, using Hibbard’s increments, is ( N3/2 ). Conjectures: Tavg – Hibbard ( N ) = O ( N5/4 ) Sedgewick’s best sequence is {1, 5, 19, 41, 109, … } in which the terms are either of the form 94 i – 92 i + 1 or 4 i – 32 i + 1. Tavg ( N ) = O ( N7/6 ) and Tworst ( N ) = O ( N4/3 ). Shellsort is a very simple algorithm, yet with an extremely complex analysis. It is good for sorting up to moderately large input (tens of thousands)
§5 Mergesort 1. Merge two sorted lists 4 Bptr 3 2426 2152738 口2「「「「□ Cptr T(N)=O(N )where N is the total number of elements
§5 Mergesort 1. Merge two sorted lists 1 13 24 26 2 15 27 38 1 2 Aptr Bptr Cptr Aptr Cptr Bptr Cptr T ( N ) = O ( ) where N is the total number of elements. N
2. Mergesort void MSort( ElementType A[], ElementType TmpArray[], int Left, int Right i int Center if Left Right )[/if there are elements to be sorted * Center =( Left Right )/2, MSort(A, TmpArray, Left, Center ) /T(N/2) MSort(A, TmpArray, Center +1, Right ) /T(N/2) Merge(A, TmpArray, Left, Center +1, Right );/O(N)*/ void Mergesort( ElementType A[], int N) I ElementType *TmpArray; /* need O(N)extra space * TmpArray malloc( N* sizeof( ElementType)); if TmpArray NULL)t MSort(A,TmpArray, 0, N-1); free( TmpArray ) else FatalError("No space for tmp array ! ") /*If a TmpArray is declared locally for each call of Merge, then S(N)=O( NlogN)
2. Mergesort void MSort( ElementType A[ ], ElementType TmpArray[ ], int Left, int Right ) { int Center; if ( Left < Right ) { /* if there are elements to be sorted */ Center = ( Left + Right ) / 2; MSort( A, TmpArray, Left, Center ); /* T( N / 2 ) */ MSort( A, TmpArray, Center + 1, Right ); /* T( N / 2 ) */ Merge( A, TmpArray, Left, Center + 1, Right ); /* O( N ) */ } } void Mergesort( ElementType A[ ], int N ) { ElementType *TmpArray; /* need O(N) extra space */ TmpArray = malloc( N * sizeof( ElementType ) ); if ( TmpArray != NULL ) { MSort( A, TmpArray, 0, N - 1 ); free( TmpArray ); } else FatalError( "No space for tmp array!!!" ); } /*If a TmpArray is declared locally for each call of Merge, then S(N) = O( NlogN)*/