Sunday, January 4, 2015

Shell sort

N = array.length
H = 1
While H < N/3 
     H = H * 3 + 1

While H => 1
    For I = H to N
       For J = I until J < H or array[J] < array[J-H]; J -= H
              Swap(J, J-H)

     H = H/3

Notice that when H=1 this becomes full blown insertion sort. Before the final pass what it's doing is partially sorting the array by moving out of order elements far distances, resulting in fewer costly inner loops in the final pass. For example, let's say H = 13 and array[13] < array[0]. They would be swapped. In the final pass (during full blown insertion) this potentially saves 13 inner loop swaps. 

No comments:

Post a Comment