1 Overview In class, we have seen sorting algorithms that work by comparing, and

Question

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 gi, where gi 1, and (1) gk-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 n/2J, where n is the length of the array. 2 Algorithm Consider the simple array of integers C35, 33, 42, 10, 14, 19, 27, 44], with the gap value set to be 4. We identify "virtual" i sublists of numbers located with a gap of 4 positions, shown in Fig. 1. This yields four sublists of length 2 each: C35,14], [33,19], [42, 27], C10,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 L4/2 2. This generates two sublists of length 4 each: C14,27,35,42] and C19, 10,33,44]. Just like before, we compare and if necessary, swap values. This step is shown in Fig. 2 By virtual, I mean that you just think of these as lists, but not actually create new list or array objects

Explanation / Answer

Done mergeSort and insertion sort using Sorter.

SorterApp.java

enum Order {
ASCENDING , DESCENDING;
}

interface Sortable {
<T extends Comparable<T>> void sort(T[] values, Order order);

//<T extends Comparable<T>> void sortDescending(T[] values);
}

class SorterApp {

public static void main(String[] args) {
SorterApp app = new SorterApp();
app.run();
}

private void run() {
sort(new Integer[] { 2, 42, -3, 2, 4 });
sort(new Integer[] { 1, 2, 3, 4, 5 });
sort(new Integer[] { 3, 1, 5, 4, 2 });
sort(new Integer[] { 5, 4, 3, 2, 1 });

System.out.println();

sort(new String[] { "a", "b", "c", "d", "e" });
sort(new String[] { "c", "a", "e", "d", "b" });
sort(new String[] { "e", "d", "c", "b", "a" });
}

private <T extends Comparable<T>> void sort(T[] values) {
Sortable sorter = newSortable(2);
sorter.sort(values, Order.ASCENDING);
  
Utils.printArray(values);
}

/**
* @param sortableAlgorithm
* The type of the algorithm that will be returned.
* @return An instance of the algorithm that was requested.
*/
private Sortable newSortable(int sortableAlgorithm) {
switch (sortableAlgorithm) {
case 1:
return new MergeSort();
case 2:
return new InsertionSort();
default:
return new MergeSort();
}
}

}

Utils.java

import java.util.ArrayList;
import java.util.List;

public class Utils {

/**
* Print all the elements of the array.
*
* @param values
*/
public static <T> void printArray(T[] values) {
for (T temp : values) {
System.out.printf("%3s", temp);
}

System.out.println();
}

/**
* Iterates over all the elements in the array and return an object (RangeElements) with the
* lowest and highest element from it.
*
* @param values
* @return An object with the lowest and highest element from it.
*/
public static <T extends Comparable<T>> RangeElements<T> getLowestAndHighestElement(T[] values) {
if ((null == values) || (values.length < 1)) {
return null;
}

RangeElements<T> rangeElements = new RangeElements<T>();
T lowestElement = values[0];
T highestElement = values[0];

for (int i = 1; i < values.length; i++) {
if (lowestElement.compareTo(values[i]) > 0) {
lowestElement = values[i];
}
if (highestElement.compareTo(values[i]) < 0) {
highestElement = values[i];
}
}

rangeElements.setLowestElement(lowestElement);
rangeElements.setHighestElement(highestElement);
return rangeElements;
}

/**
* Return a list of type T.
*
* @param initialCapacity
* the initial capacity of the list.
* @return List<T>
*/
public static <T> List<T> newList(int initialCapacity) {
return new ArrayList<T>(initialCapacity);
}
}

RangeElements.java

public class RangeElements<T> {

private T lowestElement;
private T highestElement;

public T getLowestElement() {
return lowestElement;
}

public void setLowestElement(T lowestElement) {
this.lowestElement = lowestElement;
}

public T getHighestElement() {
return highestElement;
}

public void setHighestElement(T highestElement) {
this.highestElement = highestElement;
}

}

MergeSort.java

import java.util.List;

public class MergeSort implements Sortable {

@Override
public <T extends Comparable<T>> void sort(T[] values, Order orderType) {

if(orderType.equals(Order.ASCENDING)){
mergeSort(values, 0, values.length - 1, 0);
}

else if(orderType.equals(Order.DESCENDING)){
mergeSort(values, 0, values.length - 1, 1);
}

}

/**
* Split the array until it gets to one value.
*
* @param <T>
* @param arValues
* @param left
* @param right
* @param orderType
*/
private <T extends Comparable<T>> void mergeSort(T[] arValues, int left, int right, int orderType) {
if (left < right) {
// Get the middle of the array.
int middle = (left + right) / 2;

// Divide.
mergeSort(arValues, left, middle, orderType);
mergeSort(arValues, middle + 1, right, orderType);

// Conquer.
merge(arValues, left, middle, right, orderType);
}
}

/**
* Sort and Merge the elements of the array.
*
* @param <T>
* @param arValues
* @param left
* @param middle
* @param right
* @param orderType
*/
private <T extends Comparable<T>> void merge(T[] arValues, int left, int middle, int right, int orderType) {
//
int nrTimes = (right - left) + 1;
//
int leftMoves = left;
T leftValue = null;
//
int middleMoves = middle + 1;
T middleValue = null;

List<T> arTemp = Utils.newList(nrTimes);

for (int i = 0; i < nrTimes; i++) {
if (leftMoves <= middle) {
leftValue = arValues[leftMoves];
}

if (middleMoves <= right) {
middleValue = arValues[middleMoves];
}

if ((leftValue != null) && (middleValue == null)) {
arTemp.add(i, leftValue);
leftMoves++;
leftValue = null;
} else if ((leftValue == null) && (middleValue != null)) {
arTemp.add(i, middleValue);
middleMoves++;
middleValue = null;
} else if (checkBiggerSmaller(leftValue, middleValue, orderType)) {
arTemp.add(i, leftValue);
leftMoves++;
leftValue = null;
} else {
arTemp.add(i, middleValue);
middleMoves++;
middleValue = null;
}

}

// Transfer the sorted elements to the original array.
for (int i = 0; i < nrTimes; i++) {
arValues[left + i] = arTemp.get(i);
}
}

/**
* @param leftValue
* @param middleValue
* @param orderType
* @return True if the left value is smaller or bigger (based on the order type) than the middle
* value.
*/
private <T extends Comparable<T>> boolean checkBiggerSmaller(T leftValue, T middleValue, int orderType) {
if (0 == orderType) {
// Ascending.
return leftValue.compareTo(middleValue) <= 0;
} else {
// Descending.
return leftValue.compareTo(middleValue) >= 0;
}
}

}

InsertionSort.java

public class InsertionSort implements Sortable {

@Override
public <T extends Comparable<T>> void sort(T[] values, Order orderType) {
if(orderType.equals(Order.ASCENDING))
sort(values, 0, 1);
else if(orderType.equals(Order.DESCENDING))
sort(values, 1, 0);
}

private <T extends Comparable<T>> void sort(T[] values, int first, int second) {
if ((null == values) || (values.length < 2)) {
return;
}

int length = values.length;
int j;

for (int i = 1; i < length; i++) {
j = i;
while ((j > 0) && (values[j - first].compareTo(values[j - second]) < 0)) {
//swap(values, j - first, j - second);
T temp = values[j-first];

values[j-first] = values[j-second];
values[j-second] = temp;
j--;
}
}

}
}

//////////// ReadMe ///////////////////

SorterApp.java is the main class.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.