ISC Practicals and Theory - Array Combiner

Array combining means joining two arrays into a third array that holds every element of both, here arranged in ascending order. This version uses a class Combiner with a default constructor; the method combine() receives the two arrays as objects passed as parameters and fills the current object.

Definition

If the first array is $\{5, 1, 9\}$ and the second is $\{8, 1, 3, 5\}$, the combined array has $3 + 4 = 7$ elements. Duplicates are kept, so the result in ascending order is $\{1, 1, 3, 5, 5, 8, 9\}$.

The sorting is done by hand with bubble sort: in each pass, neighbouring elements are compared and swapped if the left one is bigger, so the largest remaining element moves to the end. No library sorting method is used.

Algorithm

1. main creates three objects of Combiner: x, y and z. The default constructor sets size to 0 and arr to an empty array.
2. main calls x.accept(sc) and then y.accept(sc):
   • accept() reads size; if it is less than 1 or more than 20 it returns false, otherwise it creates arr, reads the elements with a loop and returns true.
   • Because of &&, the second array is read only if the first was valid.
3. If either call returned false, main prints INVALID SIZE and stops.
4. Otherwise main calls z.combine(x, y):
   • size becomes a.size + b.size and arr is created with that size;
   • a loop copies the elements of a, then another loop copies the elements of b, using the position counter k;
   • sort() is called.
5. sort() runs bubble sort: for each pass i, the inner loop compares arr[j] with arr[j + 1] for j from 0 to size - 2 - i and swaps them with the help of t when arr[j] > arr[j + 1].
6. main calls display() for x, y and z to print the two inputs and the combined sorted array.

Program

The data members arr and size belong to each object; accept() reads one array, combine() joins two, sort() orders the result and display() prints it.

import java.util.Scanner;

/* Class Combiner stores an integer array and its size.
   combine() merges the elements of two Combiner objects into the current object
   and sorts them in ascending order with a hand-written sorting method. */
public class Combiner
{
    int arr[];   // data member: stores the elements of the array
    int size;    // data member: number of elements stored in arr

    /* Default constructor: starts with an empty array. */
    Combiner()
    {
        size = 0;
        arr = new int[0];
    }

    /* Reads the size and the elements from the keyboard.
       sc : the Scanner used for input (one Scanner is shared by all objects)
       returns true if the size is valid (1 to 20), otherwise false */
    boolean accept(Scanner sc)
    {
        System.out.print("Enter the size of the array (1 to 20): ");
        size = sc.nextInt();
        if (size < 1 || size > 20)      // size outside the allowed range
        {
            return false;
        }
        arr = new int[size];
        System.out.println("Enter " + size + " elements:");
        for (int i = 0; i < size; i++)  // read the elements one by one
        {
            arr[i] = sc.nextInt();
        }
        return true;
    }

    /* Fills the current object with all the elements of a and b (duplicates are kept)
       and then sorts them in ascending order.
       a, b : the two Combiner objects passed as parameters
       returns nothing */
    void combine(Combiner a, Combiner b)
    {
        size = a.size + b.size;         // the new array holds every element of both
        arr = new int[size];
        int k = 0;                      // position in the combined array
        for (int i = 0; i < a.size; i++)
        {
            arr[k++] = a.arr[i];        // copy the elements of a first
        }
        for (int i = 0; i < b.size; i++)
        {
            arr[k++] = b.arr[i];        // then the elements of b
        }
        sort();
    }

    /* 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
        Combiner x = new Combiner();            // first array
        Combiner y = new Combiner();            // second array
        Combiner z = new Combiner();            // combined sorted array
        if (x.accept(sc) && y.accept(sc))       // second array is read only if the first was valid
        {
            z.combine(x, y);
            System.out.println("First array:");
            x.display();
            System.out.println("Second array:");
            y.display();
            System.out.println("Combined sorted array:");
            z.display();
        }
        else
        {
            System.out.println("INVALID SIZE");
        }
    }
}

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): 21
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): 0
INVALID SIZE

Dry run

Take the first sample: $x = \{5, 1, 9\}$ and $y = \{8, 1, 3, 5\}$. combine() copies the elements, giving arr = 5 1 9 8 1 3 5 with size = 7. Then sort() runs bubble sort. The array after each pass is:

display() then prints 1 1 3 5 5 8 9, as in the first sample run.

Variations

1. Merge sorted arrays "Two arrays are already sorted in ascending order. Combine them into a third sorted array without sorting again."
2. Without duplicates "Combine the two arrays and print the sorted result with repeated elements removed."
3. Descending order "Combine the two arrays and arrange the result in descending order."