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