Sorting by Diminishing Increment : Sort The Random Numbers by Way of Sorting by Diminishing Increments

Problems on the case this time as follows, given a randomly ordered set  of n numbers sort them into non-descending ordered using Shell’s diminishing increment menthod.

We can develop a sorting algorithm by diminishing increment following. A method is needed that initially move element s over long distances then, as the sort progresses,
the distance over which elements are compared and moved is decreased. One strategy for an array of size n is to start by comparing elements over a distance of n/2 and then successively over the distances n/4, n/8, n/16, ..., 1.

Consider what happens when the n/2  idea is applied to the data set below.

After comparison and exchanges over the distance n/2 we have n/2 chains of length two that are “sorted”.

The next step os ro compate elements over a distance n/4 and thus produce two sorted chaind of length  4.

Notice that after the n/4 sort the “amount of disorder” in the array is relatively small.

The final step is to form a single sorted chain if length 8 by comparing and sorting elements distance 1 apart.

Algorithm Description

1. Establis the array a[1..n] of n element.

2. Set the increment size inc to n.

3. While the increment size is greater than one do

                a. Decrease inc by a factor of 2,

                b. For all the inc chains to be sorted at gaps of inc do

                                1) Determine position k of second member of current chain,

                                2) While end of current chain not reached do

                                                a) Use insertion mechanism to put x = a[k] in place

                                                b) Move up current chain one by increading k by inc.

Pascal Implementation

We can make algorithm pascal in C + +. To program in C + + can be downloaded via ziddu. Check it dot!

referensi : How To Solve It By Computer_R.G. Dromey