Algorithm analysis Binary search is quicker than sequence search, So the average performance of binary insertion sort is better than direct insertion sort The number of key comparison have nothing to do with the initial order of objects to be sort, but depend on the number of objects. it needs the number of Llog,i +1 key comparison when inserting the ith object. so if we need to insert n objects, the number of key comparison is as follows ∑dg2l」 g,l+1)≈n·l0g,n
◼ Binary search is quicker than sequence search, so the average performance of binary insertion sort is better than direct insertion sort. ◼ The number of key comparison have nothing to do with the initial order of objects to be sort, but depend on the number of objects. it needs the number of log2 i +1 key comparison when inserting the ith object. so if we need to insert n objects, the number of key comparison is as follows： ( ) − = + 1 1 2 2 log 1 log n i i n n Algorithm analysis
When n is large, The number of key comparison is less than the number of direct insertion sort's key comparison in the worst condition, but is more than in the best condition When the initial sequential object is in order or as near as in order. The number of direct insertion sort's key comparison is less than the number of the binary insertion sorts. but the number of moving elements is the same, depending on the original order Binary insertion sort is a stable sort method The Time Complexity is o(n2)
◼ When n is large, The number of key comparison is less than the number of direct insertion sort’s key comparison in the worst condition, but is more than in the best condition. ◼ When the initial sequential object is in order or as near as in order, The number of direct insertion sort’s key comparison is less than the number of the binary insertion sort’s. but the number of moving elements is the same, depending on the original order. ◼ Binary insertion sort is a stable sort method. ◼ The Time Complexity is o(n2)
83 A Lower Bound for Simple Sorting Algorithms (Definition] An inversion in an array of numbers is any ordered pair(i,j) having the property that i<j buta[> All [ Example] Input list 34, 8, 64, 51, 32, 21 has 9 inversions. (34,8)(34,32)(34,21)(64,51)(64,32)(64,21)(51,32)(51,21)(32,21) There are 9 swaps needed to sort this list by insertion sort. Swapping two adjacent elements that are out of place removes exactly one inversion. T(N,1)=0(/+N where / is the number of inversions in the original array Fast if the list is almost sorted
§3 A Lower Bound for Simple Sorting Algorithms 【Definition】An inversion in an array of numbers is any ordered pair ( i, j ) having the property that i < j but A[i] > A[j]. 〖Example〗 Input list 34, 8, 64, 51, 32, 21 has inversions. 9 (34, 8) (34, 32) (34, 21) (64, 51) (64, 32) (64, 21) (51, 32) (51, 21) (32, 21) There are swaps needed to sort this list by insertion sort. 9 Swapping two adjacent elements that are out of place removes exactly one inversion. T ( N, I ) = O( ) where I is the number of inversions in the original array. I + N Fast if the list is almost sorted
(Theorem) The average number of inversions in an array of n distinct numbers is N(N-1)/4. (Theorem] Any algorithm that sorts by exchanging adjacent elements requires Q2( N2)time on average
【Theorem】The average number of inversions in an array of N distinct numbers is N ( N − 1 ) / 4. 【Theorem】Any algorithm that sorts by exchanging adjacent elements requires ( N2 ) time on average
84 Shellsort --- by Donald Shell Example〗Sort: 8194 9612317952858|1417515 5-sort 35 17 2812141175159658819495 3-sort2812 35154158179475819695 l-sort1112151728354158758199596 y Define an increment sequence h1 h1<h2<…<h1(h1=1) y Define an hk-sort at each phase for k=t, t-1,., 1 Note: An hk-sorted file that is then hk- sorted remains hk-sorted
§4 Shellsort ---- by Donald Shell 〖Example〗Sort: 81 94 11 96 12 35 17 95 28 58 41 75 15 5-sort 35 17 11 28 12 41 75 15 96 58 81 94 95 3-sort 28 12 11 35 15 41 58 17 94 75 81 96 95 1-sort 11 12 15 17 28 35 41 58 75 81 94 95 96 Define an increment sequence h1 < h2 < … < ht ( h1 = 1 ) Define an hk -sort at each phase for k = t, t − 1, …, 1 Note: An hk -sorted file that is then hk−1 -sorted remains hk -sorted