Data Structure and Algorithms – Shell Sort

What is hill’s algorithm?

Hill sort is an efficient sorting algorithm based on insertion sort. This algorithm avoids the maximum displacement (conversion) in the insertion sort case if the smaller value is at the far right end and must be moved to the far left

The algorithm uses insertion sort for widely distributed elements, sorting them first and then for elements that are closely spaced. This interval is called an interval. The interval is calculated according to the nuss formula:

The algorithm first uses a large interval element for insertion sort, and then uses a small interval element for insertion sort. This interval is called interval< increment >(gap, increment) and is calculated according to The Nuss formula:

H = h * 3 + 1 WHERE − h is interval with initial value 1Copy the code

For moderately sized data sets, this algorithm is very efficient because the algorithm’s average and worst-case complexity depends on the interval sequence (gap array, GAP array), most famously the gap sequence (n), where n is the number of items. The worst case is O (n).

How does Hill sort work?

Let’s think about how Hill sorting works in terms of the following example. We use the same array as in the previous example. To make our example easier to understand, we use the < interval/increment > of 4. We create a virtual sublist with < interval/increment > of step 4. These values are {35,14}, {33,19}, {42,27}, and {10,44}, respectively.

We compare the values in each sublist and swap them (if necessary) in the original array. After this step, the new array should look like this:

We then use the < interval/increment > of step 2 to generate the sublist. This < interval/increment > generates two sublists: {14,27,35,42}, {19,10,33,44}

If necessary, we compare and swap the values in the original array. After completing these steps, the array should look like this:

Finally, we use < interval/increment > with a step of 1 to sort the remaining arrays. Hill sort uses insert sort to sort these arrays as follows:

We see that it only takes four swaps to sort the rest of the array.

Algorithm

Step 1 – Initialize the value of h

Step 2 – Divide the list into smaller lists with equal intervals of h

Step 3 – Sort these sublists using insert sort

Step 4 – Repeat until the complete list is sorted

Non-js pseudocode:

procedure shellSort()
    A : array of items 
    
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while

   while interval > 0 do:
      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;
      
         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while

end procedure
Copy the code

Javscript:

function shell_sort(arr) {
        for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
                for (let i = gap; i < arr.length; i++) {
                        let temp = arr[i];
                        for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                                arr[j + gap] = arr[j];
                        }
                        arr[j + gap] = temp;
                }
        }
        return arr;
};
Copy the code