Write several sorts and compare their behavior. Tasks and Requirements **Here ar
ID: 3837061 • Letter: W
Question
Write several sorts and compare their behavior.
Tasks and Requirements
**Here are the required files: https://drive.google.com/open?id=0B2gb5h869g2aeHdWZ1lNOWlBdHc
Create a copy of the Java SE Project Template. The project name must follow this pattern: {FLname}_SortComparison_{TERM},
Change the package name in your project from change_this_pkg_name to sortcomparison.
BasicSorter class:
Download the Sorter.java interface and put it in the sortcomparison package.
Read the comments above each method to understand what they are supposed to do.
Create a new class named BasicSorter in the sortcomparison package. In the class creation wizard, click the Add (interface) button, and search for Sorter. Check the "Inherited abstract methods" box. Click Finish. Eclipse will create the class and automatically add method stubs that meet the Sorter interface.
You do not modify the Sorter interface. You add your code to the BasicSorter class.
You must write your own sorting code. It is OK to use the guidebook or wikipedia or other sites to look for pseudo-code versions of the algorithms, but write the code yourself. It is the only way you will really learn how to implement sort algorithms.
Add the unit testing classes. These classes will be used to test the code that you write.
Create a new package in the src folder called sbccunittest. To be clear: sbccunittest should be a child of the src folder, not of the sortcomparison package.
Download BasicSorterTester.java into sbccunittest.
Unit Testing
Debug all java compilation Errors (see the Problems view). The unit tests can't be run until these errors are fixed.
In the Package Explorer, right-click on the sbccunittest package | Run As... | JUnit Test.
Initially, all of the tests will probably fail. However, as you add functionality to the BasicSorter class, tests will begin to pass.
Work on BasicSorter.insertionSort first.
**Implement heapSort.
There is no user interface requirement for this assignment.
Please help Me to write this code
package sortcomparison;
import java.util.*;
public interface Sorter {
/**
* Sorts part or all of a list in ascending order.
*
* @param data
* The list of elements to sort
* @param firstIndex
* Index of the first element to be sorted.
* @param numberToSort
* The number of elements in the section to be sorted.
*/
public void insertionSort(ArrayList data, int firstIndex, int numberToSort);
/**
* Sorts part or all of the list, data, in ascending order. quickSort() must: - Call the insertionSort() function in
* this interface for segments of size 15 or less. - Use the median-of-three method to prevent O(n^2) running time
* for sorted data sets - Call the partition() function in this interface to do its partitioning.
*
* @param data
* The list of elements to sort
* @param firstIndex
* Index of the first element to be sorted.
* @param numberToSort
* The number of elements in the section to be sorted.
*/
public void quickSort(ArrayList data, int firstIndex, int numberToSort);
/**
* Partitions part (or all) of the list. The range of indices included in the partitioning is [firstIndex,
* firstIndex + numberToPartition -1].
*
* @param data
* @param firstIndex
* @param numberToPartition
* @return The index, relative to data[0], where the pivot value is located at the end of this partitioning.
*/
public int partition(ArrayList data, int firstIndex, int numberToPartition);
/**
* Sorts part or all of a list in ascending order.
*
* mergeSort() must: - Call the insertionSort() function in this interface for segments of size 15 or less. - Call
* the merge() function in this interface to do its merging.
*
* @param data
* list of elements to sort
* @param firstIndex
* Index of the first element to be sorted.
* @param numberToSort
* The number of elements in the section to be sorted.
*/
public void mergeSort(ArrayList data, int firstIndex, int numberToSort);
/**
* Merges two sorted segments into a single sorted segment. The left and right segments are contiguous.
*
* @param data
* The list of elements to merge
* @param firstIndex
* Index of the first element of the left segment.
* @param leftSegmentSize
* The number of elements in the left segment.
* @param rightSegmentSize
* The number of elements in the right segment.
*/
public void merge(ArrayList data, int firstIndex, int leftSegmentSize, int rightSegmentSize);
/**
*
*
* Sorts the list in ascending order.
*
* @param data
* The list of elements to sort
*/
public void heapSort(ArrayList data);
/**
*
*
* Heapifies the given list.
*
* @param data
* The list to heapify.
*/
public void heapify(ArrayList data);
}
////Here where We shold overwrite..
package sortcomparison;
import java.util.*;
public class BasicSorter implements Sorter {
@Override
public void insertionSort(ArrayList data, int firstIndex, int numberToSort) {
// TODO Auto-generated method stub
}
@Override
public void quickSort(ArrayList data, int firstIndex, int numberToSort) {
// TODO Auto-generated method stub
}
@Override
public int partition(ArrayList data, int firstIndex, int numberToPartition) {
// TODO Auto-generated method stub
return 0;
}
@Override
public void mergeSort(ArrayList data, int firstIndex, int numberToSort) {
// TODO Auto-generated method stub
}
@Override
public void merge(ArrayList data, int firstIndex, int leftSegmentSize, int rightSegmentSize) {
// TODO Auto-generated method stub
}
@Override
public void heapSort(ArrayList data) {
// TODO Auto-generated method stub
}
@Override
public void heapify(ArrayList data) {
// TODO Auto-generated method stub
}
}
******TESTER****I HAVE TO PASS THIS TEST****
package sbccunittest;
import static junit.framework.Assert.*;
import static org.apache.commons.io.FileUtils.*;
import static org.apache.commons.lang3.StringUtils.*;
import java.io.*;
import java.util.*;
import org.junit.*;
import fullboard.*;
public class FullBoardTester {
public static int totalScore = 0;
public static int extraCredit = 0;
public static InputStream defaultSystemIn;
public static PrintStream defaultSystemOut;
public static PrintStream defaultSystemErr;
public static String newLine = System.getProperty("line.separator");
@BeforeClass
public static void beforeTesting() throws Exception {
totalScore = 0;
extraCredit = 0;
String fbSrc = readFileToString(new File("src/fullboard/Main.java"));
if (fbSrc.contains("fullboardri"))
throw new Exception("Reference to fullboardri found");
}
@AfterClass
public static void afterTesting() {
System.out.println("Estimated score (w/o late penalties, etc.) = " + totalScore);
}
@Before
public void setUp() throws Exception {
defaultSystemIn = System.in;
defaultSystemOut = System.out;
defaultSystemErr = System.err;
}
@After
public void tearDown() throws Exception {
System.setIn(defaultSystemIn);
System.setOut(defaultSystemOut);
System.setErr(defaultSystemErr);
}
@Test
public void testFileNotFound() throws Exception {
sendToStdinOfTestee("blah.txt ");
final ByteArrayOutputStream myOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(myOut));
Main.main(null);
String output = myOut.toString();
System.setOut(defaultSystemOut);
StringBuilder sb = new StringBuilder("File not found.");
sb.append(newLine + "Complete" + newLine);
String expectedOutput = sb.toString();
// Convert to common end-of-line system.
output = output.replace(" ", " ");
expectedOutput = expectedOutput.replace(" ", " ");
assertEquals(expectedOutput, output);
totalScore += 5;
}
@Test
public void testSmallMapsFile() throws IOException {
String filename = "smallmaps.txt";
generateSmallMapsFile(filename);
sendToStdinOfTestee(filename);
final ByteArrayOutputStream myOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(myOut));
Main.main(null);
String output = myOut.toString();
System.setOut(defaultSystemOut);
// Expected output
sendToStdinOfTestee(filename);
final ByteArrayOutputStream expectedOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(expectedOut));
fullboardri.Main.main(null);
String expectedOutput = expectedOut.toString();
System.setOut(defaultSystemOut);
// out.println(expectedOutput);
// Convert to common end-of-line system.
output = output.replace(" ", " ");
writeStringToFile(new File("smallmaps_out.txt"), output);
expectedOutput = expectedOutput.replace(" ", " ");
writeStringToFile(new File("smallmaps_expected_out.txt"), expectedOutput);
// Go through outputs, map by map
String[] oMaps = substringsBetween(output, "map ", "endmap ");
String[] eMaps = substringsBetween(expectedOutput, "map ", "endmap ");
assertEquals("The number of maps doesn't match.", eMaps.length, oMaps.length);
totalScore += 5;
// Verify that the # of moves is correct for all maps
for (int ndx = 0; ndx < eMaps.length; ndx++) {
String[] olines = oMaps[ndx].split(" ");
String[] elines = eMaps[ndx].split(" ");
assertTrue("Each map must have a least one line defined in it.", olines.length > 0);
assertEquals("The minimum number of moves doesn't match", elines[0].trim(), olines[0].trim());
}
totalScore += 10;
// Verify all maps match.
assertEquals(expectedOutput, output);
totalScore += 10;
}
@Test(timeout = 120000)
public void testLargeMapsFile() throws IOException {
String filename = "largemaps.txt";
generateLargeMapsFile(filename);
sendToStdinOfTestee(filename);
final ByteArrayOutputStream myOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(myOut));
Main.main(null);
String output = myOut.toString();
System.setOut(defaultSystemOut);
writeStringToFile(new File("largemaps_out.txt"), output);
// Expected output
sendToStdinOfTestee(filename);
final ByteArrayOutputStream expectedOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(expectedOut));
fullboardri.Main.main(null);
String expectedOutput = expectedOut.toString();
System.setOut(defaultSystemOut);
// Convert to common end-of-line system.
output = output.replace(" ", " ");
expectedOutput = expectedOutput.replace(" ", " ");
// Verify that the number of maps is correct
String[] oMaps = substringsBetween(output, "map ", "endmap ");
String[] eMaps = substringsBetween(expectedOutput, "map ", "endmap ");
assertEquals("The number of maps doesn't match.", eMaps.length, oMaps.length);
totalScore += 5;
if (oMaps.length == eMaps.length) {
boolean numMovesCorrect = true;
String message = null;
// Verify that the number of moves is correct
for (int ndx = 0; ndx < eMaps.length; ndx++) {
String[] expectedLines = eMaps[ndx].split(" ");
String[] outputLines = oMaps[ndx].split(" ");
if (!outputLines[1].trim().equals(expectedLines[1].trim())) {
numMovesCorrect = false;
message = "For large map " + (ndx + 1) + " the number of moves do not match.";
}
}
assertTrue(message, numMovesCorrect);
totalScore += 5;
}
// Verify that all output is as expected.
assertEquals(expectedOutput, output);
totalScore += 10;
}
private void generateLargeMapsFile(String filename) throws IOException {
int vfi = (int) (Math.random() * 2);
StringBuilder sb = new StringBuilder();
for (int ndx = 0; ndx < 2; ndx++) {
int n = (int) (30 * Math.random() + 20);
String map;
if (ndx != vfi)
map = generateMap(n, n, 5);
else
map = generateLargeValidMap(n);
sb.append("map").append(newLine);
sb.append(map);
sb.append("endmap").append(newLine);
}
writeStringToFile(new File(filename), sb.toString());
}
private String generateLargeValidMap(int n) {
StringBuilder sb = new StringBuilder(generateMap(n, n, 0));
int pos = (int) (4 * Math.random());
switch (pos) {
case 0:
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2 + 1, '');
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2 + 2, '');
break;
case 1:
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2 + 1, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2 + 2, '');
break;
case 2:
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2 + 1) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2, '');
break;
case 3:
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2 + 2, '');
sb.setCharAt((n / 2 + 1) * (n + newLine.length()) + n / 2 + 2, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2 + 2, '');
break;
}
return sb.toString();
}
public void generateSmallMapsFile(String filename) throws IOException {
boolean done = false;
int numMaps = (int) (Math.random() * 4) + 10;
int numNoSolution = (int) (Math.random() * 2) + 1;
StringBuilder sb = new StringBuilder();
int validCount = 0;
List noSolutionIndices = new ArrayList<>(numMaps);
for (int i = 0; i < numMaps; i++)
noSolutionIndices.add(i);
Collections.shuffle(noSolutionIndices);
noSolutionIndices = noSolutionIndices.subList(0, numNoSolution);
int noSolutionCount = 0;
boolean saveSolution = false;
boolean isANoSolution = false;
while (!done) {
int numRows = (int) (Math.random() * 4) + 7;
int numCols = numRows;
int numBlocks = 5;
String map = generateMap(numRows, numCols, numBlocks);
fullboardri.Main checker = new fullboardri.Main(true);
String result = checker.processMap(map);
isANoSolution = result.contains("No solution");
boolean needNoSolution = false;
saveSolution = false;
if (numNoSolution > 0) {
if (noSolutionCount < numNoSolution) {
if ((noSolutionIndices.contains(validCount))) {
needNoSolution = true;
}
}
}
if (isANoSolution) {
if (needNoSolution)
saveSolution = true;
} else
saveSolution = true;
if (saveSolution) {
sb.append("map").append(newLine);
sb.append(map);
sb.append("endmap").append(newLine);
if (needNoSolution)
noSolutionCount++;
validCount++;
if (validCount >= numMaps)
done = true;
}
}
writeStringToFile(new File(filename), sb.toString());
}
public String generateMap(int numRows, int numCols, int numBlocks) {
char[][] map = new char[numRows][numCols];
for (int c = 0; c < numCols; c++)
map[0][c] = '';
for (int r = 1; r < numRows - 1; r++) {
map[r][0] = '';
for (int c = 1; c < numCols - 1; c++)
map[r][c] = ' ';
map[r][numCols - 1] = '';
}
for (int c = 0; c < numCols; c++)
map[numRows - 1][c] = '';
// Place blocks. Note: this is n^2 if numBlocks is of the order of numRows*numCols.
int blocksPlaced = 0;
while (blocksPlaced < numBlocks) {
int r = (int) (Math.random() * (numRows - 2)) + 1;
int c = (int) (Math.random() * (numCols - 2)) + 1;
if (map[r][c] != '') {
map[r][c] = '';
blocksPlaced++;
}
}
// Convert to string
StringBuilder sb = new StringBuilder(numRows * (numCols + newLine.length()));
for (int r = 0; r < numRows; r++) {
for (int c = 0; c < numCols; c++)
sb.append(map[r][c]);
sb.append(newLine);
}
return sb.toString();
}
public void sendToStdinOfTestee(String message) {
System.setIn(new ByteArrayInputStream(message.getBytes()));
}
}
Explanation / Answer
Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.
Time Sort Average Best Worst Space Stability Remarks Bubble sort O(n^2) O(n^2) O(n^2) Constant Stable Always use a modified bubble sort Modified Bubble sort O(n^2) O(n) O(n^2) Constant Stable Stops after reaching a sorted array Selection Sort O(n^2) O(n^2) O(n^2) Constant Stable Even a perfectly sorted input requires scanning the entire array Insertion Sort O(n^2) O(n) O(n^2) Constant Stable In the best case (already sorted), every insert requires constant time Heap Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Constant Instable By using input array as storage for the heap, it is possible to achieve constant space Merge Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Depends Stable On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space Quicksort O(n*log(n)) O(n*log(n)) O(n^2) Constant StableRandomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.