Decrementing Increment or Just Shell-Sort - Practices
One of the main activities in algorithms and programs, whose purpose is manipulating data, is sorting. So if you write these kinds of programs-what kind of method for sorting data is best? In this article I will present some algorithms for sorting and their advantages and weaknesses.
Shell-sorting is a better solution than insertion-sort, but it also contains insertion-sorting. First it splits our unsorted array into groups. In each group are elements whose positions in the array are on equidistant positions.
The number of spaces between elements in groups is called increment h1. Tbe number of groups, naturally, suits the value of increment. Now each group is sorted by insertion-sort method, after that our array is h1-sorted.
In our next step our increment is decremented and its value is h2. Then we form smaller numbers of groups with more elements per group. Our algorithm ends when our increment reaches value one. This means that now we just use insertion-sort on the whole array, after that our array is completely sorted.
Letís see what this algorithm looks like:
-SORT: for i =1 to n do inc=h[i] for j=inc+1 to n do y=a[j] k=j-inc while ((k>=1) and (y<=a[k])) do a[k+inc] = a[k] k=k-inc end_while end_for end_for
In this algorithm we assume that we have our increments in an array h[1:t]. Notice that everything inside the second for loop is just insertion-sort method used on groups.
It's not obvious that this method has better performances than insertion-sort, but it does. In the beginning our increment h is big so groups are smaller, that means that speed increases on each group using insertion-sort. Each consecutive step our groups are bigger, but now those groups are sorted, facilitating insertion-sort on remaining groups. See step-by-step how this works below: