Sorts

mergeSort.c

// mergeSort.c
// Based on Sedgwick's code

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int Item;

// prototypes
void merge(int items[], int left, int mid, int right);
void mergeSort(Item items[], int left, int right);


int main() {

    printf("hello, world!\n");

    return 0;
}

void mergeSort(Item items[], int left, int right) {
    // base case
    if (right <= left) { return; }

    // calculate floored mid
    int mid = (left + right) / 2;

    // recurse on the left half
    mergeSort(items, left, mid);

    // recurse on the right half
    mergeSort(items, mid + 1, right);

    // merge two sorted halves
    merge(items, left, mid, right);
}

void merge(int items[], int left, int mid, int right) {

    // allocate memory for a temporary array to store the merged result
    int numItems = right - left + 1;
    int *temp = malloc(numItems * sizeof(int));
    assert(temp != NULL);

    // initialise counters
    int i = left;
    int j = mid + 1;
    int k = 0;

    // perform the merge of left and right partitions
    while (i <= mid && j <= right) {
        if (items[i] < items[j]) {
            temp[k++] = items[i++];
        } else {
            temp[k++] = items[j++];
        }
    }

    // add on the rest if either partition has items left over
    while (i <= mid) { temp[k++] = items[i++]; };
    while (j <= right) { temp[k++] = items[j++]; };

    // copy from the temporary array back into items
    for (i = left, k = 0; i <= right; i++, k++) {
        items[i] = temp[k];
    }

    free(temp);
}

quickSort.c

// quickSort.c
// Based on Sedgwick's code

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

typedef int Item;

#define key(items) (items)
#define less(items, B) (key(items) < key(B))
#define swap(items, B) { Item t = items; items = B; B = t; }

// function prototypes
int partition(Item items[], int left, int right);
void quicksort(Item items[], int left, int right);


int main() {

    printf("hello, world!\n");

    return EXIT_SUCCESS;
}

void quicksort(Item items[], int left, int right) {
    // base case
    if (right <= left) return;

    int i = partition(items, left, right);

    // recurse on the left of pivot
    quicksort(items, left, i - 1);

    // recurse on the right of pivot
    quicksort(items, i + 1, right);
}

int partition(Item items[], int left, int right) {
    // set some counters
    int i = left - 1;
    int j = right;

    Item pivot = items[right];

    while (true) {  // loop until break condition
        while (key(items[++i]) < key(pivot));

        while (less(pivot, items[--j])) {
            if (j == left) { break; }
        }

        if (i >= j) break;

        swap(items[i], items[j]);
    }

    swap(items[i], items[right]);

    return i;
}