Question

The following submission rules apply: • For those questions requiring programs, the solutions must be implemented using JavaScript or Java. o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices. o Solutions must be provided in plain text so that formatting is not lost. • All answers must be provided in this document. • Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.

1. Demonstrate the action of ShellSort on the list (33, 2, 56, 23, 55, 78, 2, 98, 61, 108, 14, 60, 56, 77, 5, 3, 1), with increments (5, 3, 1)

Answer 1

ShellSort.java

import java.util.*;
 
public class ShellSort{
 
  public static void sort(int[] array) {
    int inner, outer;
    int temp;
 
    int h = 1;
    while (h <= array.length / 3) {
      h = h * 3 + 1;
    }
    while (h > 0) {
      for (outer = h; outer < array.length; outer++) {
        temp = array[outer];
        inner = outer;
 
        while (inner > h - 1 && array[inner - h] >= temp) {
          array[inner] = array[inner - h];
          inner -= h;
        }
        array[inner] = temp;
      }
      h = (h - 1) / 3;
    }
  }
 
  public static void main(String[] args) {
 
    int [] array = {33, 2, 56, 23, 55, 78, 2, 98, 61, 108, 14, 60, 56, 77, 5, 3, 1};
    System.out.println("Before: " + Arrays.toString(array));
    sort(array);
    System.out.println("After:  " + Arrays.toString(array));
 
  }
}
 

Output:-

Before: [33, 2, 56, 23, 55, 78, 2, 98, 61, 108, 14, 60, 56, 77, 5, 3, 1]
After:  [1, 2, 2, 3, 5, 14, 23, 33, 55, 56, 56, 60, 61, 77, 78, 98, 108]

Demonstrate the action of ShellSort on the list---->
[33, 2, 56, 23, 55, 78, 2, 98, 61, 108, 14, 60, 56, 77, 5, 3, 1]

After increments of size 8 The list is 
[1, 2, 14, 23, 55, 77, 2, 3, 33, 108, 56, 60, 56, 78, 5, 98, 61]

After increments of size 4 The list is 
[1, 2, 2, 3, 33, 77, 5, 23, 55, 78, 14, 60, 56, 108, 56, 98, 61]

After increments of size 2 The list is 
[1, 2, 2, 3, 5, 23, 14, 60, 33, 77, 55, 78, 56, 98, 56, 108, 61]

After increments of size 1 The list is 
[1, 2, 2, 3, 5, 14, 23, 33, 55, 56, 56, 60, 61, 77, 78, 98, 108]

[1, 2, 2, 3, 5, 14, 23, 33, 55, 56, 56, 60, 61, 77, 78, 98, 108]