CSE 331 Spring 2018

Homework 0

Due: Friday, March 30 by 5 PM

No late submissions will be accepted.

Write an algorithm to partition the elements of 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 the exercise is to get it right by thinking and analyzing, not by executing, debugging, trial-and-error, or experimenting.

Use Java syntax for your code, 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]`. You may assume that `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.
• 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 variables `x` and `y` (including array elements like `b[i]`). You may not use arithmetic or logical operations to compute new integer values to store in the array, and you may not assign integer constant values (like `0`) to array elements. The idea is to rearrange the contents of the original array only by swapping array elements.
• You may use a small number of additional integer variables in your solution but no additional arrays.
• Your solution should run in `O(n)` time, preferably without multiple passes through the array.

• 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 using a single pass through the data, you should describe those problems. Be brief.
Note: gradescope accounts will be created on the first or second day of the quarter for all registered students. You will receive an email message from gradescope with a link you can use to access the turnin page, or you can follow the link on the course home page. If you are not registered for the course before the assignment is due, please send mail to `cse331-staff[at]cs` with your name and UW ID number so we can set up a gradescope account for you.