Here a class that could be used to help sort data in an array. You will need to
ID: 3833628 • Letter: H
Question
Here a class that could be used to help sort data in an array. You will need to complete the insertionSort() method so that it orders the data using insertion sort BUT stops after performing the firstinsertionSteps passes over the array data. You should assume that insertionSteps will not exceed the size of the array. Because we want this code to work with ANY data, you will need to compare items using the Comparator named comp.
InsertionSort
package edu.buffalo.cse116;
import java.util.Comparator;
/**
* This class defines a single public method which performs one be used to sorts an array using insertion-sort.
*
* @author Matthew Hertz
* @param <E> Type of data which instances of this class will be sorting.
*/
public class InsertionSort<E> {
/** Comparator instance we will be using to sort our data. */
private Comparator<E> comp;
/**
* Creates a new instance of this class which will be used to sort members of an array when there are only a few items
* to sort.
*
* @param theComp Comparator instance we will be using for our sorting.
*/
public InsertionSort(Comparator<E> theComp) {
comp = theComp;
}
/**
* Begins to order the smallest {@code insertionSteps} values in the array using insertion sort. While it is unusual
* to terminate midway through the sorting process, this is useful when an instructor needs to write unit tests which
* verify students correctly implemented insertion sort (and is nearly the same as writing the entire method!).
*
* @param arrayToSort Array whose contents are to be sorted.
* @param insertionSteps Specifies how many passes through the array we should take before stopping the sort.
*/
public void insertionSort(E[] arrayToSort, int insertionSteps) {
}
}
----------------------------------------------------------------
Test code
package edu.buffalo.cse116;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;
import java.util.Comparator;
import org.junit.Test;
public class InsertionSortTest {
@Test
public void testSortEmpty() {
Integer[] empty = new Integer[0];
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
try {
sort.insertionSort(empty, 0);
} catch (Exception e) {
fail("Should not do any work and so not create errors when given an empty array. Your code threw an exception: " +
e.toString());
}
assertEquals(0, empty.length);
}
@Test
public void testSortSingle() {
Integer[] single = { 12 };
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
sort.insertionSort(single, 1);
assertEquals("When sorting an array with a single item, your code's array should not do anything.", 12,
(int) single[0]);
}
@Test
public void testSortBestCaseEven() {
String[] sorted = { "Echo", "Alpha", "Bravo", "Charlie", "Delta", "Hotel", "Golf", "Foxtrot" };
Comparator<String> comp = new StrComp();
InsertionSort<String> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 3);
assertEquals("When completing the first 3 steps of the sort, your code did not reorder element at index 0: ",
"Echo", sorted[0]);
assertEquals("When completing the first 3 steps of the sort, your code did not reorder element at index 1: ",
"Bravo", sorted[1]);
assertEquals("When completing the first 3 steps of the sort, your code did not reorder element at index 2: ",
"Alpha", sorted[2]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 3: ",
"Charlie", sorted[3]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 4: ",
"Delta", sorted[4]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 5: ",
"Hotel", sorted[5]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 6: ",
"Golf", sorted[6]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 7: ",
"Foxtrot", sorted[7]);
}
@Test
public void testSortBestCaseOdd() {
String[] sorted = { "Golf", "Alpha", "Charlie", "Delta", "Echo", "Foxtrot", "Bravo" };
Comparator<String> comp = new StrComp();
InsertionSort<String> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 4);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 0",
"Golf", sorted[0]);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 1", "Delta",
sorted[1]);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 2", "Charlie",
sorted[2]);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 3", "Alpha",
sorted[3]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify any entry past index 3 -- at index 4: ",
"Echo", sorted[4]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify any entry past index 3 -- at index 5: ",
"Foxtrot", sorted[5]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify any entry past index 3 -- at index 6: ",
"Bravo", sorted[6]);
}
@Test
public void testSortWorstCaseEven() {
Integer[] sorted = { 984262, 232324, 12842, 9324, 6974, 1932, 100, 12 };
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 3);
assertEquals("When completing the first 3 steps of the sort, your code did not update the item at index 0", 12842,
(int) sorted[0]);
assertEquals("When completing the first 3 steps of the sort, your code did not update the item at index 1", 232324,
(int) sorted[1]);
assertEquals("When completing the first 3 steps of the sort, your code did not update the item at index 2", 984262,
(int) sorted[2]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 3: ",
9324, (int) sorted[3]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 4: ",
6974, (int) sorted[4]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 5: ",
1932, (int) sorted[5]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 6: ",
100, (int) sorted[6]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 7: ",
12, (int) sorted[7]);
}
@Test
public void testSortWorstCaseOdd() {
Integer[] sorted = { 12842, 232324, 9324, 6974, 1932, 100, 12 };
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 4);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 0",
6974, (int) sorted[0]);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 1", 9324,
(int) sorted[1]);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 2", 12842,
(int) sorted[2]);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 3", 232324,
(int) sorted[3]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify the item at indices above 3 -- at index 4: ",
1932, (int) sorted[4]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify the item at indices above 3 -- at index 5: ",
100, (int) sorted[5]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify the item at indices above 3 -- at index 6: ",
12, (int) sorted[6]);
}
public class IntComp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
public class StrComp implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
}
}
Explanation / Answer
Please find my implementation.
import java.util.Comparator;
/**
* This class defines a single public method which performs one be used to sorts an array using insertion-sort.
*
* @author Matthew Hertz
* @param <E> Type of data which instances of this class will be sorting.
*/
public class InsertionSort<E> {
/** Comparator instance we will be using to sort our data. */
private Comparator<E> comp;
/**
* Creates a new instance of this class which will be used to sort members of an array when there are only a few items
* to sort.
*
* @param theComp Comparator instance we will be using for our sorting.
*/
public InsertionSort(Comparator<E> theComp) {
comp = theComp;
}
/**
* Begins to order the smallest {@code insertionSteps} values in the array using insertion sort. While it is unusual
* to terminate midway through the sorting process, this is useful when an instructor needs to write unit tests which
* verify students correctly implemented insertion sort (and is nearly the same as writing the entire method!).
*
* @param arrayToSort Array whose contents are to be sorted.
* @param insertionSteps Specifies how many passes through the array we should take before stopping the sort.
*/
public void insertionSort(E[] arrayToSort, int insertionSteps) {
for (int i=1; i<insertionSteps; ++i)
{
E key = arrayToSort[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && (comp.compare(arrayToSort[j], key) > 0))
{
arrayToSort[j+1] = arrayToSort[j];
j = j-1;
}
arrayToSort[j+1] = key;
}
}
}
###############
import static org.testng.AssertJUnit.assertEquals;
import org.testng.annotations.Test;
import org.testng.Assert;
import java.util.Comparator;
public class InsertionSortTest {
@Test
public void testSortEmpty() {
Integer[] empty = new Integer[0];
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
try {
sort.insertionSort(empty, 0);
} catch (Exception e) {
Assert.fail("Should not do any work and so not create errors when given an empty array. Your code threw an exception: " +
e.toString());
}
assertEquals(0, empty.length);
}
@Test
public void testSortSingle() {
Integer[] single = { 12 };
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
sort.insertionSort(single, 1);
assertEquals("When sorting an array with a single item, your code's array should not do anything.", 12,
(int) single[0]);
}
@Test
public void testSortBestCaseEven() {
String[] sorted = { "Echo", "Alpha", "Bravo", "Charlie", "Delta", "Hotel", "Golf", "Foxtrot" };
Comparator<String> comp = new StrComp();
InsertionSort<String> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 3);
assertEquals("When completing the first 3 steps of the sort, your code did not reorder element at index 0: ",
"Echo", sorted[0]);
assertEquals("When completing the first 3 steps of the sort, your code did not reorder element at index 1: ",
"Bravo", sorted[1]);
assertEquals("When completing the first 3 steps of the sort, your code did not reorder element at index 2: ",
"Alpha", sorted[2]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 3: ",
"Charlie", sorted[3]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 4: ",
"Delta", sorted[4]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 5: ",
"Hotel", sorted[5]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 6: ",
"Golf", sorted[6]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify any entry past index 2 -- at index 7: ",
"Foxtrot", sorted[7]);
}
@Test
public void testSortBestCaseOdd() {
String[] sorted = { "Golf", "Alpha", "Charlie", "Delta", "Echo", "Foxtrot", "Bravo" };
Comparator<String> comp = new StrComp();
InsertionSort<String> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 4);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 0",
"Golf", sorted[0]);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 1", "Delta",
sorted[1]);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 2", "Charlie",
sorted[2]);
assertEquals("When completing the first 4 steps of the sort, your code did not correctly order index 3", "Alpha",
sorted[3]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify any entry past index 3 -- at index 4: ",
"Echo", sorted[4]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify any entry past index 3 -- at index 5: ",
"Foxtrot", sorted[5]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify any entry past index 3 -- at index 6: ",
"Bravo", sorted[6]);
}
@Test
public void testSortWorstCaseEven() {
Integer[] sorted = { 984262, 232324, 12842, 9324, 6974, 1932, 100, 12 };
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 3);
assertEquals("When completing the first 3 steps of the sort, your code did not update the item at index 0", 12842,
(int) sorted[0]);
assertEquals("When completing the first 3 steps of the sort, your code did not update the item at index 1", 232324,
(int) sorted[1]);
assertEquals("When completing the first 3 steps of the sort, your code did not update the item at index 2", 984262,
(int) sorted[2]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 3: ",
9324, (int) sorted[3]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 4: ",
6974, (int) sorted[4]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 5: ",
1932, (int) sorted[5]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 6: ",
100, (int) sorted[6]);
assertEquals("When completing the first 3 steps of the sort, your code should not modify the item at indices above 2 -- at index 7: ",
12, (int) sorted[7]);
}
@Test
public void testSortWorstCaseOdd() {
Integer[] sorted = { 12842, 232324, 9324, 6974, 1932, 100, 12 };
Comparator<Integer> comp = new IntComp();
InsertionSort<Integer> sort = new InsertionSort<>(comp);
sort.insertionSort(sorted, 4);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 0",
6974, (int) sorted[0]);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 1", 9324,
(int) sorted[1]);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 2", 12842,
(int) sorted[2]);
assertEquals("When completing the first 4 steps of the sort, you code did not correctly order index 3", 232324,
(int) sorted[3]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify the item at indices above 3 -- at index 4: ",
1932, (int) sorted[4]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify the item at indices above 3 -- at index 5: ",
100, (int) sorted[5]);
assertEquals("When completing the first 4 steps of the sort, your code should not modify the item at indices above 3 -- at index 6: ",
12, (int) sorted[6]);
}
public class IntComp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
public class StrComp implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
}
}
/*
Sample run:
PASSED: testSortBestCaseEven
PASSED: testSortBestCaseOdd
PASSED: testSortEmpty
PASSED: testSortSingle
PASSED: testSortWorstCaseEven
PASSED: testSortWorstCaseOdd
===============================================
Default test
Tests run: 6, Failures: 0, Skips: 0
===============================================
===============================================
Default suite
Total tests run: 6, Failures: 0, Skips: 0
===============================================
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.