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

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());

 }

}

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);

 }

}