Tutorial Solutions

See it, Say it, Sorted

Break into three groups. Each group should prepare a short demonstration of a sorting algorithm: shell sort, top-down merge sort, heap sort.

Try to demonstrate how the algorithms work and what their properties are.

Shell Sort

void sort_shell (Item items[], size_t lo, size_t hi)
{
	size_t n = hi - lo + 1;
	size_t h = 1;
	while (h <= (n - 1) / 9)
		h = (3 * h) + 1;

	for (/* h */; h > 0; h /= 3) {
		for (size_t i = h; i < n; i++) {
			Item item = items[i];
			size_t j = i;
			while (j >= h && item < items[j - h]) {
				items[j] = items[j - h];
				j -= h;
			}
			items[j] = item;
		}
	}
}

Merge Sort

void sort_merge (Item items[], size_t lo, size_t hi)
{
	if (hi <= lo) return;
	size_t mid = (lo + hi) / 2;
	sort_merge (items, lo, mid);
	sort_merge (items, mid + 1, hi);
	merge (items, lo, mid, hi);
}

static void merge (Item items[], size_t lo, size_t mid, size_t hi)
{
	Item *tmp = calloc (hi - lo + 1, sizeof (Item));
	size_t i = lo, j = mid + 1, k = 0;

	while (i <= mid && j <= hi)
		tmp[k++]
			= less (items[i], items[j])
			? items[i++]
			: items[j++];

	while (i <= mid) tmp[k++] = items[i++];
	while (j <= hi)  tmp[k++] = items[j++];

	for (i = lo, k = 0; i <= hi; items[i++] = tmp[k++]);

	free (tmp);
}

Heap Sort

void sort_heap (Item a[], size_t lo, size_t hi)
{
	size_t N = hi - lo + 1;
	Item *pq = &a[lo - 1];
	for (size_t k = N/2; k >= 1; k--)
		heap_fixdown (pq, k, N);
	while (N > 1) {
		swap_idx (pq, 1, N);
		heap_fixdown (pq, 1, --N);
	}
}

// move value at a[k] to correct position
static void heap_fixdown (Item a[], size_t k, size_t N)
{
	while (2 * k <= N) {
		size_t j = 2 * k; // choose greater child
		if (j < N && item_cmp (a[j], a[j + 1]) < 0)
			j++;
		if (item_cmp (a[k], a[j]) >= 0) break;
		swap_idx (a, k, j);
		k = j;
	}
}

Quickly, now!

One improvement to the quicksort algorithm that we discussed was the use of median-of-three partitioning. In this version of quicksort, three items in the array are sampled, and the median of these three values is used to partition the array. Without looking at the C code given in lectures, complete the following program by replacing the comments with the relevant C program statements.

/// Quick sort with median-of-three partitioning.
void sort_quick_m3 (Item items[], size_t lo, size_t hi)
{
	if (hi <= lo) return;
	size_t i;
	if (hi - lo > 1) {
		qs_median3 (items, lo, hi);
		i = qs_partition (items, lo + 1, hi - 1);
	} else {
		i = qs_partition (items, lo, hi);
	}

	sort_quick_m3 (items, lo, i - 1);
	sort_quick_m3 (items, i + 1, hi);
}

void qs_median3 (Item items[], size_t lo, size_t hi)
{
	// Swap median (value mid-way between `lo' and `hi') with items[hi-1]
	// Compare items[lo], items[hi-1] and items[hi]
	// Rearrange values:
	//   lowest value to be stored in items[lo]
	//   highest value to be stored in items[hi]
	//   median value to be stored in items[hi-1]
}

Trace the calls of qs_median3 and qs_partition on the sequence .

Compare it to standard quicksort.

Both Sides Together!

Given the following definition of a linked list, implement merge sort on linked lists.

typedef struct node node;
struct node {
	Item item;
	node *node;
};

Macro-Invertebrate

Sorting algorithms generally require a swap operation which exchanges two values which are out of order. The swap() operation used in the textbook is implemented as a C macro:

#define swap(a,b)  { Item tmp; tmp = a; a = b; b = tmp; }

Could this be re-implemented as a function? Something like —

void swap (Item i1, Item i2)
{
	Item tmp; tmp = i1; i1 = i2; i2 = tmp;
}

If so, how would you use it? If it would not be suitable, explain why not.

Consider the implementation of swap() in the context of linked lists, where lists are defined as:

typedef struct list *List;
typedef struct list list;
typedef struct node node;
struct node { Item value; node *next; };
struct list { size_t n_items; node *head; };

Would the macro above be suitable? If so, how would you use it? If it would not be suitable, explain why not.

Give a function to implement swap() that would work for both arrays and linked lists. Show examples of how your function would be used for each structure.

The Sentinel

Early in the course, we discussed an alternate representation of linked lists, where to indicate the end of the list, we used a well-known “empty” node, and not NULL.

We can use a similar approach for trees:

typedef struct btree_node btree_node;
struct btree_node {
	Item item;
	size_t size;
	btree_node *left, *right;
};

static btree_node *EMPTY_TREE = NULL;
static void make_empty_tree (void)
{
	if (EMPTY_TREE == NULL)
		EMPTY_TREE = btree_node_new (ItemNULL, NULL, NULL, 0);
}

Given this tree (for which this picture does not show the links to the empty tree nodes), what are the values of the following expressions?

The btree_nth function picks, unsurprisingly, the th item out of a binary tree. Here’s a recursive implementation:

btree_node *btree_nth (btree_node *tree, size_t n)
{
	if (tree == EMPTY_TREE)
		return EMPTY_TREE;
	if (tree->left->size == n)
		return tree;

	if (tree->left->size > n)
		return btree_nth (tree->left, n);
	else
		return btree_nth (tree->right, n - 1 - tree->left->size);
}

Implement a non-recursive version.