CSC322S2025Sorting < CenterForComputing

Tags: view all tags
---+CSC 322 Lab 3
---++Objectives
   1. Improve Linux skills
   1. Code merge sort, heap sort, and external sort
   1. Study the time implications of the sort

---++Problem
   Write C code to:
   * Generate a very large list of numbers stored in a binary file.
   * Sort the data using an external sort and either the heap sort or merge
   * Study the implications
<br>
Note: For this lab, you are required to do all work (except the writeup) on your virtual linux machine.  Because there are no points and just using fix arrays, the c code will be much easier.  Time to work on your Linux skils!
---++Details
   1. The program is to allow for three options (based on the command line arguments:
      * <b>-g filename</b> : this option will generate the data and store it in a binary file specified by the name
      * <b>-sh filein fileout</b> : this option will sort the data in filein (binary file of data) via an external sort and heap sort and save it in fileout
      * <b>-sm filein fileout</b> : this option will sort the data in filein (binary file of data) via an external sort and merge sort and save it in fileout
   1. You may use constants to indicate the size of the buffers and how many buffers are in the file
   1. You are only allowed 5 buffers for the data in your program.  All IO must be done via the buffers.  If you wish, you can combine the buffers.  This is easy to do in C.  Doing so will probably demonstrate the difference from the heap sort and the merge sort.
   1. Track the amount of time sorting/processing the buffers vs. the amount of time doing IO
   1. Guesstimate how long this lab will take and record it.
   1. Create a Software Development Report
      a. include a discussion on the fragility of your program in the security report
      a. Lessons learned will be important.  This also needs a discussion of the work.  It should deal with Big O, time sorting vs. time doing IO, the difference between merge sort and heap sort
   1. Create a tar ball with all .c, .h, makefile, and SDR and submit it via Canvas
---++Challenges
   * Study the difference between using all buffers for reading and "merging" during all the passes (except the first) and writing one integer at a time vs saving one buffer for output and writing it all at once.  Also do a study to determine if the size of the buffer (related to block size of the external storage) matters.
   * implement any/all of the future improvements found in the README file
Topic revision: r1 - 2025-02-02 - CathyBareiss