Objectives
- Determine the sorting algorithms optimal for a specific number of elements.
- Design and implement a minHeap algorithm to sort an array of numbers.
- Get in the habit of dividing larger projects into smaller parts.
- Use EGit features such as commit and clone to write and read from your repository.
Background
Assume we are given the task of sorting a large amount of data stored in files. However, our data is too large to fit in memory. So, we cannot directly take advantage of the nifty sorting algorithms we learned in class. In this project your job is to sort multiple files, whilst requiring minimum storage and run time.
You’ll read the plain text files that contain unsorted numbers. Then, sort the data by dividing them into multiple chunks, where the size of each chunk is limited by the size of memory we are simulating. Finally, write the result in an output file.
class SimulateChunks
Reads the numbers from file and puts them in an array. Then splits the array according to the given memory size and adds the chunks to the chunks array.
Defines the static splitFileIntoArrayChunks() method to have as argument:
- a final int for the simulated memory size,
- a String object for the name of the input file,
- an ArrayList of Integer[] objects for the array list that holds chunks of arrays of integers.
class BasicSorter
Sorts an individual chunk in place using the static sortChunk() method which receives an Integer[] object as argument. The sorting algorithm should depend on the number of elements.
NOTE: In place means that the sorted result is stored in the argument “chunk”.
class SortFileData
An instance of class SortFileData sorts the files in two phases and outputs the result of all sorted numbers.
The two phases are:
- void sortChunk(Integer [] array) Sorts each individual chunk.
To determine the sorting algorithm to use, first look at the chunk size. Then based on the number of elements choose the sorting algorithm in the modules that is optimal for the given size. - Uses min heap sorting techniques to sort all chunks with respect to each other.
- Sort each array by using minHeap via the method mergeSortedArrays() defined in class MinHeapArrayMerger.
Suggestion: Take advantage of the logic from our heap sorting algorithm we studied in modules.
class MinHeapArrayMerger
- static void mergeSortedArrays(Integer[] inputChunks, HeapTuple[] minHeap, String outfile) Uses the minHeap technique to sort the various
chunks with respect to each other and writes the output to a file called result_using_min_heap.txt
Note: In class MinHeapArrayMerger we are NOT explicitly calling the FHsort.heapSort() method.
Use the array of HeapTuple objects called minHeap to hold the current minimums.
NOTE: Assume the number of chunks can be greater than available MEM_SIZE. In this case the challenge is keep track of which array you grabbed the current minimum in this pass. Remember, it doesn’t matter how many chunks we have, our only goal is to run through all the chunks until MEM_SIZE many minimums are grabbed. Write these out to a file. Then, we reset our array holding the mins and restart for the next pass.
In your RUN.txt file show a sample number of iterations.
The format of the inputs files “numbers01.txt”, “numbers02.txt”, etc in CSV shown in the example below:
143,685,163,90,413,918,940,829,397
Output of example:
90,143,163,397,413,685,829,918,940,
In total you will have two output files:
- Files produced by main called “result_using_bin_heap.txt”. The output should be a comma delimited list of all sorted numbers with respect to each other. For example: If you had four input files with the following:
numbers01.txt file:
5,3,4
numbers02.txt file:
4,2,3,2
numbers03.txt file:
1,9,5
numbers04.txt file:
4,5,1,7
Then, for example result_using_min_heap.txt should look as follows:
1,1,2,2,3,3,4,4,4,5,5,5,7,9
NOTE: Do NOT edit the output file result_using_bin_heap.txt.
- File RUN.txt where you will copy and paste the output of your program.
FAQ
FAQ: Should our MinHeapArrayMerger class extend FHbinHeap?
No, MinHeapArrayMerger class should not extend FHbinHeap class. The approach in FHbinHeap uses extra memory, which is not necessary.
Take a look at FHsort class heapSort() method from the modules.
FAQ: Can I have instance fields in my MinHeapArrayMerger class?
No, a static method cannot refer to an instance field (i.e. a nonstatic variable of the class). Your implementation of static mergeSortedArrays() method should not rely on any instance fields. In the same respect, design your implementation such that it does not rely on any static fields as well.
FAQ: Will our implementation be evaluated based on the algorithm efficiency or just the program output? Let us say the input files are much bigger than the ones we have for the assignment.
No, Your implementation will not be graded based on the runtime of your algorithm.
However, your implementation should be taking advantage of the logNtime needed to remove the min value and run within a reasonable amount of time. For example, for a couple of thousand entries (small in comparison with algo’s bigoh), it should complete within a few miliseconds.