Design Problem Design and implement two methods. Each method will sort a list of
ID: 3793303 • Letter: D
Question
Design Problem
Design and implement two methods. Each method will sort a list of integers, keeping track of the number of times a specific operation occurs. This information will then be used to compare the performance of the two sorting methods. You will also need a test driver for purposes of input, calling the methods, and possibly output, depending on your method implementations.
Input
Input consists of a text data file, sortlist.txt, which contains unique integers in the range 1 to 300, written one value per line. The maximum number of values in the file is 300, but in practice will be many fewer.
Output
The output will be the list of integers sorted into ascending order. Also output will be the number of assignment statements that were made which assigned (not input) a value into the array. Details below will make this clearer.
Method 1 – Sort by address calculation, or perfect hashing
This sort runs in linear time, and is thus very fast. It is restricted to lists of unique (unduplicated) items (integers in our case) that extend over a manageable range. The range of the numbers must be manageable in the sense that we must have enough memory to be able to allocate one unit of memory for each number that might be in the list, whether or not it actually turns to be there. For example, if we are sorting 200 numbers that range from 1 to 9999, we must allocate 9999 units of memory, even though 9799 of the locations are never used.
So, if we are working with integers, we first set each element of an appropriately sized array to 0. As a data value is read from the file, it is placed into its unique spot (e.g., if 57 is read, it is stored in location 57 of the array). To write out the (now) sorted list, scan the array, picking out only nonzero items.
Count each assignment that is made into the array. Giving this a little thought, you know that if the file contains N values, there will be N assignments into the array.
Method 2 – Insertion sort
The insertion sort algorithm can be used to sort numbers in place; that is, not storage (other than one temporary location) is needed other than the space used to hold the unsorted numbers. Sorted values are placed above unsorted ones in a systematic way that never overwrites a value before it is processed. Suppose that a sort of 10 integers has been partially completed to the point that the first thee are in order.
5, 12, 23 Sorted numbers
7,29,19,16,33,4,19 first number not yet sorted
To place the next unsorted number, 7, in its proper place, we must make room to insert it between the 5 and the 12, and we must carefully create the “hole” needed so as not to disturb the ordering of 12 and 23. This can be done by copying the 7 to a temporary location, moving 23 and then 12 down one position, and then inserting the 7 into the position vacated by 12.
But how did we know that the 7 goes between the 5 and the 12 rather than somewhere else? Clearly, a test of some kind must be made in order to find the proper place. What must be done is to scan upward from the number at the end of the partially sorted list, we in the diagram, until either we find a number smaller than or equal to the number we are trying to insert or else we come to the top of the list.
The loop that contains this test can and should be the same loop that moves sorted numbers downward. (You might also think of this as moving a hole upward until it reaches the proper place for inserting a new value.) Sometimes the loop will have to move all currently sorted values down ne, as it will have to do when it comes to the 4, and sometimes it is lucky enough that the next number can be tacked onto the end of the partially sorted list, as will happen when it is time to insert 29 and, later, 33. Even though we showed a partially sorted list as a starting point, you should be able to determine how to start the process with an unsorted list.
Again, keep a count of assignments made into the array as items are moved and inserted (not input).
Explanation / Answer
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import javax.swing.JFileChooser;
import javax.swing.JOptionPane;
public class TestDriver {
static JFileChooser fileDialog;
static int[] sortedlist=new int[300];
public static void main(String args[])
{
insertionsort();
}
//return a filestream to sort.txt
public static Scanner doOpen() {
if (fileDialog == null)
fileDialog = new JFileChooser();
fileDialog.setDialogTitle("Select File to be Opened");
fileDialog.setSelectedFile(null); // No file is initially selected.
int option = fileDialog.showOpenDialog(fileDialog);
if (option != JFileChooser.APPROVE_OPTION)
return null; // User canceled or clicked the dialog's close box.
File selectedFile = fileDialog.getSelectedFile();
Scanner in;
try {
in = new Scanner( selectedFile );
}
catch (FileNotFoundException e) {
JOptionPane.showMessageDialog(fileDialog,fileDialog, "Sorry, but an error occurred while trying to open the file: " + e, option);
return null;
}
return in;
}
public static void perfecthashing()
{
int assignmentcount=0;
Scanner in=doOpen();
int temp;
try {
while (in.hasNextLine()) {
temp = in.nextInt();
sortedlist[temp]=temp;
assignmentcount++;
}
}
catch (Exception e) {
JOptionPane.showMessageDialog(fileDialog,
"Sorry, but an error occurred while trying to read the data: " + e);
}
finally {
in.close();
}
for(int i=0;i<sortedlist.length;i++)
{
if(sortedlist[i]!=0)
{
System.out.println(sortedlist[i]);
}
}
System.out.println();
System.out.println("assignment count :"+assignmentcount);
}
public static void insertionsort()
{
int assignmentcount=0;
Scanner in=doOpen();
int i=0;
ArrayList<Integer> a=new ArrayList<Integer>();
try {
while (in.hasNextLine()) {
a.add(in.nextInt());
}
}
catch (Exception e) {
JOptionPane.showMessageDialog(fileDialog,
"Sorry, but an error occurred while trying to read the data: " + e);
}
finally {
in.close();
}
int[] A = new int[a.size()]; //converting arraylist to primitive array of type int and size equal to array list
for (int k=0; k < A.length; k++)
{
A[k] = a.get(k).intValue();
}
int itemsSorted; // Number of items that have been sorted so far.
for (itemsSorted = 1; itemsSorted < A.length; itemsSorted++) {
// Assume that items A[0], A[1], ... A[itemsSorted-1]
// have already been sorted. Insert A[itemsSorted]
// into the sorted part of the list.
int temp = A[itemsSorted]; // The item to be inserted.
int loc = itemsSorted - 1; // Start at end of list.
while (loc >= 0 && A[loc] > temp) {
A[loc + 1] = A[loc]; // Bump item from A[loc] up to loc+1.
loc = loc - 1; // Go on to next location.
assignmentcount++;
}
A[loc + 1] = temp; // Put temp in last vacated space.
assignmentcount=assignmentcount+3;
}
for(int j=0;j<A.length;j++)
{
if(A[j]!=0)
{
System.out.println(A[j]);
}
}
System.out.println();
System.out.println("assignment count :"+assignmentcount);
}
}