Question

In this problem, we provide you with a Java file called Question2.java. Suppose that there is an array and let us call this array, items. The array items contains n integers. These n integers are in a completely random order in the array. What you are asked to do is to reorder the items in the array such that all the negative integers come before all the zeros and all the positive integers appear at the end. Note, this question is not asking you to sort the numbers in the array. It is asking you to reorder them

In this first example, you can see that the array initially contains the integers 7, −3, 0, 0, 8 and −2. Now, this is in some random order. What you must do to this array, is to reorder the numbers such that the array has three distinct pieces (also called constraints) represented by < 0, == 0 and > 0. You can see that in the first region, we place all the numbers that are less than 0, followed by all zeros and then followed by any numbers that are greater than 0. The numbers within each region can be in any order, as long as they happen to fulfill the constraint.

2. You can only visit all the numbers in the array once. i.e., you are not allowed to have nested loops. Neither can you create a new array or use an array list. You should be able to work on this problem simply by visiting every number once. You must mutate the array that is already provided to you and make changes to this array itself.

3. Do not sort any numbers. If you were to sort the numbers, you would receive zero for this question.

4. The numbers within each region can be in any order, as long as they happen to fulfill the constraint.

5. You cannot assume that there will be at least a single zero in the array. You may very well have an array with all zeros or an array that contains no zero. Assuming that the array contains only negative numbers and positive numbers (≥ 1) If this is the case, you will proceed with reordering the items in the array such that you have negative numbers followed by positive numbers. 6. We provide to you the following methods that must be completed

starter code:

package 3;
//Make sure to copy/paste the honor code and fill in all the required details. 
//If you do not complete the honor code, your assignment will not get marked.
import java.util.Arrays;

public class Question2 {
        /*
         * TODO: You are asked to complete the method
         * rearranging. This method takes in as input an 
         * array of ints and returns back nothing (void).
         * You cannot change the function 
         * signature of this method. Your method question2 must call
         * the swap method. Scroll down to find the swap method.   
         * You cannot use any kind of sorting to answer this question. 
         */
        public static void question2(int[] items)
        {
                
        }
        
        /*
         * TODO: You are asked to complete the method
         * swap. This method takes in as input two ints
         * and an array of ints. The int i and int j 
         * are the index i and index j in the array items.
         * You are asked to swap the value at the index i in items
         * with the value at the index j. You cannot change the function 
         * signature of this method. This method must be called inside question2. 
         */
        private static void swap(int i,int j,int[] items)
        {
                
                
        }

        
        /*
         * Do not write any code inside the main method and expect it to get marked. 
         * Any code that you write inside the main method will be ignored. However, 
         * you are free to edit the main function in any way you like for 
         * your own testing purposes. 
         */
        public static void main(String[] args) {
                
                
                int [] items={-7,-3,20,10,8,2};
                Question2.question2(items);
                System.out.println(Arrays.toString(items)); //must print [-7, -3, 10, 8, 2, 20]
                
                int [] items1={1,1,1,1,1,1,1,1};
                Question2.question2(items1);
                System.out.println(Arrays.toString(items1)); //must print [1, 1, 1, 1, 1, 1, 1, 1]
                
                
                int [] items2={1,2,3,4,5,6,7,8,9};
                Question2.question2(items2);
                System.out.println(Arrays.toString(items2)); //must print [2, 3, 4, 5, 6, 7, 8, 9, 1]
                
                int [] items3={6,7,8,0,1,2,3,-1,-2};
                Question2.question2(items3);
                System.out.println(Arrays.toString(items3)); //must print [-2, -1, 0, 1, 2, 3, 8, 7, 6]
                
                
                
                int [] items4={0,0,0,0,1,2,3,-1,-2,-3};
                Question2.question2(items4);
                System.out.println(Arrays.toString(items4)); //must print [-3, -2, -1, 0, 0, 0, 0, 3, 2, 1]
                
                int [] items5={-1,4,5,6,0,0,0,-2};
                Question2.question2(items5);
                System.out.println(Arrays.toString(items5)); //must print [-1, -2, 0, 0, 0, 6, 5, 4]
                
                
        }
}

Answer 1

The below code satisfies all the constraints described in the problem statement. The outputs may not match with the comments mentioned in main method but the output given by this below program satisfies all the constraints.

import java.util.Arrays;

public class Question2 {
    /*
     * rearranging. This method takes in as input an
     * array of ints and returns back nothing (void).
     * You cannot change the function
     * signature of this method. Your method question2 must call
     * the swap method. Scroll down to find the swap method.
     * You cannot use any kind of sorting to answer this question.
     */
    public static void question2(int[] items)
    {
        if( items.length > 1){
            int j = 0; // keeps track of the index of last parsed number which is less than or equals to zero
            int countZeroes = 0; // keeps track of number of zeroes in order to get the index of last parsed negative number

            for(int i=0; i<items.length; i++){
                if(items[i] < 0){
                    if(i!=j)
                        swap(i, j, items);
                    // swaps the first 0 with the negative number if 0s exist
                    if(countZeroes>0)
                        swap(j-countZeroes, j, items);
                    j++;
                }
                else if( items[i] == 0 ){
                    if(i!=j)
                        swap(i, j, items);
                    j++;
                    countZeroes++;
                }
            }
        }
    }

    /*
     * swap. This method takes in as input two ints
     * and an array of ints. The int i and int j
     * are the index i and index j in the array items.
     * You are asked to swap the value at the index i in items
     * with the value at the index j. You cannot change the function
     * signature of this method. This method must be called inside question2.
     */
    private static void swap(int i,int j,int[] items)
    {
        // The below code swaps the elements without using any extra variable
        items[i] = items[i] + items[j];
        items[j] = items[i] - items[j];
        items[i] = items[i] - items[j];
    }


    /*
     * Do not write any code inside the main method and expect it to get marked.
     * Any code that you write inside the main method will be ignored. However,
     * you are free to edit the main function in any way you like for
     * your own testing purposes.
     */
    public static void main(String[] args) {


        int [] items={-7,-3,20,10,8,2};
        Question2.question2(items);
        System.out.println(Arrays.toString(items)); //must print [-7, -3, 10, 8, 2, 20]

        int [] items1={1,1,1,1,1,1,1,1};
        Question2.question2(items1);
        System.out.println(Arrays.toString(items1)); //must print [1, 1, 1, 1, 1, 1, 1, 1]


        int [] items2={1,2,3,4,5,6,7,8,9};
        Question2.question2(items2);
        System.out.println(Arrays.toString(items2)); //must print [2, 3, 4, 5, 6, 7, 8, 9, 1]

        int [] items3={6,7,8,0,1,2,3,-1,-2};
        Question2.question2(items3);
        System.out.println(Arrays.toString(items3)); //must print [-2, -1, 0, 1, 2, 3, 8, 7, 6]



        int [] items4={0,0,0,0,1,2,3,-1,-2,-3};
        Question2.question2(items4);
        System.out.println(Arrays.toString(items4)); //must print [-3, -2, -1, 0, 0, 0, 0, 3, 2, 1]

        int [] items5={-1,4,5,6,0,0,0,-2};
        Question2.question2(items5);
        System.out.println(Arrays.toString(items5)); //must print [-1, -2, 0, 0, 0, 6, 5, 4]


    }
}

Output is as follows: