Hello Friends, In this blog post ‘Shell sort in data structure‘ I am going to let you know about a very interesting and useful sort in a data structure that is known as Shell Sort.
Inside this blog post(Shell sort in data structure), we are going to cover What is Shell sort example? What is meant by the Shell sort in data structure? What are the 3 types of sorting? What is the main difference between Shell sort and insertion sort?
What is meant by the Shell sort in data structure?
Shell sort is named after its discoverer D.L. Shell. It is also known as diminishing increment sort. In the case of insertion sort, we can move entries only one position because it compares only adjacent keys.
To modify this method using Shell Sort, we first compare keys that are far apart and then sort the entries far apart. Afterward, we sort the entries which are closer together, finally reducing the increment between keys being sorted to 1, to ensure that the file is completely sorted.
What is Shell sort example?
For example, consider the following unsorted file-
20 50 60 70 90 10 80 40 30 100
We choose the sequence(5, 3, 1) as increments. Any other sequence may be chosen, which might work as well or better. However, we must avoid choosing a power of 2, such as 8, 4, 2 and 1 because the same keys compared on one pass will be compared again at the next pass in that case.
If we choose increments that are not multiples of each other, there is a better chance of obtaining new information from more comparisons.
Fig 1 shows the steps of shell sort on the sample file using the increment sequence 3, 3, 1. It should be noted that when the increment is equal to 1, the sort is reduced to simple insertion
The analysis of shell sort turns out to be exceedingly difficult and good estimates on the number of comparisons and moves have been obtained only under special conditions.
However, a simple insertion sort is highly efficient for files which are small and almost in sorted order. Since the first increment used by shell sort is large, the subfiles are quite small and therefore, the insertion sort works fast on these subfiles.
Although the next passes of the shell sort work on large subfiles using smaller increments, these subfiles are almost sorted due to the previous passes.
Therefore, insertion sort on these subfiles is also quite efficient. In general, the shell sort is recommended for moderately sized files of several hundred elements.
What is the main difference between Shell sort and insertion sort?
Insertion sort works with the one sequence(Initially with the first array element) and expands it (using the next element), whereas shell sort has a diminishing increment, which means there is a gap between the compared element.
Please go through the below extensive blog link related to the sorting techniques:
Within this blog post(Shell sort in data structure) we have learned What is Shell sort example, What is meant by Shell sort in the data structure, What are the 3 types of sorting, What is the main difference between Shell sort and insertion sort.
In the case of any queries, you can write to us at [email protected] we will get back to you ASAP.
Hope! you would have enjoyed this post about ‘Shell sort in data structure’.
Please feel free to give your important feedbacks in the comment section below.
Have a great time! Sayonara!