Question

P1

Consider an array of length n that contains unique integers between 1 and n+1. For example, an array A1 of length 5 might contain the integers 3, 6, 5, 1, and 4. In an array of this form, one number between 1 and n+1 will be missing. In A1, the integer 2 is missing from the array. As another example, consider the array A2 that contain the integers 4, 7, 5, 2, 6, and 1. A2 has size 6, contains integers in the range of 1 to 7. In A2, the integer 3 is missing from this array.

Write a Java method

static int findMissing(int [] a)

that reads the array and returns the number not present in the array. The running time of the algorithm should be O(n).

For A1=[3,6,5,1,4], findMissing(A1) returns 2. For A2=[4,7,5,2,6,1], findMissing(A2) returns 3.

Hint: Use the formula: 1 + 2 + 3 + …+ n = n(n+1)/2

P2

You can sort a large array of m integers that are in the range 1 to n by using an array count of n entries to count the number of occurrences of each integer in the array. For example, consider the following array A of 14 integers that are in the range from 1 to 9 (note that in this case m = 14 and n = 9):

9 2 4 8 9 4 3 2 8 1 2 7 2 5

Form an array count of 9 elements such that count[i-1] contains the number of times that i occurs in the array to be sorted. Thus, count is

1 4 1 2 1 0 1 2 2

In particular, count[0] = 1 since 1 occurs once in A. count[1] = 4 since 2 occurs 4 times in A. count[2]=1 since 3 occurs once in A. count[3] =2 since 4 occurs 2 times in A.

Use the count array to sort the original array A. Implement this sorting algorithm in the function

public static void countingSort(int[] a, int n )

and analyze its worst case running time in terms of m (the length of array a) and n.

After calling countingSort(), a must be a sorted array (do not store sorting result in a temporary array).

P3

The median of a collection of values is the middle value. One way to find the median is to sort the data and take the value at the center. But sorting does more than necessary to find the median. You need to find only the k^th smallest entry in the collection for an appropriate value of k. To find the median of n items, you would take k as n/2 rounded up

You can use the partitioning strategy of quick sort to find the k^th smallest entry in an array. After choosing a pivot and forming the subarrays Smaller and Larger, you can draw one of the following conclusions:

If Smaller contains k or more entries, it must contain the k^th smallest entry

If Smaller contains k-1 entries, the k^th smallest entry is the pivot.

If Smaller contains fewer than k-1 entries, the k^th smallest entry is in Larger.

Implement the recursive method

public satic int findKSmallest(int[] a, int k)

that finds the k^th smallest entry in an unsorted array a.

Use the method findKSmallest to implement the method

public static int findMedian(int[] a)

that finds the median in an array a.

------------------------------------------------------------------------------------------------

//The code below is given need to add methods here:

public class ArraySort

{

public static <T extends Comparable<? super T>>

           void mergeSort(T[] a, int n) {

       mergeSort(a, 0, n - 1);

}

public static <T extends Comparable<? super T>>

           void mergeSort(T[] a, int first, int last) {

       @SuppressWarnings("unchecked")

      T[] tempArray = (T[])new Comparable<?>[a.length];

      mergeSort(a, tempArray, first, last);

}

  

private static <T extends Comparable<? super T>>

              void mergeSort(T[] a, T[] tempArray, int first, int last)

{

       if (first < last) { // sort each half

           int mid = (first + last) / 2;// index of midpoint

           mergeSort(a, first, mid); // sort left half array[first..mid]

           mergeSort(a, mid + 1, last); // sort right half array[mid+1..last]

  

           if (a[mid].compareTo(a[mid + 1]) > 0)

               merge(a, tempArray, first, mid, last); // merge the two halves

           //   else skip merge step

       }

}

  

private static <T extends Comparable<? super T>>

              void merge(T[] a, T[] tempArray, int first, int mid, int last)

{

       // Two adjacent subarrays are a[beginHalf1..endHalf1] and a[beginHalf2..endHalf2].

       int beginHalf1 = first;

       int endHalf1 = mid;

       int beginHalf2 = mid + 1;

       int endHalf2 = last;

  

       // while both subarrays are not empty, copy the

       // smaller item into the temporary array

       int index = beginHalf1; // next available location in

       // tempArray

       for (; (beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2); index++) {

  

           if (a[beginHalf1].compareTo(a[beginHalf2]) < 0) {

               tempArray[index] = a[beginHalf1];

               beginHalf1++;

           }

           else {

               tempArray[index] = a[beginHalf2];

               beginHalf2++;

           }

       }

  

       // finish off the nonempty subarray

  

       // finish off the first subarray, if necessary

       for (; beginHalf1 <= endHalf1; beginHalf1++, index++)

           tempArray[index] = a[beginHalf1];

  

       // finish off the second subarray, if necessary

       for (; beginHalf2 <= endHalf2; beginHalf2++, index++)

           tempArray[index] = a[beginHalf2];

  

       // copy the result back into the original array

       for (index = first; index <= last; index++)

           a[index] = tempArray[index];

   }

  

// Quick Sort

  

// Median-of-three privot selection

// Sort by comparison

private static <T extends Comparable<? super T>>

              void sortFirstMiddleLast(T[] a, int first, int mid, int last)

{

       // Note similarity to bubble sort

       order(a, first, mid); // make a[first] <= a[mid]

       order(a, mid, last); // make a[mid] <= a[last]

       order(a, first, mid); // make a[first] <= a[mid]

}

private static <T extends Comparable<? super T>>

              void order(T[] a, int i, int j)

{

       if (a[i].compareTo(a[j]) > 0)

           swap(a, i, j);

}

  

private static void swap(Object[] array, int i, int j)

{

       Object temp = array[i];

       array[i] = array[j];

       array[j] = temp;

}

  

// Partitioning

  

private static <T extends Comparable<? super T>>

              int partition(T[] a, int first, int last)

{

       int mid = (first + last)/2;

       sortFirstMiddleLast(a, first, mid, last);

       // move pivot to next-to-last position in array

       swap(a, mid, last - 1);

       int pivotIndex = last - 1;

       T pivot = a[pivotIndex];

       // determine subarrays Smaller = a[first..endSmaller]

       // and Larger = a[endSmaller+1..last-1]

       // such that entries in Smaller are <= pivot and

       // entries in Larger are >= pivot; initially, these subarrays are empty

  

       int indexFromLeft = first + 1;

       int indexFromRight = last - 2;

  

       boolean done = false;

       while (!done) {

           // starting at beginning of array, leave entries that are < pivot;

           // locate first entry that is >= pivot; you will find one,

           // since last entry is >= pivot

           while (a[indexFromLeft].compareTo(pivot) < 0)

               indexFromLeft++;

          

           // starting at end of array, leave entries that are > pivot;

           // locate first entry that is <= pivot; you will find one,

           // since first entry is <= pivot

          

           while (a[indexFromRight].compareTo(pivot) > 0)

               indexFromRight--;

                     

           if (indexFromLeft < indexFromRight)

           {

               swap(a, indexFromLeft, indexFromRight);

               indexFromLeft++;

               indexFromRight--;

           }

           else

               done = true;

       } // end while

  

       // place pivot between Smaller and Larger subarrays

       swap(a, pivotIndex, indexFromLeft);

       pivotIndex = indexFromLeft;

      

       return pivotIndex;

}

public static <T extends Comparable<? super T>>

           void quickSort(T[] a, int n) {

       quickSort(a, 0, n - 1);

}

  

public static <T extends Comparable<? super T>>

           void quickSort(T[] a, int first, int last) {

       // perform recursive step if 2 or more elements

       if(first < last) {

           // create the partition: Smaller | Pivot | Larger

           int pivotIndex = partition(a, first, last);

          

           // sort subarrays Smaller and Larger

           quickSort(a, first, pivotIndex - 1);

           quickSort(a, pivotIndex + 1, last);

       }

}

}

Answer 1

// here is complete answer, output is attached, plz comment if you need any clarification.
import java.util.Arrays;

/**
*
* @author ram bablu
*/
public class Chegg192 {
    public static void main(String... agrs) {
        int A1[] = new int[]{3, 6, 5, 1, 4};
        int A2[] = new int[]{4, 7, 5, 2, 6, 1};
       
        int missing = ArraySort.findMissing(A1);
        System.out.println("Missing Element in A1 : "+missing);
        missing = ArraySort.findMissing(A2);
        System.out.println("Missing Element in A2 : "+missing);
       
        int A[] = new int[]{9, 2, 4, 8, 9, 4, 3, 2, 8, 1, 2, 7, 2, 5};
        ArraySort.countingSort(A, 9);
       
        System.out.println("Array Sorted Using Counting Sort : ");
        for(int i : A) {
            System.out.print(i+" ");
        }
        System.out.println();
       
        A = new int[]{9, 2, 4, 8, 9, 4, 3, 2, 8, 1, 11, 7, 2, 5};
        int median = ArraySort.findMedian(A);
        System.out.println("Median of above array is : "+median);
    }
}
//The code below is given need to add methods here:
class ArraySort {
    public static <T extends Comparable<? super T>>
                 void mergeSort(T[] a, int n) {
        mergeSort(a, 0, n - 1);
    }

    public static <T extends Comparable<? super T>>
                 void mergeSort(T[] a, int first, int last) {
        @SuppressWarnings("unchecked")
        T[] tempArray = (T[])new Comparable<?>[a.length];
        mergeSort(a, tempArray, first, last);
    }
   
    private static <T extends Comparable<? super T>>
                  void mergeSort(T[] a, T[] tempArray, int first, int last) {
        if (first < last) { // sort each half
            int mid = (first + last) / 2;// index of midpoint
            mergeSort(a, first, mid); // sort left half array[first..mid]
            mergeSort(a, mid + 1, last); // sort right half array[mid+1..last]
       
            if (a[mid].compareTo(a[mid + 1]) > 0)    
                merge(a, tempArray, first, mid, last); // merge the two halves
            //    else skip merge step
        }
    }
   
    private static <T extends Comparable<? super T>>
                  void merge(T[] a, T[] tempArray, int first, int mid, int last) {
        // Two adjacent subarrays are a[beginHalf1..endHalf1] and a[beginHalf2..endHalf2].
        int beginHalf1 = first;
        int endHalf1 = mid;
        int beginHalf2 = mid + 1;
        int endHalf2 = last;
   
        // while both subarrays are not empty, copy the
        // smaller item into the temporary array
        int index = beginHalf1; // next available location in
        // tempArray
        for (; (beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2); index++) {
       
            if (a[beginHalf1].compareTo(a[beginHalf2]) < 0) {
                tempArray[index] = a[beginHalf1];
                beginHalf1++;
            }
            else {
                tempArray[index] = a[beginHalf2];
                beginHalf2++;
            }
        }
   
        // finish off the nonempty subarray
   
        // finish off the first subarray, if necessary
        for (; beginHalf1 <= endHalf1; beginHalf1++, index++)
            tempArray[index] = a[beginHalf1];
   
        // finish off the second subarray, if necessary
        for (; beginHalf2 <= endHalf2; beginHalf2++, index++)
            tempArray[index] = a[beginHalf2];
   
        // copy the result back into the original array
        for (index = first; index <= last; index++)
            a[index] = tempArray[index];
    }
   
    // Quick Sort
   
    // Median-of-three privot selection
    // Sort by comparison
    private static <T extends Comparable<? super T>>
                  void sortFirstMiddleLast(T[] a, int first, int mid, int last) {
        // Note similarity to bubble sort
        order(a, first, mid); // make a[first] <= a[mid]
        order(a, mid, last); // make a[mid] <= a[last]
        order(a, first, mid); // make a[first] <= a[mid]
    }

    private static <T extends Comparable<? super T>>
                  void order(T[] a, int i, int j) {
        if (a[i].compareTo(a[j]) > 0)
            swap(a, i, j);
    }
   
    private static void swap(Object[] array, int i, int j) {
        Object temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
   
    // Partitioning
   
    private static <T extends Comparable<? super T>>
                  int partition(T[] a, int first, int last) {
        int mid = (first + last)/2;
        sortFirstMiddleLast(a, first, mid, last);

        // move pivot to next-to-last position in array
        swap(a, mid, last - 1);
        int pivotIndex = last - 1;
        T pivot = a[pivotIndex];

        // determine subarrays Smaller = a[first..endSmaller]
        // and                 Larger = a[endSmaller+1..last-1]
        // such that entries in Smaller are <= pivot and
        // entries in Larger are >= pivot; initially, these subarrays are empty
   
        int indexFromLeft = first + 1;
        int indexFromRight = last - 2;
   
        boolean done = false;
        while (!done) {
            // starting at beginning of array, leave entries that are < pivot;
            // locate first entry that is >= pivot; you will find one,
            // since last entry is >= pivot
            while (a[indexFromLeft].compareTo(pivot) < 0)
                indexFromLeft++;
           
            // starting at end of array, leave entries that are > pivot;
            // locate first entry that is <= pivot; you will find one,
            // since first entry is <= pivot
           
            while (a[indexFromRight].compareTo(pivot) > 0)
                indexFromRight--;
                      
            if (indexFromLeft < indexFromRight)
            {
                swap(a, indexFromLeft, indexFromRight);
                indexFromLeft++;
                indexFromRight--;
            }
            else
                done = true;
        } // end while
   
        // place pivot between Smaller and Larger subarrays
        swap(a, pivotIndex, indexFromLeft);
        pivotIndex = indexFromLeft;
       
        return pivotIndex;
    }
                 
    public static <T extends Comparable<? super T>>
                 void quickSort(T[] a, int n) {
        quickSort(a, 0, n - 1);
    }
   
    public static <T extends Comparable<? super T>>
                 void quickSort(T[] a, int first, int last) {
        // perform recursive step if 2 or more elements
        if(first < last) {
            // create the partition: Smaller | Pivot | Larger
            int pivotIndex = partition(a, first, last);
           
            // sort subarrays Smaller and Larger
            quickSort(a, first, pivotIndex - 1);
            quickSort(a, pivotIndex + 1, last);
        }
    }

    public static int findMissing(int[] a) {
        int sum = 0;
        for(int i : a) {
            sum += i;
        }
        int nsum = ((a.length+1) * (a.length+2) / 2); // sum of first n+1 natural numbers
       
        return nsum - sum; // correct sum - original sum = missing element
    }

    static void countingSort(int[] A, int n) {
        int count[] = new int[n+1];
        Arrays.fill(count, 0);
       
        for(int i : A) {
            count[i]++;
        }
       
        for(int i = 1; i < count.length; i++)
            count[i] += count[i - 1];
       
        int sortedA[] = new int[A.length]; // sorted array
        for(int i = 0; i < A.length; i++) {
            sortedA[count[A[i]] - 1] = A[i];
            count[A[i]]--;
        }
       
        // copy the sorted array into A
        System.arraycopy(sortedA, 0, A, 0, A.length);
    }

    static int findMedian(int[] A) {
        int k = A.length/2;
        Integer array[] = new Integer[A.length];
        int ind = 0;
        for(int i : A) {
            array[ind++] = i;
        }
        return findKSmallest(array, k);
    }

    private static int findKSmallest(Integer[] A, int k) {
        if(A.length == 1) return A[0];
        System.out.println(Arrays.asList(A)+"   k = "+k);
        int pivot = partition(A, 0, A.length-1);
        if(pivot > k) {
            return findKSmallest((Integer[])Arrays.copyOfRange(A, 0, pivot), k);
        } else if(pivot < k) {
            return findKSmallest((Integer[])Arrays.copyOfRange(A, pivot+1, A.length), k-pivot-1);
        } else return A[pivot];
     }
}

// OUTPUT