CSC 270
Homework 3

Assigned Sept. 22, due Sept. 27

What I want you to do


Write a C++ program that reads in an int, then that many double numbers into an array, sorts them (see below for algorithm), and prints the sorted list. As in homework 2, the int at the beginning should be no smaller than 0, nor larger than 100; if it is, your program should print an appropriate error message rather than asking for the doubles and printing the results.

For example, if the input were
5 3.7 5.2 -4.7 -62 1.2
the output might be
After sorting, the values are -62 -4.7 1.2 3.7 5.2

Also turn in sample runs with well-chosen test cases.

The assignment should be done in teams of two students, working together at one workstation much or all of the time. Each team should turn in one copy of the homework with both names on it.

How I want you to do it

The tasks of reading in the array values, sorting them, and printing them should each be done by a function that takes an array and its size as parameters. In particular, the sorting task should be done by a function named bubble_sort (see below). The bubble_sort function, in turn, should call a function named compare_and_swap which takes pointers (or references) to two numbers, checks whether they're in order (i.e. the first is less than or equal to the second), and swaps them if not. For example, if you write compare_and_swap using pointers, then
double x=17.3, y=12.1, z=15.6;
compare_and_swap (&x,&y);
cout << "x=" << x << " and y=" << y;
compare_and_swap (&z,&y);
cout << "z=" << z << " and y=" << y;
should swap x and y, but not z and y, and should produce the output
x=12.1 and y=17.3
z=15.6 and y=17.3

For those of you unfamiliar with the bubble-sort algorithm...
Suppose you're given an unsorted array. Compare the first two elements; if they're in order, leave them, and if they're not in order, swap them. Then compare the second and third elements and do the same thing. Then the third and fourth, and so on until you get to the last two elements. Once you're done with this, the last element is definitely the largest thing in the array (wherever the largest element in the array was, it won every comparison with a neighbor, so it must have swapped its way all the way to the end), and the remaining elements are more nearly in-order than they were.

Now do all that again (although you can skip comparing the last two elements, since you already know that the largest element is at the end). The second-largest element will make its way into the second-to-last position, and the remaining elements are more nearly in-order than they were. Keep repeating this until the whole array is sorted.

For example, if the array were
{3.7,5.2,-4.7,6.3,1.2}
the bubble-sort algorithm would transform it successively into
3.7 5.2 -4.7 -62 1.2
3.7 5.2 -4.7 -62 1.2
3.7 -4.7 5.2 6.3 1.2
3.7 -4.7 5.2 6.3 1.2
3.7 -4.7 5.2 1.2 6.3
-4.7 3.7 5.2 1.2 6.3
-4.7 3.7 5.2 1.2 6.3
-4.7 3.7 1.2 5.2 6.3
-4.7 3.7 1.2 5.2 6.3
-4.7 1.2 3.7 5.2 6.3
-4.7 1.2 3.7 5.2 6.3

Note: The bubble-sort is not a particularly efficient sorting algorithm -- for real applications I would use a quick-sort, a heap-sort, or a merge-sort -- but it's easy to write and provides a good motivation for the swap function.

Last modified: 
Stephen Bloch / sbloch@adelphi.edu