96 / \ 47 61 / \ / \ 32 13 50 36 / \ 19 28
The first step is shown for you below:
Original heap: 96 47 61 32 13 50 36 19 28 96 / \ 47 61 / \ / \ 32 13 50 36 / \ 19 28 After first pass: 61 47 50 32 13 28 36 19 | 96 61 / \ 47 50 / \ / \ 32 13 28 36 / 19
public static <T extends Comparable<T>> void sort(T[] table, int a, int b) { if (b - a > 0) { sort(table, a, (a+b)/2); sort(table, (a+b)/2 + 1, b); merge(table, a, b); } }
The merge method copies the elements of table from indices a to b (inclusive) into a new array and then merges the two halves of the new array back into table.
public static <T extends Comparable<T>> void sort(T[] table, int a, int b) { if (b - a > 0) { T pivot = table[a]; int pivotPosition = partition(table, a, b, pivot); sort(table, a, pivotPosition-1); sort(table, pivotPosition+1, b); } }
The partition method rearranges the array so all the elements less than the pivot come first (not necessarily sorted), followed by the pivot, followed by the elements that are greater than or equal to the pivot (not necessarily sorted).
public static void sort(String[] table) { int n = table.length; // number of strings in table int d = table[0].length(); // length of first (or any) string ArrayList[] list = new ArrayList[26]; for (int i = d-1; i >= 0; i--) { for (int k = 0; k < 26; k++) { list[k] = new ArrayList(); } for (int j = 0; j < n; j++) { char ch = table[j].charAt(i); list[ch-'A'].add(table[j]); } int m = 0; for (int k = 0; k < 26; k++) { for (int j = 0; j < list[k].size(); j++) { table[m] = (String)list[k].get(j); m++; } } // For part a: for (String s: table) System.out.println(s); System.out.println(); } }
{"WISK","COKE","TWIX","TIDE","LAYS","DOVE","RAID","ZEST","NIKE","OREO", "RAGU","AJAX","DAWN","SURF","GAIN","CHEX","DOLE","OLAY","LUVS"}
Sorting Algorithm #1:
Sorting Algorithm #2:
Sorting Algorithm #3:
Sorting Algorithm #4:
An grayscale image consists of pixels with intensities between 0 and 255 (inclusive). To store an image, we can use a compressed version using a quadtree. A quadtree is a tree where each node is either a leaf or a nonleaf with 4 children.
Assume that the image region is square and the number of pixels across (and down) is a power of 2, as shown below, where 0,1,2,3 are pixel intensities:
If the image does not consist of pixels of the same intensity, then the image is divided recursively into four quadrants (which are also squares) until each square consists of a single intensity, as shown by the sequence below:
Dividing the image into four quadrants:
Dividing two quadrants again:
Dividing three quadrants again (the final division):
The image can now be stored as a quadtree where the root represents the whole image. If the image is split into 4, the node stores a -1 and has four children representing the image's four quadrants (in the order NW, NE, SW, SE). If the quadrant consists of 1 color only, then the node is a leaf and stores the intensity of the quadrant. This process is repeated for each quadrant if necessary. Based on this information, the image above would be stored as a quadtree as follows:
The quadtree can then be stored in a file, one integer per line, by performing a preorder traversal of the tree:
-1 1 -1 0 3 -1 0 2 0 0 -1 3 0 0 1 0 -1 0 -1 0 0 1 0 2 0
Note that the quadtree file above requires only 25 integers whereas the original image would have required 64 integers (since it is an 8 X 8 image).
Download the QuadTrees.zip project file. Your assignment is to complete a QuadTree class to implement a quadtree that represents a 256 X 256 image.
Your QuadTree class requires an inner class to represent a node of the quadtree. Each node consists of an intensity value and references to four children. The intensity value can be an integer between 0 and 255 (if the node is a leaf) or -1 (if the node is a nonleaf). Your inner class should have a constructor that creates a node with no children and an intensity value of -1. These can be changed once the node is inserted into the tree.
Complete the constructor for the QuadTree class that has one parameter, the name of a text file containing the preorder traversal of the quadtree for an image, like the example shown above. The file will have one integer per line, and each integer will be between -1 and 255, inclusive. You may assume that the input file is the preorder traversal for a valid quadtree. You should read the data from the file and build a quadtree based on the data. (If the file cannot be opened, just output an error message and exit the program.)
Complete the method getNumNodes that returns the number of nodes in the quadtree. Do this as efficiently as possible.
Complete the method getNumLeaves that returns the number of leaves in the quadtree. Do this as efficiently as possible.
Complete the method getImageArray that creates an array of size 256 X 256 and then traverses the quadtree, filling in each cell of the array with its intensity value. Return this array when you're done. Note that as you traverse the quadtree, whenever you hit a leaf, you may need to fill in more than one array cell with the leaf's intensity value. (Think recursively here.)
Once you complete the QuadTree class, run the QuadTreeDisplayer provided for you to load in a sample quadtree file (see below) and make sure you can see the original image. This application passes the quadtree file name to your constructor so you can create the tree, then it calls your getImageArray method to get the image array based on your quadtree and displays the image in a window. Keep testing until you have your QuadTree class working correctly.
Finally, write another class named QuadTreeFileCreator that reads in the name of a text file containing the data for an uncompressed image of size 256 X 256 (one integer per line), and create a new text file containing the data needed for the quadtree representation for the image. If you write this class correctly, you can use the generated quadtree data file with the QuadTreeDisplayer above to view the image. Note: This can be done without creating a quadtree. Hint: Think recursively. See below for a few sample image files that you can convert to quadtree files. [This final step is worth 2 points of the 10 points.]
The quadtree files consist of one integer per line, representing the preorder traversal of a quadtree that represents a 256 X 256 grayscale image consisting of pixel intensities between 0 and 255 (inclusive) for leaf nodes and -1 values for nonleaf nodes. You may assume that the quadtree files are valid.
Here are four sample quadtree files you can use for testing purposes - RIGHT CLICK TO SAVE:
stopsignQT.txt
earthQT.txt
inclineQT.txt
walkingtotheskyQT.txt
The image files consist of one integer per line, representing the raw (uncompressed) data for the image. The integers are in row major order, meaning that the image is scanned row by row. So the first 256 integers represent the first row of the image. The next 256 integers represent the 2nd row of the image, etc. The integers are always in the range 0 to 255 (inclusive). You may assume for this assignment that the image files are valid (although it's easy to check for this if you wish).
Here are four sample image files you can use for testing purposes (these are 3 different images than the ones given in the quadtree files above) - RIGHT CLICK TO SAVE:
smileyface.txt
i376.txt
mascot.txt
ghc.txt
Be sure to document all of the code that you write to explain what you are doing. Use appropriate Java style (indentation, variable names, etc.) to make your code as readable as possible.
Your submitted zip file should include the complete Java program.
See the course website for instructions on how to hand in your program and the policy for late submissions.
Thanks to Rolf Lakaemper for the inspiration and image displayer for this assignment.