quick2.h:
Header file for this version of the quicksort function.
You don't have to write much of this file.
Just copy our version from
~main2270/programs/quick2.h
and add your name and other information at the top.
NOTE: This header file contains only one prototype (for the
quicksort function) and its documentation. It does not have any
class declarations.
quick2.cxx:
This file should contain the implementations of the flexible
quicksort function that is described in the header file.
Make sure that you read all of the discussion below which
describes special aspects of the programming.
makefile:
This is a makefile for the assignment.
The file should contain targets for qtest2.o, qexam2.o,
qtest2 (an executable file) and qexam2 (another
executable file). The source codes qtest2.cxx and qexam2.cxx
are available in the locations listed below. Your makefile should
also include "all" and "clean" options.
Include your name in a comment at the top.
qtest2.cxx:
A simple interactive test program.
qexam2.cxx:
A non-interactive test program that will
be used to grade the correctness of your quicksort function.
void quicksort( void* base, size_t n, size_t bytes, int compar(const void*, const void*) ) Precondition: base is a pointer to the first component of an array with at least n elements. The component type of the array may be any type at all, and the parameter bytes must be the number of bytes in each component of the array. The fourth parameter, compar, must be the name of a function that can compare two elements of the array. The two arguments of compar are pointers to two elements in the array, and the return value of compar indicates which of the two arguments is largest, as follows: -- a negative return value means that the 2nd argument is larger -- a zero return value indicates that the arguments are equal -- a positive return value means that the 1st argument is larger Postcondition: The elements of the array have been rearranged so that they are in order from smallest to largest.This specification includes several new items that you haven't seen before, such as the third parameter (which must be the number of bytes required by one component of an array) and the fourth parameter (where the actual argument must be a function that you write and make available to the quicksort function).
int compare_ints(const void* ptr1, const void* ptr2) { // NOTE: *ptr1 is the first integer, but since ptr1 is a void // pointer, we must use the notation *((int *) ptr1) to refer to // this first integer. Similarly, *((int *) ptr2) refers to the // second integer. This comparison function works by subtracting // the second integer from the first, and returning the result. // This result meets the requirements listed above (for example, // it is negative when the second argument is larger than the // first. return *((int *) ptr1) - *((int *) ptr2); }Notice that
compare_ints
has two parameters that are
declared as void pointers. This means that in the prototype, we
are not going to tell the compiler exactly what ptr1 and ptr2 are
pointing to. But, as the implementor of this function, we know that
ptr1 and ptr2 are actually pointing to integers. In particular:
*((int *) ptr1)
is the integer that ptr1 points to, and
*((int *) ptr2)
is the integer that ptr2 points to.
int my_numbers[4000]; ...code to put 4000 numbers into the array my_numbers... // Now use quicksort. Note that the array my_numbers is the first // argument (but we need to cast it to void* to match the quicksort // prototype). The second argument is the number of elements in the // array. The third argument is the number of bytes in each array // component (obtained by using the predefined sizeof operator). // The fourth arguement is the comparison function listed above. quicksort((void *)my_numbers, 4000, sizeof(int), compare_ints);
#define element(i) (base + ((i)*bytes)) #define assign(x,y) (memcpy((x), (y), bytes)) #define less_than(x,y) (compar((x),(y)) < 0)The macros act sort of like functions, allowing you to easily access and manipulate elements of the array (even though you don't know the data type of that array!) You may use the macros in any place that has access to the quicksort parameters (base, bytes, and compar). Here is what the macros will do:
void *pivot = malloc(bytes);
void *temp = malloc(bytes);
assign(pivot, element(0));
By the way,
you could also use base
instead of
element(0)
.
assign(temp, element(i));
assign(element(i), element(j));
assign(element(j), temp);
size_t random_index = rand( ) % n;
assign(temp, element(0));
assign(element(0), element(random_index));
assign(element(random_index), temp);
free (pivot);
free (temp);
Notice that you are using free instead of delete.
The reason is because the memory was originally allocated with
malloc instead of new.
static void insertion_sort( void* base, size_t n, size_t bytes, int compar(const void*, const void*) ) { void *new_item = malloc(bytes); size_t i; size_t j; for (i = 1; i < n; i++) { // Insert element i into the right place assign(new_item, element(i)); for (j = i; (j > 0) && (less_than(new_item, element(j-1))); j--) assign(element(j), element(j-1)); assign(element(j), new_item); } free (new_item); }
insertion_sort(element(i), n, bytes, compar);
pivot_index
indicates where the pivot element
ended up.
stack1.h
and
stack1.template
:
in your
implementation (instantiating the Stack's item as size_t).