Refer : http://education.cdacmumbai.in/education/pgdst/dsalfac/notes/ShellSort.pdf
Shellsort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared.
Shellsort makes multiple passes through a list and sorts a number of equally sized sets using the insertion sort.
Shellsort improves on the efficiency of insertion sort by quickly shifting values to their destination.
Shellsort is also known as diminishing increment sort.
The distance between comparisons decreases as the sorting algorithm runs until the last phase in which adjacent elements are compared
After each phase and some increment hk, for every i, we have a[ i ] ≤ a [ i + hk ] all elements spaced hk apart are sorted.
The file is said to be hk – sorted.
Advantages :
Advantage of Shellsort is that its only efficient for medium size lists. For bigger lists, the algorithm is not the best choice. Fastest of all O(N^2) sorting algorithms.
5 times faster than the bubble sort and a little over twice as fast as the insertion sort, its closest competitor.
Disadvantages :
Disadvantage of Shellsort is that it is a complex algorithm and its not nearly as efficient as the merge, heap, and quick sorts.
The shell sort is still significantly slower than the merge, heap, and quick sorts, but its relatively simple algorithm makes it a good choice for sorting lists of less than 5000 items unless speed important. It's also an excellent choice for repetitive sorting of smaller lists.
Best Case: The best case in the shell sort is when the array is already sorted in the right order. The number of comparisons is less.
Shellsort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared.
Shellsort makes multiple passes through a list and sorts a number of equally sized sets using the insertion sort.
Shellsort improves on the efficiency of insertion sort by quickly shifting values to their destination.
Shellsort is also known as diminishing increment sort.
The distance between comparisons decreases as the sorting algorithm runs until the last phase in which adjacent elements are compared
After each phase and some increment hk, for every i, we have a[ i ] ≤ a [ i + hk ] all elements spaced hk apart are sorted.
The file is said to be hk – sorted.
Advantages :
Advantage of Shellsort is that its only efficient for medium size lists. For bigger lists, the algorithm is not the best choice. Fastest of all O(N^2) sorting algorithms.
5 times faster than the bubble sort and a little over twice as fast as the insertion sort, its closest competitor.
Disadvantages :
Disadvantage of Shellsort is that it is a complex algorithm and its not nearly as efficient as the merge, heap, and quick sorts.
The shell sort is still significantly slower than the merge, heap, and quick sorts, but its relatively simple algorithm makes it a good choice for sorting lists of less than 5000 items unless speed important. It's also an excellent choice for repetitive sorting of smaller lists.
Best Case: The best case in the shell sort is when the array is already sorted in the right order. The number of comparisons is less.
No comments:
Post a Comment