Work with Binary Data, File IO and Sorting Techniques in Java Assignment Solution

Instructions

Objective

Write a java homework to work with binary data, file IO and sorting techniques.

Requirements and Specifications

Source Code

NWAY MERGE

package submission; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; public class NWayMerge { private final short[][] individuallySortedSamples; private final boolean sortX; private final int totalNumSamples; NWayMerge(short[][] individuallySortedSamples, boolean sortX) { this.individuallySortedSamples = individuallySortedSamples; this.sortX = sortX; int totalNumSamples = 0; for (int i=0; i totalNumSamples += individuallySortedSamples[i].length; } // every sample consists of two values this.totalNumSamples = totalNumSamples/2; } abstract class ASamplePicker { // current position in each of the input arrays protected int[] positions = new int[individuallySortedSamples.length]; // returns the index of the partition with the smallest sample at the current position abstract short proposeNextPartition(); // get the current sample position and advance it by one int getNextSamplePositionFromPartition(short partition) { return positions[partition]++; } } class SamplePickerSimple extends ASamplePicker { short proposeNextPartition() { short minPart = -1; short value = Short.MAX_VALUE; for(short i = 0; i < individuallySortedSamples.length; i++) { if (individuallySortedSamples[i].length <= 2*positions[i]) { continue; } if (individuallySortedSamples[i][2*positions[i] + (sortX ? 0 : 1)] < value) { value = individuallySortedSamples[i][2*positions[i] + (sortX ? 0 : 1)]; minPart = i; } } return minPart; } } class SamplePickerHeap extends ASamplePicker { private short[] heap; private int heapSize = 0; SamplePickerHeap() { heap = new short[individuallySortedSamples.length]; List shorts = new ArrayList<>(); for (short i = 0; i shorts.add(i); } shorts.sort(Comparator.comparingInt(o -> individuallySortedSamples[o][sortX ? 0 : 1])); for(short i = 0; i heap[i] = shorts.get(i); heapSize++; } } void percolateHeap(int i) { int child = 2*i+1; if (child < heapSize) { if (child + 1 < heapSize && individuallySortedSamples[heap[child]][2*positions[heap[child]] + (sortX ? 0 : 1)] > individuallySortedSamples[heap[child+1]][2*positions[heap[child+1]] + (sortX ? 0 : 1)]) { child++; } if (individuallySortedSamples[heap[i]][2*positions[heap[i]] + (sortX ? 0 : 1)] > individuallySortedSamples[heap[child]][2*positions[heap[child]] + (sortX ? 0 : 1)]) { short sw = heap[i]; heap[i] = heap[child]; heap[child] = sw; percolateHeap(child); } } } short proposeNextPartition() { short minPart = heap[0]; if (2*positions[minPart] + 2 >= individuallySortedSamples[minPart].length) { heap[0] = heap[heapSize-1]; heapSize--; } positions[minPart]++; percolateHeap(0); positions[minPart]--; return minPart; } } private short[] merge(ASamplePicker samplePicker) { short[] result = new short[2*totalNumSamples]; for (int i = 0; i short j = samplePicker.proposeNextPartition(); int pos = samplePicker.getNextSamplePositionFromPartition(j); result[2*i] = individuallySortedSamples[j][2*pos]; result[2*i+1] = individuallySortedSamples[j][2*pos + 1]; } return result; } short[] simpleMerge() { return merge(new SamplePickerSimple()); } short[] heapMerge() { return merge(new SamplePickerHeap()); } }

QUICK SORT

package submission; import java.util.Random; public class QuickSort { static int partition(short[] samples, int begin, int end, short pivot, boolean sortX) { // TODO: partition the sample data either by the x or the y coordinates based on the pivot value // NOTE: all samples consist of two values and the begin and end indices are given with respect to the sample, not the array position int i = begin-1; for (int j = begin; j <= end; j++) { if (sortX && samples[2*j] < pivot || !sortX && samples[2*j + 1] < pivot) { i++; swap(samples, i, j); } } return i+1; // return -1; // FIXME: replace this with something useful } private static void swap(short[] samples, int a, int b) { // TODO: swap the samples stored at indices a and b // NOTE: all samples consist of two values and the a and b indices are given with respect to the sample, not the array position short s1 = samples[2*a]; short s2 = samples[2*a+1]; samples[2*a] = samples[2*b]; samples[2*a+1] = samples[2*b+1]; samples[2*b] = s1; samples[2*b+1] = s2; } static void sort(short[] samples, int begin, int end, boolean sortX) { if (end <= begin) return; final int middle = partition(samples, begin, end-1, samples[2*end+(sortX ? 0 : 1)], sortX); swap(samples, middle, end); sort(samples, begin, middle-1, sortX); sort(samples, middle+1, end, sortX); } }