Homework #3

Car.c

#include <stdlib.h>
#include <stdio.h>
#include "sort.h"

#define MAX_STRING_LENGTH 8

typedef struct Car_
{
	char make[MAX_STRING_LENGTH];
	char model[MAX_STRING_LENGTH];
	int  mpg; /* Miles per gallon */
} Car;

/*
 * Implement a function called compareCarsByMakeThenModel that can be passed as
 * an argument to the compare parameter of the qksort function from the book.
 * compareCarsByMakeThenModel should return a value that will cause qksort to sort an
 * array of cars in ascending order (from smallest to largest) by make and, when two cars have the
 * same make, in ascending order by model.
 */
int compareCarsByMakeThenModel(const void *key1, const void *key2)
{
	const Car* car1 = key1;
	const Car* car2 = key2;

	return strcmp(car1->make, car2->make) ?: strcmp(car1->model, car2->model);
}

/*
 * Implement a function called compareCarsByDescendingMPG that can be passed as
 * an argument to the compare parameter of the qksort function from the book.
 * compareCarsByDescendingMPG should return a value that will cause qksort to sort an array
 * of cars in descending order (from largest to smallest) by mpg.
 */
int compareCarsByDescendingMPG(const void *key1, const void *key2)
{
	const Car* car1 = key1;
	const Car* car2 = key2;

	return car2->mpg - car1->mpg;
}

/*
 * Implement a function called compareCarsByMakeThenDescendingMPG that can be
 * passed as an argument to the compare parameter of the qksort function from the book.
 * compareCarsByMakeThenDescendingMPG should return a value that will cause qksort to
 * sort an array of cars in ascending order by make and, when two cars have the same make, in
 * descending order by mpg.
 */
int compareCarsByMakeThenDescendingMPG(const void *key1, const void *key2)
{
	const Car* car1 = key1;
	const Car* car2 = key2;

	return strcmp(car1->make, car2->make) ?: compareCarsByDescendingMPG(car1, car2);
}

int print_car(const Car* car)
{
        static char buffer[MAX_STRING_LENGTH + 1];
        int count;

        sprintf(buffer, "%s,", car->make);
        count = printf("{%*s ", -MAX_STRING_LENGTH, buffer);
        sprintf(buffer, "%s,", car->model);
        return count + printf("%*s %i}", -MAX_STRING_LENGTH, buffer, car->mpg);
}

int print_cars(const Car* cars, const size_t count)
{
        int i;

 	for (i = 0; i < count; ++i)
 	{
 		print_car(&cars[i]);
 		printf("\n");
 	}
	return count;
}

int main(int argc, const char *argv[])
{
	Car cars[] =
	{
		{ "Toyota",	"Camry",	33 },
		{ "Ford",	"Focus",	40 },
		{ "Honda",	"Accord",	34 },
		{ "Ford",	"Mustang",	31 },
		{ "Honda",	"Civic",	39 },
		{ "Toyota",	"Prius",	48 },
		{ "Honda",	"Fit",  	35 },
		{ "Toyota",	"Corolla",	35 },
		{ "Ford",	"Taurus",	28 }
	};

	const size_t count = sizeof(cars) / sizeof(*cars);

        /* 1. Output (displaying make, model, and MPG) the cars in original unsorted order. */
	print_cars(cars, count);
	printf("\n");

	/* 2. Output the cars sorted (using qksort from the book) by make then model. */
	qksort(cars, sizeof(cars), sizeof(*cars), 0, count - 1, compareCarsByMakeThenModel);
	print_cars(cars, count);
	printf("\n");

	/* 3. Output the cars sorted (using qksort from the book) by descending MPG. */
	qksort(cars, sizeof(cars), sizeof(*cars), 0, count - 1, compareCarsByDescendingMPG);
	print_cars(cars, count);
	printf("\n");

	/* 4. Output the cars sorted (using qksort from the book) by make then descending MPG. */
	qksort(cars, sizeof(cars), sizeof(*cars), 0, count - 1, compareCarsByMakeThenDescendingMPG);
	print_cars(cars, count);
	printf("\n");

	return EXIT_SUCCESS;
}

issort.c

/*
 * issort.c
 */
#include <stdlib.h>
#include <string.h>

#include "sort.h"

int issort(void *data, int size, int esize,
        int (*compare)(const void *key1, const void *key2))
{
    char *a = data;
    void *key;
    int   i,
          j;

    /* Allocate storage for the key element. */
    if ((key = (char *)malloc(esize)) == NULL)
        return -1;

    /* Repeatedly insert a key element among the sorted elements. */
    for (j = 1; j < size; j++) {
        memcpy(key, &a[j * esize], esize);
        i = j - 1;

        /* Determine the position at which to insert the key element. */
        while (i >= 0 && compare(&a[i * esize], key) > 0) {
            memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
            i--;
        }

        memcpy(&a[(i + 1) * esize], key, esize);
    }

    /* Free the storage allocated for sorting. */
    free(key);

    return 0;
}

qksort.c

/*
 * qksort.c
 */
#include <stdlib.h>
#include <string.h>
#include "sort.h"

static int compare_int(const void *int1, const void *int2)
{
    /* Compare two integers (used during median-of-three partitioning). */
    if (*(const int *)int1 > *(const int *)int2)
        return 1;
    else if (*(const int *)int1 < *(const int *)int2)
        return -1;
    else
        return 0;
}
static int partition(void *data, int esize, int i, int k,
        int (*compare)(const void *key1, const void *key2))
{
    char *a = data;
    void *pval,
         *temp;
    int r[3];

    /* Allocate storage for the partition value and swapping. */
    if ((pval = malloc(esize)) == NULL)
        return -1;
    if ((temp = malloc(esize)) == NULL) {
        free(pval);
        return -1;
    }
    /* Use the median-of-three method to find the partition value. */
    r[0] = (rand() % (k - i + 1)) + i;  /* Get random index in range [i, k] */
    r[1] = (rand() % (k - i + 1)) + i;  /* "" */
    r[2] = (rand() % (k - i + 1)) + i;  /* "" */
    /*
     * BUG:  The next two lines are selecting the median INDEX from the three
     * randomly generated indices.  These lines should instead be selecting
     * the median VALUE from the values at the three randomly generated
     * indices.  This bug effectively causes a random value to be selected
     * for the pivot rather than the median-of-three random values.  This means
     * quicksort will not be virtually guaranteed to perform in average case
     * O(nlgn) and instead may perform in worst case O(n^2).
     */
    issort(r, 3, sizeof(int), compare_int); /* Sort random indices */
    memcpy(pval, &a[r[1] * esize], esize);  /* Set pivot = value at mid index */

    /* Create two partitions around the partition value. */
    i--;
    k++;
    while (1) {
        /* Move left until an element is found in the wrong partition. */
        do {
            k--;
        } while (compare(&a[k * esize], pval) > 0);

        /* Move right until an element is found in the wrong partition. */
        do {
            i++;
        } while (compare(&a[i * esize], pval) < 0);
        if (i >= k) {
            /* Stop partitioning when the left and right counters cross. */
            break;
        }
        else {
            /* Swap the elements now under the left and right counters. */
            memcpy(temp, &a[i * esize], esize);
            memcpy(&a[i * esize], &a[k * esize], esize);
            memcpy(&a[k * esize], temp, esize);
        }
    }

    /* Free the storage allocated for partitioning. */
    free(pval);
    free(temp);
    /* Return the position dividing the two partitions. */
    return k;
}

int qksort(void *data, int size, int esize, int i, int k,
        int (*compare)(const void *key1, const void *key2))
{
    int j;
    /* Stop the recursion when it is not possible to partition further. */
    if (i < k) {
        /* Determine where to partition the elements. */
        if ((j = partition(data, esize, i, k, compare)) < 0)
            return -1;
        /* Recursively sort the left partition. */
        if (qksort(data, size, esize, i, j, compare) < 0)
            return -1;

        /* Recursively sort the right partition. */
        if (qksort(data, size, esize, j + 1, k, compare) < 0)
            return -1;
    }
    return 0;
}

sort.h

/*
 * sort.h
 */
#ifndef SORT_H
#define SORT_H

/*
 * Public interface
 */
int issort(void *data, int size, int esize, int (*compare)(const void *key1,
   const void *key2));

int qksort(void *data, int size, int esize, int i, int k, int (*compare)
   (const void *key1, const void *key2));

int mgsort(void *data, int size, int esize, int i, int k, int (*compare)
   (const void *key1, const void *key2));

int ctsort(int *data, int size, int k);

int rxsort(int *data, int size, int p, int k);

#endif

{Toyota,  Camry,   33}
{Ford,    Focus,   40}
{Honda,   Accord,  34}
{Ford,    Mustang, 31}
{Honda,   Civic,   39}
{Toyota,  Prius,   48}
{Honda,   Fit,     35}
{Toyota,  Corolla, 35}
{Ford,    Taurus,  28}

{Ford,    Focus,   40}
{Ford,    Mustang, 31}
{Ford,    Taurus,  28}
{Honda,   Accord,  34}
{Honda,   Civic,   39}
{Honda,   Fit,     35}
{Toyota,  Camry,   33}
{Toyota,  Corolla, 35}
{Toyota,  Prius,   48}

{Toyota,  Prius,   48}
{Ford,    Focus,   40}
{Honda,   Civic,   39}
{Honda,   Fit,     35}
{Toyota,  Corolla, 35}
{Honda,   Accord,  34}
{Toyota,  Camry,   33}
{Ford,    Mustang, 31}
{Ford,    Taurus,  28}

{Ford,    Focus,   40}
{Ford,    Mustang, 31}
{Ford,    Taurus,  28}
{Honda,   Civic,   39}
{Honda,   Fit,     35}
{Honda,   Accord,  34}
{Toyota,  Prius,   48}
{Toyota,  Corolla, 35}
{Toyota,  Camry,   33}