Shell sort moves entries by more than one position at a time. It is basically insertion sort with a stride length h - it considers h interleaved sequences and sorts them using insertion sort. When the increment(h) is big, the sub-arrays are smaller and when the increment gets shorter in subsequent iterations, the array is already partially sorted. In both cases, insertion sort works great and hence, it's the best option here.
The optimal value for h is provided by Knuth as 3X+1, but no accurate model has been found for this algorithm yet.
It takes O(N3/2) compares in worst case. It's fast unless array size is large and it has less footprint for code. These make it a perfect choice for hardware sort prototype, linux/kernel, embedded systems etc.
Following is the program:
The optimal value for h is provided by Knuth as 3X+1, but no accurate model has been found for this algorithm yet.
It takes O(N3/2) compares in worst case. It's fast unless array size is large and it has less footprint for code. These make it a perfect choice for hardware sort prototype, linux/kernel, embedded systems etc.
Following is the program:
No comments:
Post a Comment