You will write a simple program for arranging the records in a file by increasing order of the keys for each

record. This program should be invoked as follows $($assuming that you are using Linux or mac and the

program is compiled into an executable. If you are using python this will be a bit different and it will still

be acceptable$)$:

$./$arrange $-$i inputfile $-$o outputfile

The above line means the users typed in the name of the program $``$arrange$\text{'}\text{'}$ and gave it two inputs: an

input file to work on called $$inputfile$$ and an output file to put the results into called $$outputfile$.$

I provide you with an input file called $``$input$\text{'}\text{'}$ and it has $100$ rows. The file is binary with each row having

$100$ bytes. The first four bytes are corresponding to a key and the last $96$ bytes are corresponding to the

value of the record. Thus, the input file contains a series of $100-$byte records, the first four bytes of which

are an unsigned $32$ bit integer key, and the remaining $96$ bytes of which are integers that form the rest of

the record.

Your goal: to build a program called $``$arrange$\text{'}\text{'}$ that takes in this file and arranges it based on the $4-$byte

key in increasing order using insertion sort. The remainder of the record should of course be kept with

the same key.

The output should be written to the specified output file. Note that the input file will be in binary, but the

corresponding output file should be in ascii. In order to read the input file and see its contents in ascii, I

provide you with a program called $``$dump$.$c$\text{'}\text{'}.$ In order to compile dump.c you would do $($this is assuming

you are running on linux or mac$)$:

gcc $-$o dmp dump.c

Now you should have an executable called $``$dmp$\text{'}\text{'}$ in your current directory and you can use it to read the

binary input file as follows:

$./$dmp $-$i input

When you do this the contents of the binary file are displayed to you in a nice, formatted manner on the

terminal.

Programming languages and formatting

You are free to use either C$,$ C$++$ or Python and should implement the algorithms yourself and NOT use

any library which provides an implementation of the algorithm.

Submission Guidelines

Please mention the programming language and version and it SHOULD WORK ON the CS servers. Your

submission must have the following:

$$ A short report documenting the algorithm you used. This is a very crucial step. Can you compute

the running time in Big$-$Oh notation for your algorithm.

A README file that describes how the code can be compiled and run. Also list any external

dependencies that need to be satisfied for compiling and running the code. If your code fails to compile

YOU GET A ZERO.

Your submission should have a single point of entry for running the code, like a main$()$ method in C or its

equivalent in any other language

"sort.h$"$:

#ifndef $\_\_$sort$\_$h$\_\_$

#define $\_\_$sort$\_$h$\_\_$

$//$ DO NOT EDIT THIS FILE

#define NUMRECS $(24)$

typedef struct $\_\_$rec$\_$t $\{$

unsigned int key;

unsigned int record$[$NUMRECS$]$;

$\}$ rec$\_$t;

#endif $//\_\_$sort$\_$h$\_\_$

"dump.c$"$:

#include

#include

#include

#include

#include

#include

#include

#include "sort.h$"$

void

usage$($char $*$prog$)$

$\{$

fprintf$($stderr$,$ "usage: $\%$s $<-$i file$>$

$",$ prog$)$;

exit$(1)$;

$\}$

int

main$($int argc, char $*$argv$[])$

$\{$

$//$ arguments

char $*$inFile $="/$no$/$such$/$file$"$;

$//$ input params

int c;

opterr $=0$;

while $(($c $=$ getopt$($argc$,$ argv, $"$i:$"))!=-1)\{$

switch $($c$)\{$

case $\text{'}$i$\text{'}$:

inFile $=$ strdup$($optarg$)$;

break;

default:

usage$($argv$[0])$;

$\}$

$\}$

$//$ open and create output file

int fd $=$ open$($inFile$,$ O$\_$RDONLY$)$;

if $($fd $<0)\{$

perror$("$open$")$;

exit$(1)$;

$\}$

rec$\_$t r;

while $(1)\{$

int rc;

rc $=$ read$($fd$,$ &r$,$ sizeof$($rec$\_$t$))$;

if $($rc $==0)//0$ indicates EOF

break;

if $($rc $<0)\{$

perror$("$read$")$;

exit$(1)$;

$\}$

printf$("$key: $\%$u rec:", r$.$key$)$;

int j;

for $($j $=0$; j $<$ NUMRECS; j$++)$

printf$("\%$u $",$ r$.$record$[$j$])$;

printf$("$

$")$;

$\}$

$($void$)$ close$($fd$)$;

return $0$;

$\}$