A & DS: Exercises from Wednesday

Exercise 1. In the lecture, I described sorting algorithms that are given an unsorted array A and place its sorted values into a new array B. Their signature looked something like this: 

public static int[] sort(int[] A) {
   int n = A.length;
   int[] B = new int[n];
   ... 
   // sort A into B 
   ... 
   return B;
}
In practice, most sorting algorithms sort the values of A in place: they don't create a second array but rather rearrange the values in A until the values are in sorted order.

Create a method that sorts A in place. It should scan through the values in an array A of n integers, from lowest to highest index, swapping successive pairs of values if they are out of order. Note that after one such scan, the largest value will be in A[n-1]. Repeating this scan, the second largest value will be in A[n-2], and so forth, until all of A is in sorted order.

Since your method sorts A in place it can have the signature 

public static void sort(int[] A) {
   int n = A.length;
   ... 
   // sort within A 
   ...
}
You might consider modifying InsertionSort.java so that it uses your sorting method. It runs by sorting a sequence of integers enetered on the command line. If you want to keep with convention, call it BubbleSort.java.

Exercise 2. Write a postscript procedure whose use is of the form

n  maxof
that moves the largest of the n values at the top of the stack, to the top of the stack. It preserves the order of the other n-1 values on the stack. For example the postcript command sequence
6 2 7 1 4 5 maxof
should yield the stack contents
6 2 1 4 7
by removing the 7 and putting it at the top of the stack.

Optionally write the procedure so that it does not use arrays. If you do, you'll probably want to use the roll command

n  i  roll
which modifies a stack containing the contents
x_n   ...    x_i+1    x_i   ...   x_1
so that it has the contents
x_i   ...    x_1   x_n   ...   x_i+1
In other words, it removes the top i elements off the stack and puts them n-i places deeper in the stack.

Exercise 3 (Optional). Although it is possible to use arrays in Postscript, it is also possible to sort the contents of the stack without the use of an array by manipulating the stack. Devise a Postscript sorting procedure that does this. You might use your work from Exercise 2.