# Assignment 5: Sorting Out Sorting

Assigned: Friday, 8 October 2010
Due: 11:00 p.m., Wednesday, 13 October 2010

This assignment is also available in PDF.

Summary: In this assignment, you will implement a famous sorting algorithm and explore mechanisms for testing that algorithm.

Purposes: To give you experience implementing real algorithms. To give you experience with testing. To give you experience with simple libraries (or at least separate compilation).

Expected Time: Two to three hours.

Collaboration: I encourage you to work in groups of two or three students. However, you may work on your own or in groups of up to size four. You may discuss the assignment with anyone you wish, provided you clearly document such discussions.

Warning: So that this assignment is a learning experience for everyone, I may spend class time publicly critiquing your work.

## Background

As we've recently noted in class, many programs require similar components. Hence, it behooves you as programmer to build reusable libraries that provide those components.

One component that many programs include is sorting: rearranging an array of values so that the array is in order. There are a number of strategies for sorting arrays and the choice of algorithm often depends on the particulars of the data.

One useful and relatively simple sorting algorithm is selection sort. In selection sort, one repeatedly finds the index of the largest remaining element in the array and swaps it to the end of the subarray.

```void
selection_sort (int values[], int len)
{
int i;
for (i = len-1; i > 1; i--)
{
swap (values, i, index_of_largest (values, i+1));
}
} // selection_sort
```

We assume that `index_of_largest (values,limit)` finds the largst value in the first `limit` elements of `values`. There are two approaches to writing `index_of_largest `: You can write it directly, or you can decompose it into two subproblems: Finding the largest element in an array and finding the index of that value.

```int
index_of_largest (int values[], int limit)
{
return index_of (values, limit, largest (values, limit));
} // index_of_largest
```

## Assignment

a. Create `array_utils.h`, which contains declarations for `swap`, `largest`, `index_of`, `index_of_largest`, `selection_sort`, and any other procedures you expect to write. (Don't worry if you can't come up with them all. You can always change the header later.)

b. Write unit tests for `swap`, `largest`, and `index_of`. You should have three files: `utest_swap.c`, `utest_largest.c`, and `utest_index_of.c`.

c. Write `swap`, `largest`, and `index_of`. All of these should be in a single source file, `array_utils.c`. Use your unit tests to ensure that your code is correct.

d. Write unit tests for `index_of_largest`. Use these unit tests to make sure that the provided implementation of `index_of_largest` is correct. If it is not, correct it.

e. Write an interactive tester for `selection_sort`. Your tester should read up to 1024 integers from standard input and print them out in sorted order. Call your tester `sort.c` (executable `sort`). Use the interactive tester on some inputs you find useful. Correct any errors you detect in `selection_sort`.

f. Write a systematic unit tester for `selection_sort`, `utest_selection_sort.c`. Using this tester, identify and correct any remaining errors in `selection_sort`.

## Hints

In your unit tests for `selection_sort`, you will find it useful to compare arrays. Here is a procedure for comparing arrays.

```/**
* Procedure:
*   array_equal
* Parameters:
*   a1, an array of integers
*   a2, an array of integers
*   len, an integer
* Purpose:
*   Determine if a1 and a2 are equal
* Produces:
*   is_equal, an integer (representing a Boolean)
* Preconditions:
*   len >= 0.
*   a1 contains at least len elements.
*   a2 contains at least len elements.
* Postconditions:
*   If there exists an i, 0 <= i < len s.t. a1[i] != a2[i],
*     returns 0.
*   Otherwise, returns 1.
*/
int
array_equal (int a1[], int a2[], int len)
{
int i;
for (i = 0; i < len; i++)
{
if (a1[i] != a2[i])
return 0;
} // for
// No unequal elements.  They match!
return 1;
} // array+_equal
```

Using `script`, build logs of sample runs of your programs.

Put those logs, your source code, and any other files you deem appropriate in a directory called `username.hw5`.

Make a tarball of that directory.

Submit that tarball as an attachment to an email message entitled should be titled CSC161 Assignment 5.

## History

October 2010 [Samuel A. Rebelsky]

• Created.

Monday, 11 October 2010 [Samuel A. Rebelsky]

• Fixed some bugs in the code.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Mon Oct 11 11:56:02 2010.
The source to the document was last modified on Mon Oct 11 11:56:01 2010.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CSC161/2010F/Assignments/assignment.05.html`.

Samuel A. Rebelsky, rebelsky@grinnell.edu