#include

#include

void ascend$($int A$[],$ int N$)\{$

for $($int i $=0$; i $<$ N; i$++)\{$

A$[$i$]=$ i $+1$; $\}$

$\}$

void descend$($int A$[],$ int N$)\{$

for $($int i $=0$; i $<$ N; i$++)\{$

A$[$i$]=$ N $-$ i; $\}$

$\}$

void vee$($int A$[],$ int N$)\{$

int mid $=$ N $/2$;

for $($int i $=0$; i $<$ mid; i$++)\{$

A$[$i$]=$ N $-2*$ i;

$\}$

for $($int i $=$ mid; i $<$ N; i$++)\{$

A$[$i$]=2*($i $-$ mid$)+1$;

$\}$

$\}$

void zigzag$($int A$[],$ int N$)\{$

int left $=0,$ right $=$ N $-1$;

for $($int i $=0$; i $<$ N; i$++)\{$

if $($i $\%2==0)\{$

A$[$i$]=$ N $-$ left$++$;

$\}$ else $\{$

A$[$i$]=$ right $+1-$ N $+$ left$++$;

$\}$

$\}$

$\}$

void random$\_$fill$($int A$[],$ int N$)\{$

for $($int i $=0$; i $<$ N; i$++)\{$

A$[$i$]=$ rand$()\%($N $+1)$;

$\}$

$\}$

long insertSort$($int A$[],$ int N$)\{$

long comparisons $=0$;

for $($int i $=1$; i $<$ N; i$++)\{$

int key $=$ A$[$i$]$;

int j $=$ i $-1$;

while $($j $>=0$ && A$[$j$]>$ key$)\{$

A$[$j $+1]=$ A$[$j$]$; j$--$;

comparisons$++$;

$\}$

A$[$j $+1]=$ key; comparisons$++$;

$\}$

return comparisons;

$\}$

long quickSort$($int A$[],$ int N$)\{$

long comparisons $=0$;

$//$ Helper function

void quickSortHelper$($int A$[],$ int low, int high$)\{$

if $($low $<$ high$)\{$

int pivot $=$ A$[$high$]$;

int i $=($low $-1)$;

for $($int j $=$ low; j $<$ high; j$++)\{$

comparisons$++$;

if $($A$[$j$]<$ pivot$)\{$

i$++$;

int temp $=$ A$[$i$]$; A$[$i$]=$ A$[$j$]$;

A$[$j$]=$ temp;

$\}$

$\}$

int temp $=$ A$[$i $+1]$;

A$[$i $+1]=$ A$[$high$]$;

A$[$high$]=$ temp;

quickSortHelper$($A$,$ low, i$)$;

quickSortHelper$($A$,$ i $+2,$ high$)$;

$\}$

$\}$

quickSortHelper$($A$,0,$ N $-1)$;

return comparisons;

$\}$

long mergeSort$($int A$[],$ int N$)\{$

long comparisons $=0$;

void merge$($int A$[],$ int left, int mid, int right$)\{$

int n$1=$ mid $-$ left $+1$; int n$2=$ right $-$ mid;

int L$[$n$1],$ R$[$n$2]$;

for $($int i $=0$; i $<$ n$1$; i$++)$ L$[$i$]=$ A$[$left $+$ i$]$;

for $($int j $=0$; j $<$ n$2$; j$++)$ R$[$j$]=$ A$[$mid $+1+$ j$]$;

int i $=0,$ j $=0,$ k $=$ left;

while $($i $<$ n$1$ && j $<$ n$2)\{$

comparisons$++$;

if $($L$[$i$]<=$ R$[$j$])\{$

A$[$k$++]=$ L$[$i$++]$;

$\}$ else $\{$

A$[$k$++]=$ R$[$j$++]$;

$\}$

$\}$

while $($i $<$ n$1)$ A$[$k$++]=$ L$[$i$++]$;

while $($j $<$ n$2)$ A$[$k$++]=$ R$[$j$++]$;

$\}$

void mergeSortHelper$($int A$[],$ int left, int right$)\{$

if $($left $<$ right$)\{$

int mid $=$ left $+($right $-$ left$)/2$;

mergeSortHelper$($A$,$ left, mid$)$;

mergeSortHelper$($A$,$ mid $+1,$ right$)$;

merge$($A$,$ left, mid, right$)$;

$\}$

$\}$

mergeSortHelper$($A$,0,$ N $-1)$;

return comparisons;

$\}$

void runSorting$($char$*$ filename$)\{$

FILE$*$ file $=$ fopen$($filename$,"$r$")$;

if $(!$file$)\{$

printf$("$Failed to open file.

$")$;

return;

$\}$

int R;

fscanf$($file$,"\%$d$",$ &R$)$;

for $($int i $=0$; i $<$ R; i$++)\{$

int N;

char inputType, sortType;

fscanf$($file$,"\%$d $\%$c $\%$c$",$ &N$,$ &inputType, &sortType$)$;

int A$[$N$]$;

switch $($inputType$)\{$

case $\text{'}$A$\text{'}$: ascend$($A$,$ N$)$;

break;

case $\text{'}$D$\text{'}$: descend$($A$,$ N$)$; break;

case $\text{'}$V$\text{'}$: vee$($A$,$ N$)$;

break;

case $\text{'}$Z$\text{'}$: zigzag$($A$,$ N$)$;

break;

case $\text{'}$R$\text{'}$: random$\_$fill$($A$,$ N$)$; break;

$\}$

long comparisons $=0$;

switch $($sortType$)\{$

case $\text{'}$I$\text{'}$: comparisons $=$ insertSort$($A$,$ N$)$;

break;

case $\text{'}$Q$\text{'}$: comparisons $=$ quickSort$($A$,$ N$)$;

break;

case $\text{'}$M$\text{'}$: comparisons $=$ mergeSort$($A$,$ N$)$;

break;

$\}$

printf$("\%$d $\%$c $\%$c $\%$ld

$",$ N$,$ inputType, sortType, comparisons$)$;

$\}$

fclose$($file$)$;

$\}$

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

if $($argc $!=2)\{$

printf$("$Usage: $\%$s

$",$ argv$[0])$;

return $1$;

$\}$

runSorting$($argv$[1])$;

return $0$;

$\}$

WHAT WOULD THE CONTROL FILE LOOK LIKE?