# More Complex Structures

## Today:

• More on structures: Rectangles, Finding an apartment
• Yet another array example
• A first look at sorting
• One of the coolest ideas in computing: recursion!

## Review: Structures vs. Arrays

How are structures and arrays similar? How are they different? Why do they matter?

#### Why we care

Computers allow us to deal with vast quantities of information, and with many types of information. Under the covers, the computer represents all of this as bits, coded patterns of zeros and ones. The simple types that C++ gives us like `int` and `string` are very useful for representing individual pieces of information, but they don't have the power we need to conveniently manipulate millions or billions of data items, or data with complex structure. Arrays and structures work together to give us this capability.

#### Arrays

Arrays let us exploit the computer's ability to represent lots of information. Important characteristics of arrays include:

• C++ arrays naturally model mathematical arrays, arrays of data from scientific measurements, or lists of symbolic information
• The elements of an array are homogenous, i.e, the have the same type
• Array elements are identified by a numeric offset or subscript
• These two characteristics enable another vital features of arrays: we can select elements at runtime using variable or computed subscripts as in:
`arr[i]` or `arr[j * 8 + i]`
Assuming the subscript is within bounds 0 .. (length_of_array - 1), the type of the result is the same, so it can be processed by the same code.
• We can use arrays of arrays to model multidimensional data.
• Because structs are first class types, we can have arrays of structs
• Unlike most other C++ data, arrays are passed to functions by reference. That is, the called function operates on the same copy of the array as the caller. Any changes are seen by both.

#### Structures

Structures let us create our own first class types that match or model the objects we have in the real world. If a student has a name, a student ID, course listings, and a GPA in the real world, then we can create a structure type called `Student` that has just those fields. By first class type we mean that the new `Student` type is accepted by C++ in same ways that the built-in types are. In a sense, when you define a struct, you are extending the C++ language to manipulate just the type of data you need. This is a wonderful capability; indeed, the ability to do things like this is one of the characteristics that distinguishes computing systems from many other engineering innovations. Not only can we model new types of data as needed, we can write code that extends the computer with useful capabilities for manipulating that data. For example, we could write code that would automatically update the student's GPA when a new course is added to her list of courses taken. Computers can, in this sense, extend themselves and adapt to new uses in ways that other "machines" can't.

## Using points to make rectangles

We've seen structures used to make new types for our C++ programs. Here we explore how these types can themselves be used in other structs.

Exercise

Specifically, consider a structure representing a point on the x,y plane:

```struct Point {
int x;
int y;
};
```

How can we use two of these structs to define the bounds of a retangle? Explore `rectangles.cpp`.

That program created and displayed an array of retangles, each of which was built from two points. Now we can make the program do more:

Exercise

How can we expand that program to test whether a point we enter from the console is within any of our rectangles? Explore `is_in_rectangle.cpp`

## Finding an Apartment

Go to an apartment website

How does such a web site work? What do they have to represent?

Exercise
• What information does each structure contain? It's hierarchical! Apartment has occupants (maybe), rooms, price, address. (Extra problem, represent an apartment building with floors of apartments.)
• What can you do with the information? Display, search, sort, …
Fill in `apartment.cpp`

Exercise
Design a `Flight` structure.
• Define what a flight is (e.g., origination, destination, departure time, arrival time, fare, fees and taxes, flight number, airline name, etc.)
• How to search for a flight (based on destination, departure time, fare, airline name, etc.)
Fill in `travel-inc.cpp`

## Modifying versus Translating an Array

Often you want to transform the contents of an array.
• Sometimes, as in your programming project, you want to modify the array in place (give an example). Example: Painting a house.
• Sometimes you would like to get a new array. Like translating a book: do you want the original book to be destroyed? A new family moves into a development: they want a new house.

Problem: Given array of temperatures in degrees Celsius, produce an array of equivalent temperatures in degrees Fahrenheit. See: ftoc-list.cpp

## Sorting an array

Sorting is a common programming task. You want to sort a list of apartments by rent, by distance from campus, by the number of bedrooms. You want to sort a list of flights by price, by time enroute, by number of stops, by airline.

Given that sorting has been such a common problem since the inception of modern computing devices, there are many algorithms for accomplishing the task. You'll study quite a few and their relative efficiencies in Algorithms. First imagine how you might sort a stack of papers by the name. Would you create a new stack of papers and move the papers into it one at a time by inserting each one into its appropriate place (insertion sort)? Would you move the first name to the front, then move the next name to the second position (selection sort)? Divid the papers into piles, sort each one, then merge the results (merge sort)? Sorting can be done either in place (the sorted array occupies the same space as the original array) or into another array. Often, we prefer in-place solutions.

Today, just consider the problem of sorting an array of integers. To pick one example, we'll use selection sort. The basic idea is that we think of our array as having two parts, the sorted part, and the unsorted part. Initially, the sorted part contains no values and the entire array is unsorted. What element belongs in the first slot of the array? The least element. If we can find out the least element (minimum) in the unsorted part of the array and exchange it with whatever is currently in the first slot, then the first slot is sorted. So now the unsorted array consists of the second slot in the array through the end of the array. What element belongs in the first slot of the unsorted array (which is actually the second slot in the original array)? It's the minimum element. If we find that element and swap it with the element in that slot, then we have another sorted element. If we continue like this to the end of the array, the array is sorted.

Assume `index_of_min(values, start_index, end)` takes an array `values` returns the index of the least element found starting with index `start_index` and ending with index `end - 1`, i.e., the index of the least element in slots whose index is in [`start_index`, `end`).

Assume `swap(values, i, j)` swaps the elements at indices `i` and `j`.

```/*
* Sort the array in values into ascending order.
*/
void selection_sort_loop(int values[], int size)
{
for (int i = 0; i < size; ++i) {
int index_of_smallest = index_of_min(values, i, size);
swap_fun(values, i, index_of_smallest);
}
}
```
`selection_sort.cpp` shows this code in action. The example also illustrates some other fun things, including some handling of command line arguments, a fun way to swap elements, and a recursive encoding of the sorting algorithm. We'll discuss recursion more later, but note how it very directly reflects our description above: If you have some elements to sort, you put the least element in the first slot, and then you sort the rest of the list.
Mark A. Sheldon (msheldon@cs.tufts.edu) with modifications by Noah Mendelsohn (noah@cs.tufts.edu)