(15 marks) Write a C function named partition following the quick sort algorithm for partition discussed in class (Lecture 20) and submit it in the file named a6q4.c

The function must work with the program a6q4-main.c which is available at the assign- ment web page and in the ~prof2132/public/ directory. You can notice that the function must work with pointers. The pivot must be chosen as the middle element, as shows in class, however, the code for getting this middle element is somewhat different than when using arrays and indices.

If you correctly implemented the function, then you can compile the program using the command:

gcc -o a6q4-main a6q4-main.c a6q4.c 

and test it on the given test file with:

./a6q4-main < a6q4-test1.in > a6q4-test1.new The produced output should be the same as the given file a6q4-test1.out.

4

If you want to test further that partition is done exactly as expected you can use another file that produced a more detailed trace (a6q4-trace.c) using the command: gcc -o a6q4-trace a6q4-trace.c a6q4.c and test it on the given test file with:

./a6q4-trace < a6q4-test1.in > a6q4-test1-trace.new The produced output should be the same as the given file a6q4-test1-trace.out.

All given files can be found at the assignment web page or in the directory ~prof2132/public on bluenose, and they are given here as well:

The file a6q4-main.c: /* Program: a6q4-main.c Author: Vlado Keselj */

#include  

void quicksort(int *lo, int *hi); int* partition(int *lo, int *hi); 

int main() { int n; 

 scanf("%d", &n); if (n > 0) { 

 int a[n], i; for (i=0; i 
 scanf("%d", &a[i]); 
 
 quicksort(a, a+n-1); 
 
 for (i=0; i 
return 0; }
 
 else return 1; 
 
}
 
void quicksort(int *lo, int *hi) { if (lo < hi) { 
 
 int *p = partition(lo, hi); quicksort(lo, p); quicksort(p+1, hi); 
 
}
 
5
 
}
 
The file a6q4-test1.in:
 
10 -5 10 20 -1 0 -1 56 -25 10 10 
 
The file a6q4-test1.out:
 
-25 -5 -1 -1 0 10 10 10 20 56 
 
The file a6q4-trace.c: /* Program: a6q4-trace.c Author: Vlado Keselj */
 
#include  
 
void quicksort(int *lo, int *hi); int* partition(int *lo, int *hi); 
 
int main() { int n; 
 
 scanf("%d", &n); if (n > 0) { 
 
 int a[n], i; for (i=0; i 
 scanf("%d", &a[i]); 
 
 quicksort(a, a+n-1); 
 
 for (i=0; i 
6
 
return 0; }
 
 else return 1; 
 
}
 
void quicksort(int *lo, int *hi) { if (lo < hi) { 
 
int *p, *q;
 
 printf("PARTITION IN:"); for(q=lo; q<=hi; q++) printf(" %2d", *q); 
 
 putchar( ); p = partition(lo, hi); 
 
 printf("PARTITION OUT:"); for(q=lo; q<=hi; q++) 
 
 printf("%c%2d", q==p ? * :  , *q); putchar( ); 
 
 quicksort(lo, p); 
 
 quicksort(p+1, hi); } 
 
}
 
The file a6q4-test1-trace.out:
 
PARTITION IN:-51020-1 0-156-251010 PARTITION OUT: -5 -25 -1 -1* 0 20 56 10 10 10 PARTITION IN: -5 -25 -1 -1 0 PARTITION OUT: -5 -25*-1 -1 0
 
PARTITION IN: -5 -25 -1 PARTITION OUT:*-25 -5 -1 PARTITION IN: -5 -1 PARTITION OUT:*-5 -1 PARTITION IN: -1 0 PARTITION OUT:*-1 0 PARTITION IN: 20 56 10 10 10 PARTITION OUT: 10 10*10 56 20 PARTITION IN: 10 10 10 
 
7
 
PARTITION OUT: 10*10 10 PARTITION IN: 10 10 PARTITION OUT:*10 10 PARTITION IN: 56 20 PARTITION OUT:*20 56 -25 
 
-5 -1 -1 0 10 10 10 20 56