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.
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.
Pretty much the same, except that methods that take in an array don't
need an extra parameter for its size, and Java has no pointers so you
can't write compare_and_swap as described above. Instead,
write compareAndSwap to take in an array and two array
indices; it will compare those two elements of the array, and swap them
if the first is greater than the second (note that we're not worrying
about which index is greater, only which value).
For example,
double arr[3] = {17.3, 12.1, 15.6};
compareAndSwap (arr, 0, 1);
cout << "arr[0]=" << arr[0] << " and arr[1]=" << arr[1];
compare_and_swap (arr, 2, 1);
cout << "arr[2]=" << arr[2] << " and arr[1]=" << arr[1];
should swap elements 0 and 1, but not 2 and 1, and should produce the output
arr[0]=12.1 and arr[1]=17.3 arr[2]=15.6 and arr[1]=17.3
The bubble sort is really not a natural algorithm in Scheme, so start by doing an insertion or selection sort on a list. (A merge sort is more efficient, and only slightly more complicated.)
If you want to learn about Scheme vectors, try implementing a bubble
sort on a vector, using a compare-and-swap function like
that in the Java version above: it takes in a vector and two indices,
and swaps the two elements of the vector if they're out of order.
Pretty similar to the Scheme version: an insertion sort or a selection sort is the most natural thing to try. (A merge sort is more efficient, and only slightly more complicated.)