CSE 331 12au Software Design & Implementation

Exercise #0

out: Monday, September 24, 2012
due: Wednesday, September 26, 2012 by 10 am. 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 code up your algorithm, run it, or debug it on a computer. Use conventional notation as in Java, C, or similar languages to write assignments, loops, conditionals, and other statements.

  • The input is an array b containing n integer values in locations b[0] to b[n-1]. If necessary, you may assume that the array has at least one element, i.e., 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 do any arithmetic on the array elements or assign constant values 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 variables x and y. 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 CSE 331 Au12 home page to turn in a file containing your answer. The file should contain:

  1. Your algorithm.
  2. 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.
  3. The total amount of time you spent on this problem.

Be sure that your name appears at the top of your solution.