Computer Science project

3/11/2016 Lab Assignment Number 7 - cs257

http://cs.sou.edu/~harveyd/classes/cs257/lab7.htm 1/2

Lab Assignment Number 7 – cs257

Optional project for extra credit

 

Goals: Implement sorting algorithms and time them to see which approach is best.

Description

1.      Create a new Lab7 project; your class files should be in a packge called Sort. This project will be a Java Application, not a Java Applet. Make sure that you select the create

Main Project check box after selecting file/new/Java Application. You won’t have to change the Project Properties. 

2.      This lab creates a GUI application that evaluates three sorting methods (bubble, shell, and the built in Java collections sort). A screen shot of my implementation follows.  

  3.       My Implementation has three classes. These are Main, MainPanel, and Sorter. 4.       The Main class

a.  Main is the primary class which contains the public static void main(String[] args) method. It is the only method in this class. It instantiates a JFrame and a MainPanel object and adds the MainPanel to the JFrame content pane. It also calls Jframe methods to set the frame title, the default close operation, size the panel, and set the 

visible.

5.       The MainPanel class extends JPanel a.  The MainPanel class does all its setup work in the constructor. It also implements ActionListener to respond to the calculate button. b.  The layout is Border, with a JScrollPane (holding a JList object) in center, a vertical box layout in the east, and horizontal box in the south. c.  The JList object constructor is called as follows: new JList(new DefaultListModel()). This is necessary to allow the list model to clear and replace the list contents. The

dropdown menus are JComboBox components. String length possibilities are: "10", "20", "30", "40", "50". Data set size possibilities are: "1000", "2000", "4000", "8000", "16000", "32000", "64000", "128000", "256000", "512000", "1024000".  Sort types are: "bubble", "shell", "generic".

d.  Lining up the components in a vertical box layout can be tricky. If you call setAlignmentX(JComponent.CENTER_ALIGNMENT); for each component, things will work out.

e.  Sizing JComboBox components in a vertical box layout can also be tricky. Call setMaximumSize() method for each of these components. f.  Calling createVerticalGlue() and createVerticalStrut() methods can help space the components to they look good. g.  The south section simply contains two labels. Calling setPreferredSize() is useful so the labels don’t change each time the labels are updated. h.  When the calculate button is clicked, the ActionListener actionPerformed() method is called. Clears the JList of rows. It then extracts the selected values from the drop

down menus and calls a doSort() method in the Sorter class (described below). Finally, it fills the JList with the sorted data and gets the times to use to update the label. 

The following code is my implementation, though you probably will use different variable names. Note the try/catch statements. If all goes well, the code executes all the statements between the try and catch. However, if anything goes wrong, the catch executes and the user sees an appropriate error message. Note also, that the user drop down selections for string length and data set size needs to be converted to integers. This is what the Integer.parseInt() method does.

public void actionPerformed(ActionEvent event) { try   {     DefaultListModel model = (DefaultListModel)list.getModel();     model.clear();       String lenString = (String)stringLenBox.getSelectedItem();     int len = Integer.parseInt(lenString);       String nString  = (String)dataSetSizeBox.getSelectedItem();     int n = Integer.parseInt(nString);       int type = sortTypeBox.getSelectedIndex();

3/11/2016 Lab Assignment Number 7 - cs257

http://cs.sou.edu/~harveyd/classes/cs257/lab7.htm 2/2

    String[] data = sorter.doSort(len, n, type);

 

    for (int i=0; i<data.length; i++)

    {  model.add(i, data[i]);  }

 

       long setup = sorter.getSetupTime();

       long sort = sorter.getSortTime();

 

       setupTime.setText("Setup Time: " + setup);

       sortTime.setText("Sort Time: " + sort);

    }

    catch (Throwable e)

        {JOptionPane.showMessageDialog(this, e.toString()); }

}

  6.      The Sorter class contains various methods related to sorting and timing the operations

a.       The following methods: bubbleSort(Comparable data), shellSort(Comparable data), and genericSort(ArrayList<Comparable> dataList) perform the sorts. Refer to the slides for details as to how to code these.

b.      The method, String makeString(len), creates a character array of size len. It then, in a loop, uses Math.random() to choose a character between ‘a’ and ‘z’ and fills up the character array ( (char)(Math.random()*26 + ‘a’) ). Lastly, it instantiates a string from this character array and returns it.

c.       The methods getSortTime() and getSetupTime() simply returns the values of the respective instance variables. d.      The method String[] doSort(int len, int n, int type) randomly creates the data to be sorted and then calls the appropriate sort method. It returns the sorted data. The method

System.currentTimeMillis() enables us to time how long it takes to create data to be sorted and then to perform the various sorts. It returns the current time in milliseconds. To time an operation, long startTime = System.currentTimeMillis();  records a start time. Later, long endTime = System.currentTimeMillis(); records an end time. Subtracting the two provides an elapsed time in milliseconds. The doSort() method should store the results in instance variables so getSortTime() and getSetupTime() can return the results.

Synthesis Questions 1.      Run your program on the various data set sizes and string lengths. Use EXCEL to plot your results creating a line graph. What conclusions can you draw about the data? 2.      The two sorts we implemented are common, but non­optimal. What conclusions can you draw about coding an algorithm that seems like a simple way to go, but turns out to be

non­optimal?

Lab Submission Add the answers to the synthesis questions (saved in a word file called questions.doc) to your lab directory. Make sure to include the questions with the answers. Compress your lab directory and send it to me by e­mail.