# 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);  } }```