Adjust the (nlogn) algorithm below: public class Uniqueintegers { public static

Question

Adjust the (nlogn) algorithm below:

public class Uniqueintegers {

public static void main(String[] args) {
// TODO code application logic here
int arr[]={4, 2, 6, 4, 3, 5, 5, 6, 6, 1, 7};
int i,j;
for(i=0;i<11;i++){
boolean isUnique = false;
for(j=0;j if(arr[i]==arr[j])
{
isUnique = true;
break;
}
}
if(!isUnique)
{
System.out.println(arr[i]);
}
}
}
}

1.) This O(nlogn) algorithm should now run simulations for the following array sizes n = 10, 100, 1000, 10000

2.) Each array should contain random integers ranging from 1 to 500

3.) For each array size (10, 100, 1000, 10000), run 50 simulations and output the total execution time in nanoseconds or milliseconds

Explanation / Answer

Here we use sorting to sort the array which takes O(nlogn) time and then traverse the array to find unique elements in o(n) time.To overall time complexity is O(nlogn).

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package integer;

import java.util.Arrays;
import java.util.Random;

/**
*
* @author xyz
*/
public class Uniqueintegers {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // n varies from 10 to 10000
     for(int n=10;n<=10000;n=n*10)
     {
        int num;
        //Starting time during execution   
        long startTime = System.currentTimeMillis();
        int []arr=new int[n];
        Random rand = new Random();
      
        for(int i=0;i<arr.length;i++)
        {
            num=rand.nextInt(500) + 1;
            arr[i]=num;
        }  
      
         // First sort the array so that all occurrences become consecutive
         Arrays.sort(arr);     
    
            
          // Traverse the sorted array
         for (int i=0; i<arr.length; i++)
    {
       // Move the index ahead while there are duplicates
       while (i < arr.length-1 && arr[i] == arr[i+1])
          i++;

       // print last occurrence of the current element
         System.out.println(arr[i]);
    }
   
    long endTime   = System.currentTimeMillis();
    long totalTime = endTime - startTime;
    System.out.println("Total Time execution for "+n+" numbers is " +totalTime +" ms");
    }
  
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.