Sorting Points Programming Overview Your task is to sort 3D points according to

Question

Sorting Points

Programming Overview

Your task is to sort 3D points according to their z coordinate to be displayed to the user. Points with a smaller z coordinate will appear on top of points with similar x and y coordinates but greater z coordinates. To accomplish this, you will implement four different sorting methods along with a Point3D object class to represent your 3D points. The four sorting algorithms that you will be implementing are: insertion sort, selection sort, heap sort, and merge sort. For your heap sort, you should be creating a heap-like structure in your method to use for your heap. You should implement your heap sort in-place. You may write and use your own helper methods if you wish. I strongly suggest using a few for some of these sorts.

Before you start implementing your sorting algorithms, you will need to write you Point3D object first. Your Point3D object must implement the Comparable interface so that we can compare our Point3D objects to each other. You must include the following methods in your Point3D class (you may have more, but must have at least these):

public Point3D()

Creates a default 3D points with all coordinates set to 0

public Point3D(int x, int y, int z)

Creates a 3D point with the given coordinates

public int getX()

Returns the x coordinate for the 3D point

public int getY()

Returns the y coordinate for the 3D point

public int getZ()

Returns the z coordinate for the 3D point

public int compareTo(Point3D other)

Compares our point object with the other given point object. Returns a negative value if our point is less than the other, a positive value if our point is greater than the other, or 0 if our point is equal to the other. Since we will be looking at the z values to display the points, you should first consider z values, followed by x, and finally y. For example, if I have a point (3, 2, 1) and another point (1, 2, 3), the first point should be seen as less than the second point.

public String toString()

Returns a String representation of the point in the format of (x, y, z)

Provided Files:

https://drive.google.com/open?id=0BxOSocfKKTXOcGxzdHhoYjIxRnc (For SortingMain.java and DrawingPanel.java)

Write-Up Questions:

1. What are the runtimes for each of the algorithms you implemented (big-oh will suffice)? Provide a brief description as to why they are the runtime you provided.

2. Using Quick Sort, with the median pivot rule (pick the median of: data[lo], data[hi – 1], and data[(hi + lo) / 2]), sort the following list of numbers. Show your work by drawing the tree of partitions and pivots (as seen on the slides) with the partition rules discussed in class (swapping the pivot to index lo and doing swaps to complete the partitions). Apply a cutoff of 3 elements and sort with any sorting method.

data = [5, 7, 9, 1, 3, 4, 6, 8, 2]

3. Using Radix Sort with a radix of 6 (letters: a, b, c, d, e, and f) to alphabetically sort the following Strings, draw the contents of each bucket at the end of each radix ‘digit’ iteration pass.

Strings = (abc, da, ffff, defcd, abebd, ca, b, fef, dfe)

What to turn in:

SortingMain.java – with the sorting methods fully implemented

Point3D.java – entirely written by you as defined above

Electronic version of your write-up

Explanation / Answer

point3d.java

sortingmain.java

}

drwingpanel.java

package sorting; public class Main { public static void main(String[] args) { int[] A = range(1, 1000); long startTime; long duration; startTime=System.nanoTime(); BinarySearcher.search(7,A); duration=System.nanoTime()-startTime; System.out.println("Took "+duration+" "); FisherYatesShuffler.shuffleArray(A); startTime=System.nanoTime(); InsertionSorter.sort(A); duration=System.nanoTime()-startTime; System.out.println("Insertion sort :"); printList(A); System.out.println("Took "+duration+" "); FisherYatesShuffler.shuffleArray(A); startTime=System.nanoTime(); SelectionSorter.sort(A); duration=System.nanoTime()-startTime; System.out.println("Selection sort :"); printList(A); System.out.println("Took "+duration+" "); FisherYatesShuffler.shuffleArray(A); startTime=System.nanoTime(); MergeSorter.sort(A,1,A.length); duration=System.nanoTime()-startTime; System.out.println("Merge sort :"); printList(A); System.out.println("Took "+duration+" "); FisherYatesShuffler.shuffleArray(A); startTime=System.nanoTime(); MergeSorter.sortWithoutSentinels(A, 1, A.length); duration=System.nanoTime()-startTime; System.out.println("Merge sort without sentinels :"); printList(A); System.out.println("Took "+duration+" "); FisherYatesShuffler.shuffleArray(A); startTime=System.nanoTime(); InsertionSorter.sortRecursive(A, A.length - 1); duration=System.nanoTime()-startTime; System.out.println("Insertion sort recursive version :"); printList(A); System.out.println("Took "+duration+" "); FisherYatesShuffler.shuffleArray(A); startTime=System.nanoTime(); HeapSorter.sort(A); duration=System.nanoTime()-startTime; System.out.println("Heap sort :"); printList(A); System.out.println("Took "+duration+" "); FisherYatesShuffler.shuffleArray(A); startTime = System.nanoTime(); BubbleSorter.sort(A); duration = System.nanoTime() - startTime; System.out.println("Bubble sort :"); printList(A); System.out.println("Took " + duration + " "); FisherYatesShuffler.shuffleArray(A); startTime = System.nanoTime(); QuickSorter.sort(A, 0, A.length - 1); duration = System.nanoTime() - startTime; System.out.println("Quick sort :"); printList(A); System.out.println("Took " + duration + " "); FisherYatesShuffler.shuffleArray(A); startTime = System.nanoTime(); QuickSorter.randomizedSort(A, 0, A.length - 1); duration = System.nanoTime() - startTime; System.out.println("Randomized Quick sort :"); printList(A); System.out.println("Took " + duration + " "); FisherYatesShuffler.shuffleArray(A); startTime = System.nanoTime(); int[] B=CountingSorter.sort(A,1000); duration = System.nanoTime() - startTime; System.out.println("Counting sort :"); printList(B); System.out.println("Took " + duration + " "); FisherYatesShuffler.shuffleArray(A); startTime = System.nanoTime(); int[] R=RadixSorter.sort(A,3); duration = System.nanoTime() - startTime; System.out.println("Radix sort :"); printList(R); System.out.println("Took " + duration + " "); } private static void printList(int[] a) { for(int i: a){ System.out.print(i+" "); } System.out.println(" "); } public static int[] range(int start,int stop){ int[] a=new int[stop-start]; for(int i=0;i<stop-start;i++){ a[i]=start+i; } return a; }

}

drwingpanel.java

  import java.awt.*;  import java.awt.event.*;  import java.awt.image.*;  import javax.imageio.*;  import javax.swing.*;  import javax.swing.event.*;    public class DrawingPanel implements ActionListener {      public static final int DELAY = 250;  // delay between repaints in millis        private static final String DUMP_IMAGE_PROPERTY_NAME = "drawingpanel.save";      private static String TARGET_IMAGE_FILE_NAME = null;      private static final boolean PRETTY = true;  // true to anti-alias      private static boolean DUMP_IMAGE = true;  // true to write DrawingPanel to file        private int width, height;    // dimensions of window frame      private JFrame frame;         // overall window frame      private JPanel panel;         // overall drawing surface      private BufferedImage image;  // remembers drawing commands      private Graphics2D g2;        // graphics context for painting      private JLabel statusBar;     // status bar showing mouse position      private long createTime;        static {          TARGET_IMAGE_FILE_NAME = System.getProperty(DUMP_IMAGE_PROPERTY_NAME);          DUMP_IMAGE = (TARGET_IMAGE_FILE_NAME != null);      }        // construct a drawing panel of given width and height enclosed in a window      public DrawingPanel(int width, int height) {          this.width = width;          this.height = height;          this.image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);            this.statusBar = new JLabel(" ");          this.statusBar.setBorder(BorderFactory.createLineBorder(Color.BLACK));            this.panel = new JPanel(new FlowLayout(FlowLayout.CENTER, 0, 0));          this.panel.setBackground(Color.WHITE);          this.panel.setPreferredSize(new Dimension(width, height));          this.panel.add(new JLabel(new ImageIcon(image)));            // listen to mouse movement          MouseInputAdapter listener = new MouseInputAdapter() {              public void mouseMoved(MouseEvent e) {                  DrawingPanel.this.statusBar.setText("(" + e.getX() + ", " + e.getY() + ")");              }                public void mouseExited(MouseEvent e) {                  DrawingPanel.this.statusBar.setText(" ");              }          };          this.panel.addMouseListener(listener);          this.panel.addMouseMotionListener(listener);            this.g2 = (Graphics2D)image.getGraphics();          this.g2.setColor(Color.BLACK);          if (PRETTY) {              this.g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);              this.g2.setStroke(new BasicStroke(1.1f));          }            this.frame = new JFrame("CS307 Drawing Panel");          this.frame.setResizable(false);          this.frame.addWindowListener(new WindowAdapter() {              public void windowClosing(WindowEvent e) {                  if (DUMP_IMAGE) {                      DrawingPanel.this.save(TARGET_IMAGE_FILE_NAME);                  }                  System.exit(0);              }          });          this.frame.getContentPane().add(panel);          this.frame.getContentPane().add(statusBar, "South");          this.frame.pack();          this.frame.setVisible(true);          if (DUMP_IMAGE) {              createTime = System.currentTimeMillis();              this.frame.toBack();          } else {              this.toFront();          }            // repaint timer so that the screen will update          new Timer(DELAY, this).start();      }        // used for an internal timer that keeps repainting      public void actionPerformed(ActionEvent e) {          this.panel.repaint();          if (DUMP_IMAGE && System.currentTimeMillis() > createTime + 4 * DELAY) {              this.frame.setVisible(false);              this.frame.dispose();              this.save(TARGET_IMAGE_FILE_NAME);              System.exit(0);          }      }        // obtain the Graphics object to draw on the panel      public Graphics2D getGraphics() {          return this.g2;      }        // set the background color of the drawing panel      public void setBackground(Color c) {          this.panel.setBackground(c);      }        // show or hide the drawing panel on the screen      public void setVisible(boolean visible) {          this.frame.setVisible(visible);      }        // makes the program pause for the given amount of time,      // allowing for animation      public void sleep(int millis) {          try {              Thread.sleep(millis);          } catch (InterruptedException e) {}      }        // take the current contents of the panel and write them to a file      public void save(String filename) {          String extension = filename.substring(filename.lastIndexOf(".") + 1);            // create second image so we get the background color          BufferedImage image2 = new BufferedImage(this.width, this.height, BufferedImage.TYPE_INT_RGB);          Graphics g = image2.getGraphics();          g.setColor(panel.getBackground());          g.fillRect(0, 0, this.width, this.height);          g.drawImage(this.image, 0, 0, panel);            // write file          try {              ImageIO.write(image2, extension, new java.io.File(filename));          } catch (java.io.IOException e) {              System.err.println("Unable to save image: " + e);          }      }        // makes drawing panel become the frontmost window on the screen      public void toFront() {          this.frame.toFront();      }  

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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