Pages

Friday, 3 January 2020

Merge Sort using copyOf method

/* Java program for Merge Sort using copyOf  method*/
import java.util.*;
class msrk
{
    static void sort(int a[], int p, int r)
    {
        if (p < r)
        {
            // Find the middle point
        int q = (p+r)/2;
       
        // Sort first and second halves
            sort(a, p, q);
            sort(a , q+1, r);
   
        // Merge the sorted halves
            merge(a, p, q, r);
            System.out.printf("\n merged array element :");
            int[] FS = Arrays.copyOf(a,r+1);
            for (int k=0; k<FS.length; k++)
            System.out.print(FS[k]+" ");
        }
    }

    public static void main(String args[])
    {
        int a[] = {38,27,43,3,9,82,10};
        int n = a.length;
   
    System.out.printf("\n unsorted array :");
    for (int i=0; i<n; i++)
            System.out.print(a[i]+" ");
              
        sort(a, 0, n-1);

        System.out.printf("\n sorted array :");
        for (int i=0; i<n; i++)
            System.out.print(a[i]+" ");
        }
  
    static void merge(int a[], int p, int q, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = q-p+1 ;
        int n2 = r-q; // r-(q+1)+1  r-q-1+1

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];
       
        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
           L[i] = a[p + i];
   
       for (int j=0; j<n2; ++j)
            R[j] = a[q + 1 + j];
   
        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged sub array
        int k = p;
        while (i < n1 && j < n2)
        {
          a[k++]=(L[i] <= R[j]) ? L[i++] : R[j++];
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            a[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            a[k] = R[j];
            j++;
            k++;
        }
    }
}
output:

No comments:

Post a Comment

Constructors & Destructors in c++

  Constructors :  A Constructor is a special member function, which is used to initialize the objects of its class. The Constructor is invok...