Write the SWAP and ORDER macros so that the second version of sort in the exampl
ID: 3587452 • Letter: W
Question
Write the SWAP and ORDER macros so that the second version of sort in the example program works correctly.
Example Program:
// insertion sort w macros
/*
insertion sort
bad:
inefficient for large arrays
good:
simple to write
efficient for small arrays
conducive to programming tricks to speed up performance
stable
adaptive (fast if almost sorted)
don't need extra space for copy of array
online (can sort items as they come in)
pseudocode:
for( j in [1, els)
for(i = j; a[i-1] & a[i] gotta be switched?; i--)
a[i-1] <=> a[i]
*/
#include <stdio.h>
#include <stdlib.h> // rand() gives int in [0, 32768)
#include <string.h> // strlen gives # chars before null char
#define STR(s) #s
#define XSTR(s) STR(s)
#define PASTE(x,y) x##y
#define XPASTE(x,y) PASTE(x,y)
#define ELS 6
void randomize(double a[], unsigned els);
void show(const double a[], unsigned els);
void sort(double a[], unsigned els);
#define SHOW_H(type, ty) /*
*/ void XPASTE(show, ty)(const type a[], unsigned els) /**/
#define SHOW_DEF(type, ty, f) /*
*/ SHOW_H(type, ty){ /*
*/ for(unsigned i = 0; i < els; i++) /*
*/ printf(" %" XSTR(f), a[i]); /*
*/ printf(" "); /*
*/ } /**/
// assuming that x & y have type double, swap their values
// the SWAPDOUBLE macro should expand into a single C++ statement
// so that:
// SWAPDOUBLE can be used normally in if's and loops
// SWAPDOUBLE's temporary variable's scope doesn't pollute the
// surrounding code
#define SWAPDOUBLE(x, y) /*
*/ double temp = x; /*
*/ x = y; /*
*/ y = temp; /**/
// Assume that type names a C type (e.g. double) and that x and y are
// lvalues of that type (so your temporary variable should be of
// that type also).
// SWAP's job is to use the temporary to swap the values of x & y.
// SWAP should expand into a single statement, and the scope of any
// temporaries should be confined to that statement.
#define SWAP(type, x, y) ...
// Assume that a is an array of doubles, i is an index into that array.
// ORDER's job is to make sure that the [i-1] element of the array and
// the [i] element of the array are in non-decreasing order - if
// they're not then call your SWAP macro to swap them.
// Like SWAP, ORDER should expand into a single C statement, and any
// temporaries should have their scope confined to the macro.
#define ORDER(a, i) ...
SHOW_H(double, Dbl);
SHOW_H(int, Int);
SHOW_H(char, Char);
int main(){
/*
double x0 = 0, x1 = 1;
for(unsigned i = 3; i--; )
SWAPDOUBLE(x0, x1)
int temp = 6; printf("%i ", temp);
/**/
double a[ELS];
randomize(a, ELS);
show(a, ELS);
sort(a, ELS);
showDbl(a, ELS);
int b[] = {1, 2, 3, 4};
const unsigned bEls = sizeof(b) / sizeof(b[0]);
showInt(b, bEls);
char c[] = "supercalifragilisticexpialidocious";
showChar(c, strlen(c));
} // main
void randomize(double a[], unsigned els){
for(unsigned i = 0; i < els; i++)
a[i] = rand();
}
void show(const double a[], unsigned els){
for(unsigned i = 0; i < els; i++)
printf(" %f", a[i]);
printf(" ");
}
/**/
void sort(double a[], unsigned els){
for(unsigned j = 1; j < els; j++)
for(unsigned i = j; i > 0 && a[i-1] > a[i]; i--){
double t = a[i-1];
a[i-1] = a[i];
a[i] = t;
}
}
/*
void sort(double a[], unsigned els){
for(unsigned j = 1; j < els; j++)
for(unsigned i = j; i > 0 && a[i-1] > a[i]; i--)
ORDER(a, 1)
}
/**/
SHOW_DEF(double, Dbl, f)
SHOW_DEF(int, Int, i)
SHOW_DEF(char, Char, c)
Explanation / Answer
#define SWAP(type,x, y) {type temp = x;x = y;y = temp;}
#define ORDER(a,i) (a[i]<a[i-1])?(SWAP(double,a[i],a[i-1])):1
Here are the SWAP and ORDER macros and yes, they work correctly for single line for loops and temp variable's scope is also limited to SWAP only.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.