Due 2:00PM Friday September 26 — No late submissions accepted
Write an algorithm to partition the elements in an integer array as
described below and argue that your algorithm is
correct. You should not run your algorithm
or debug it on a computer. The idea of this exercise is to get it
right by thinking and analyzing, not by executing, debugging, or
experimenting.
Use Java syntax for a method, but do not
write an entire Java program; just one method. Because you are not
using a computer, we will not grade on tiny syntax mistakes like
forgetting a semicolon, but do your best to write a clear and correct
algorithm.
Your algorithm should work as follows:
- The input is an array b containing n integer values in locations b[0] to b[n-1] where you may assume n >= 1.
- Your algorithm should rearrange the original elements of the
array so that all the negative (<0) elements in the original
array, if any, appear at the front of the array starting in
location b[0]; all of the 0 elements in the original array,
if any, are moved to the middle; and all the positive (>0)
elements, if any, follow that up to
position b[n-1]. The array does not need to be
sorted, just partitioned so the negative, zero, and positive
elements are grouped together.
- You should not use any arithmetic or logical operations to
compute new values for array elements or assign constant values (like 0) to
array elements. Use assignment statements to copy or swap the
original values as needed. You may
write swap(x,y) as a shorthand for
interchanging the contents of x and y
(including array elements like b[i]). You may use
a small number of additional integer variables in your solution but
no additional arrays. The idea is to rearrange the elements of the
original array in place.
- Your solution should run in O(n) time.
Use the catalyst drop-box linked from the course home page to turn in a pdf file containing your answer. The file should contain:
- Your algorithm
- An argument that your algorithm is correct: You may use any informal, but precise, style you wish. If you were unable to completely solve the problem, for instance to create an algorithm that runs in O(n) time, you should describe those problems. Be brief.
- The total amount of time you spent working on this problem
Be sure that your name appears at the top of your solution.
Note: Your solution file must be in pdf format, but it is okay to submit a scanned copy of a handwritten document as long as it is legible when printed and the total file size is no larger than 2-3MB or so.
