1 Overview In class, we have seen sorting algorithms that work by comparing, and if necessary, swapping, adjacent elements. Now, we will improve upon this idea by swapping elements that are further apart. This document explains how to do this by means of an example. It will be your job to implement the algorithm being explained and provide Java code that can be used for sorting. This homework is just as much about understanding an algorithm as it is about the final implementation in Java. Therefore:

It is EXTREMELY important that you read the whole document before coding. The idea is to avoid large shifts (as may happen in insertion sort). The idea is to create virtual sublists and sort these one by one. These virtual lists are created based on the gap between elements. The final algorithm uses a sequence of gaps, starting with a large value, and getting recursively smaller. The gap values are given by

Notice how each gap value depends on the previous one, as shown in the recursive definition of equation (1). The gap values start at gk = bn/2c, where n is the length of the array.

2 Algorithm Consider the simple array of integers, [35, 33, 42, 10, 14, 19, 27, 44], with the gap value set to be 4. We identify virtual1 sublists of numbers located with a gap of 4 positions, shown in Fig. 1. This yields four sublists of length 2 each: [35,14], [33,19], [42,27], [10,44]. Then, we compare values in each sublist, and whenever necessary, swap them in the original array. Once done, the new array will be [14, 19, 27, 10, 35, 33, 42, 44]

Next, based on equation (1), we set the gap value to be b4/2c = 2. This generates two sublists of length 4 each: [14,27,35,42] and [19,10,33,44]. Just like before, we compare and if necessary, swap values. This step is shown in Fig. 2.

1By virtual, I mean that you just think of these as lists, but not actually create new list or array objects.

Finally, the gap value is set to b2/1c = 1, At this stage, with just one subslist with the length of the entire array, the algorithm becomes effectively the same as insertion sort. The pseudocode of this algorithm is provided below:

3 Programming Tasks For the programming tasks, you must make use of two things:

(1) An enumeration for ascending and descending order: enum Order { ASCENDING, DESCENDING }

(2) An interface specifying the behavior of any sorting class: public interface Sorter> { void sort(List eList, Order order); }

Based on this, your task comprises of writing the three following Java classes:

1. Write a Java class called InsertionSorter that implements the Sorter interface. The sort method in this class must implement the standard insertion sort algorithm we studied in class. This must be an in-place sorting.

2. Write a Java class called MergeSorter that implements the Sorter interface, where the sort method must implement the mergesort algorithm we studied in class.

3. Write a Java class called GapSorter that implements the Sorter interface, where the sort method implements the algorithm discussed above in section 2. This must be an in-place.

Notes For testing purpose, you can use a simple main method like this:

public static void main(String... args) {

Sorter insertionsorter = new InsertionSorter();

Sorter gapsorter = new GapSorter();

Sorter treatmentsorter = new MergeSorter();

.

.

.

insertionsorter.sort(aListOfIntegers, Order.DESCENDING); // similarly for the other sorters }

Your code will be tested with a similar main method, so do not change any name or structure that is specified in the code font in this document. In this assignment, you are not given any objects for testing (like, say, the Treatment object in the last assignment). Your code is generic, and will be tested with objects that have a natural order. The above main method is simply an example of how you can test your own code.

Can I change any given code? No. Code already provided must not be modified.

gk gk-1 gi, where gi 1, and gk-1