ISC Practicals and Theory - Array Combiner (OOP)

Combining two integer arrays gives a third array holding every element of both, arranged in ascending order. In this version the class Combiner has a parameterised constructor Combiner(int n), and the method combine(Combiner c) **returns a new Combiner object** that holds the sorted union of the current object and the object passed to it.

Definition

The combined array has as many elements as the two arrays together, and duplicates are kept. For $\{5, 1, 9\}$ and $\{8, 1, 3, 5\}$ the result is $\{1, 1, 3, 5, 5, 8, 9\}$ (7 elements). The sorting is hand-written bubble sort; no library sorting method is used.

Algorithm

1. main reads the size n1 of the first array. If it is less than 1 or more than 20 it prints INVALID SIZE and stops.
2. main creates x = new Combiner(n1); the constructor sets size to n1 and creates arr with that size. x.accept(sc) reads the elements.
3. The same is done for the second array: size n2, validation, object y, y.accept(sc).
4. main calls z = x.combine(y):
   • a new object r = new Combiner(size + c.size) is created inside combine();
   • a loop copies the elements of the current object into r.arr, then a second loop copies the elements of c, using the counter k;
   • r.sort() is called and r is returned.
5. sort() is bubble sort: for each pass i, the inner loop compares arr[j] and arr[j + 1] for j from 0 to size - 2 - i and swaps them through t if the left one is larger.
6. main calls display() on x, y and z.

Program

Unlike the default-constructor version, the size is validated in main before the object is made, and combine() returns the result instead of filling the current object.

import java.util.Scanner;

/* Class Combiner stores an integer array and its size.
   combine() takes another Combiner object and RETURNS a new Combiner object
   that holds the elements of both in ascending order (hand-written sort). */
public class Combiner
{
    int arr[];   // data member: stores the elements of the array
    int size;    // data member: number of elements stored in arr

    /* Parameterised constructor: creates an array of n elements.
       n : the size of the array (already checked to be 1 to 20 by main) */
    Combiner(int n)
    {
        size = n;
        arr = new int[n];
    }

    /* Reads the size elements of this object from the keyboard.
       sc : the Scanner used for input. returns nothing */
    void accept(Scanner sc)
    {
        System.out.println("Enter " + size + " elements:");
        for (int i = 0; i < size; i++)  // read the elements one by one
        {
            arr[i] = sc.nextInt();
        }
    }

    /* Combines this object with c (duplicates are kept) and sorts the result.
       c : the Combiner object passed as a parameter
       returns a new Combiner object holding all the elements in ascending order */
    Combiner combine(Combiner c)
    {
        Combiner r = new Combiner(size + c.size);   // result object with room for both arrays
        int k = 0;                                  // position in the result array
        for (int i = 0; i < size; i++)
        {
            r.arr[k++] = arr[i];                    // copy the elements of this object first
        }
        for (int i = 0; i < c.size; i++)
        {
            r.arr[k++] = c.arr[i];                  // then the elements of c
        }
        r.sort();
        return r;
    }

    /* Sorts arr in ascending order by bubble sort. returns nothing */
    void sort()
    {
        for (int i = 0; i < size - 1; i++)          // number of passes
        {
            for (int j = 0; j < size - 1 - i; j++)  // compare neighbouring elements
            {
                if (arr[j] > arr[j + 1])            // out of order: swap them
                {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                }
            }
        }
    }

    /* Prints the elements of the array on one line, separated by spaces. returns nothing */
    void display()
    {
        for (int i = 0; i < size; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);    // one Scanner for both arrays
        System.out.print("Enter the size of the array (1 to 20): ");
        int n1 = sc.nextInt();                  // size of the first array
        if (n1 < 1 || n1 > 20)
        {
            System.out.println("INVALID SIZE");
            return;
        }
        Combiner x = new Combiner(n1);          // first array
        x.accept(sc);
        System.out.print("Enter the size of the array (1 to 20): ");
        int n2 = sc.nextInt();                  // size of the second array
        if (n2 < 1 || n2 > 20)
        {
            System.out.println("INVALID SIZE");
            return;
        }
        Combiner y = new Combiner(n2);          // second array
        y.accept(sc);
        Combiner z = x.combine(y);              // combined sorted array returned as a new object
        System.out.println("First array:");
        x.display();
        System.out.println("Second array:");
        y.display();
        System.out.println("Combined sorted array:");
        z.display();
    }
}

Variable description table

Sample input and output

Enter the size of the array (1 to 20): 3
Enter 3 elements:
5 1 9
Enter the size of the array (1 to 20): 4
Enter 4 elements:
8 1 3 5
First array:
5 1 9 
Second array:
8 1 3 5 
Combined sorted array:
1 1 3 5 5 8 9 

Enter the size of the array (1 to 20): 1
Enter 1 elements:
7
Enter the size of the array (1 to 20): 1
Enter 1 elements:
7
First array:
7 
Second array:
7 
Combined sorted array:
7 7 

Enter the size of the array (1 to 20): 2
Enter 2 elements:
4 4
Enter the size of the array (1 to 20): 3
Enter 3 elements:
4 2 4
First array:
4 4 
Second array:
4 2 4 
Combined sorted array:
2 4 4 4 4 

Enter the size of the array (1 to 20): 0
INVALID SIZE

Enter the size of the array (1 to 20): 3
Enter 3 elements:
1 2 3
Enter the size of the array (1 to 20): 21
INVALID SIZE

Dry run

Take the first sample: $x = \{5, 1, 9\}$ and $y = \{8, 1, 3, 5\}$. Inside x.combine(y) a new object r of size 7 is created and filled with 5 1 9 8 1 3 5. Then r.sort() runs; the array after each pass is:

r is returned and stored in z, so z.display() prints 1 1 3 5 5 8 9, as in the first sample run.

Variations

1. Merge sorted arrays "Two arrays are already sorted. Return a new object holding both arrays merged in order, without sorting again."
2. Descending order "Combine the two arrays and arrange the result in descending order."