In This Lab We Gain Practice in Manipulating Arrays. an Array Is a Data Structure That

Laboratory 12

Sorting

Introduction

In this lab we gain practice in manipulating arrays. An array is a data structure that allows a programmer to organize data into a list, and to refer easily to any object in that list by subscripting, just as we did when we wanted to access the individual characters in a string. Arrays permit us to maintain lists of any type of object, although all members must be of the same type. In this lab the objects will be ints. This new concept will also permit us to study two fundamental problems that computers must solve on an everyday basis. One of these problems is that of sorting a list. In this lab, we will experiment with one C++ sorting program that uses arrays. The other problem is that of searching an array for a specified value, which will be dealt with in Lab 13.

Key Concepts

Arrays as data structures

Arrays as parameters

Problem solving: Finding the maximum

Problem solving: Selection sort

Complexity

Before the Lab

Read Section 9.4 in Cohoon and Davidson.

Preliminary

Turn the PC on, if necessary.

Access the network.

Copy the source files from the Lab 12 Source Files folder.

Start up CodeWarrior.

Open the LabWork project.

Finding the Largest Element in an Array

Observation

Open the file RandomList.cpp and study the program.

The program RandomList.cpp fills the array a with 100 randomly generated ints, by repeatedly calling upon the C++ rand() function. (See the function generateList() in RandomList.cpp.) To use the rand() function, we needed to include the header file cstdlib.h. Once the array has been filled, the program simply prints its contents, 10 numbers per line. (See the function printList() in RandomList.cpp.)

Note that the array a is a reference parameter in generateList() and a const reference parameter in printList().

Why is this so?

Referring to printList(),

Which of the array elements start new lines in the output?

Add RandomList.cpp to the LabWork project.

Run the program to see that it works properly.

Now we will generate a list of random numbers and find the largest number in the list.

Replace the file RandomList.cpp with FindMax.cpp in your project.

Open FindMax.cpp.

Study the program in FindMax.cpp.

This program generates an array of random integers, as before, prints the array, but this time reports both the index and the value of the largest number in the array. Note the difference in usage between maxPos and a[maxPos].

The definitions of generateList() and printList() are in list.cpp, along with swap(), and their prototypes are in list.h. Since we now understand how they work, we have tucked them away so that we do not have to look at them anymore. In order for this program to run, do the following.

Add the file list.cpp to your project.

Run the program to see that it works properly.

Note that the prototype for findMax() is

int findMax(const int a[], int size)

Which parameters are constant? Which are reference? Why?

Study the algorithm for findMax() and be sure that you understand it.

Swapping Elements in an Array

Observation

Replace FindMax.cpp with FindAndSwap.cpp in your project. (Do not remove list.cpp.)

Open FindAndSwap.cpp.

The FindAndSwap.cpp program swaps the largest element in the array with the “front” element a[0].

Run the program to see that it works.

It is now the case that the largest number is where it should be if our ultimate goal is to sort the array elements into decreasing order.

Inspect the array values to determine the location of the element that should now be swapped with a[1] so as to make sure that the first two numbers are where they should ultimately be. (You may need to run the program again in order to see the output window.)

You should have agreed that the second largest number in the array is the one that should be swapped with a[1]. Then, to make more progress towards sorting, we would swap the third largest with a[2], the fourth largest with a[3], and so on.

Unfortunately, in its present form, the function findMax() cannot find any number but the largest in the array. We cannot use it to find the second or third largest. What we need is something more general. We rectify this in the next section.

Sorting an Array

Observation

Replace FindAndSwap.cpp with StartSort.cpp in your project, and open StartSort.cpp. (Do not remove list.cpp.)

Note that the array a will have only 10 elements, so that we don't have to look at so much output.

The StartSort program has exactly what we said we needed: a generalized findMax() function, which we call generalizedMax(). We can now send generalizedMax() a starting point for its search for the largest element. In other words, if the largest element is already at position 0, and we need generalizedMax() to find the second largest, we simply send it 1 for the starting position, since the second largest amongst a[0], a[1], …, a[9] is also the largest amongst a[1], …, a[9].

Run StartSort.cpp and see that it swaps the first member with the largest member.

Experimentation

To see if you understood the above, do the following.

Write statements in StartSort.cpp that will result in the three largest numbers in the array being, in decreasing order, a[0], a[1], and a[2]. You may use the statements

int maxPos = generalizedMax(a, maxLen, 0);

swap(a[0], a[maxPos]);

and repeat the pattern two more times, with appropriate changes.

Run the program to see if it works properly. It should place the three largest numbers in the first three positions, in descending order.

Application

Open the MS Word document Lab 12 App.doc, found in the Lab 12 App subfolder, and follow the instructions.

Summary

We have seen that arrays give the programmer a convenient way of processing lists of data objects. In this lab, we studied arrays and saw them processed in several ways. We studied functions designed to fill an array with randomly generated integers, to print an array’s contents, and to find the index corresponding to the largest member of the array. By calling a generalized version of this last function repeatedly, we saw how to sort an array, via an algorithm that is known as a “selection sort,” which is one of several well-known sorting algorithms requiring O(n2) comparisons to sort an n-element list. Later we will learn more about why this is, and how it can be used to predict the time requirements of our sorting program on lists of various sizes.