# 程序代写代做代考 Java algorithm CSE 214 – Homework V

CSE 214 – Homework V

Instructor: Dr. Ritwik Banerjee

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

gk > gk−1 > . . . > g1, where g1 = 1, and

gk−1 =

⌊gk

2

⌋

(1)

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 “virtual”1 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.

1

CSE 214 2 Submission Deadline: Apr 30, 2017

Figure 1: Virtual sublists with gap value 4.

Figure 2: Virtual sublists with gap value 2. Af-

ter performing the necessary swaps, the array

will be [14, 10, 27, 19, 35, 33, 42, 44].

In this example, no swaps are required in the

first sublist. In the second sublist, only 19 and

10 get interchanged.

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:

1: procedure GapSort(int[] a)

2: gap ← ba.length/2c

3: while gap > 0 do

4: for all i such that gap ≤ i < a.length do
5: j ← i
6: k ← a[i]
7: while j ≥ gap and a[i] < a[j− gap] do
8: a[j] ← a[j− gap]
a[j] ← k
9: gap ← bgap/2c
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

}

CSE 214 3 Submission Deadline: Apr 30, 2017

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

1. (10)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. (20)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. (20)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

Sorter

Sorter

.

.

.

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.

Guidelines

• Can I change any given code?

No. Code already provided must not be modified.

• What to submit?

A single .zip file consisting of the three .java files you wrote plus the sorter interface and

the enum.

• As always, uncompilable code will not be graded, and get no credit.

• In this assignment, there will be a 5 point penalty for submitting the the code for one algorithm

in more than one class.

Submission Deadline: Apr 30, 2017, 11:59 pm

Overview

Algorithm

Programming Tasks