Instructions
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<individuallySortedSamples.length; ++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<Short> shorts = new ArrayList<>();
for (short i = 0; i<individuallySortedSamples.length; i++) {
shorts.add(i);
}
shorts.sort(Comparator.comparingInt(o -> individuallySortedSamples[o][sortX ? 0 : 1]));
for(short i = 0; i<individuallySortedSamples.length; 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<totalNumSamples; 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);
}
}