the Shell sort, named after its creator D.L. Shell. It is the first algorithm that we will look at that swaps non-adjacent elements, and takes a "divide and conquer" approach. The list is divided into many sublists, which are sorted, and are then merged together. The shell sort takes advantage of the insertion sort, which is very efficient in a best case scenario (that is, the list being sorted is already 'near sorted').
The shell sort divides the list into n/2 sublists, each being n/2 apart. For instance, in a list of ten elements, the first iteration would consist of five lists, two elements each. The first list would be list[0] and list[5], the second would be list[1] and list[6], and so on. Each of these lists is then sorted using an insertion sort. During the next iteration, we divide the list into bigger sublists, with the elements being closer together. In the second iteration, there are n/4 lists, each element being n/4 apart. These lists are then sorted using insertion sort, and so on. The process continues with twice the amount of lists each iteration as in the one before. Each iteration, the list becomes closer to being sorted. The last sort is done on the entire list, using a standard insertion sort. Since the list should be 'near sorted', the algorithm is very efficient.
Note, during some iterations, sublists will contain unequal amount of elements, since the amount of sublists does not evenly divide into the total number of elements. Remember, in integer division, the decimal in the answer is dropped, e.g. 5/2 = 2. Therefore, if we have seven elements, there are three lists during the first iteration. One contains three elements, and the other two each contain two elements.
{6,3,1,5,2,4,9} -> {6,3,1,5,2,4,9}
In the example, list one starts at list[0] (6) and includes every item two apart. The next list starts at list[1] (3) and also includes every item two apart from its position. Since there is no item that is two locations after the '4', the list has only two items.
The code for shell sort is very simple and straightforward. A slightly modified version of the insertion sort is used however. Since the elements of the sublists to be sorted are not adjacent, an increment parameter is added, which specifies how far apart the elements of the sublists are. The value '1' is then replaced by the increment in the original insertion sort code, since it now compares values that are increment apart.
void InSortShell(int *nums,int n, int incr) //array called nums with n elements to be sorted, incr apart
{
for(int i=incr; i<n; i+=incr)
for(int j=i; (j>=incr) && (nums[j] < nums[j-incr]); j-=incr)
swap(nums[j],nums[j-incr]);
}
void ShellSort(int *nums, int n)
{
for(int i=n/2; i>2; i/=2) //each iteration there are twice as many sublists. Divide the distance between each element by 2.
for(int j=0; j<i; j++) //sort each sublist
InSortShell(&nums[j],n-j,i); //the first element of each sublist begins at j, and therefore the entire list is j items shorter (n-j). The elements of the sublist are i apart.
InSortShell(nums,n,1); //do a standard insertion sort on the now nearly sorted list.
}
MFA site not allowed, ITDunya team
Bookmarks