Demonstrate Big-O for the Oracle Java API Collections.sort(). Use the System clo

Question

Demonstrate Big-O for the Oracle Java API Collections.sort(). Use the System clock (milliseconds) or equivalent way to count operations and assess the run-time complexity, O(N), O(N^2), O(1)??? for Collections.sort(). Create an Excel workbook of your results, and clearly indicate your answer for Big-O. Your chart should have a title, label axes, a line that proposes your answer, and appropriate scales from zero to whatever is large enough to encompass your data. Everyone will have different data, but we might all come to the same Big-O conclusion that Collections.sort is O??? You will likely start with some preliminary results, often getting slightly different results, something like Preliminary.JPG. In the end you will clean things up and get a more polished final chart that displays on the first worksheet along with your data FinalEst.JPG Hints: Your Collection must be large enough so sorting takes at least ideally one or two seconds. Anything higher (like minutes to hours for sorting) will likely be timing the problem of virtual memory instead of Big-O algorithm processing. Submit 2 files here:

Submit 2 files here:

your Testing.java program

your Excel workbook

Explanation / Answer

Collections.sort() method uses merge sorting.

By below statement you can understand why merge sort is used ,

main reason for choosing merge sort is stableness in worstcase running time, that is O(n logn).

"java.util.Collections.sort to sort object references is a "modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist)." It is a reasonably fast stable sort that guarantees O(n log n) performance and requires O(n) extra space. In its day (it was written in 1997 by Joshua Bloch)."

import java.util.ArrayList;

import java.util.Collections;
import java.util.List;
import java.util.Random;

public class CollectionSortAnalysis {

   public static void main(String[] args) {

       Random random = new Random();
       List<Integer> list1 = new ArrayList<>();

      
       for (int i = 0; i < 100000000; i++) {
           list1.add(random.nextInt(1000000000));
       }
       // Test1
       long startTime = System.currentTimeMillis();
       Collections.sort(list1);
       long endTime = System.currentTimeMillis();

       System.out.println("Test1 : " + (endTime - startTime));

       // since the list1 is sorted now if we try to reverse it, that will be
       // another test case.
       startTime = System.currentTimeMillis();
       Collections.sort(list1);
       endTime = System.currentTimeMillis();

       System.out.println("Test2 : " + (endTime - startTime));

   }
}

when you running this program u can find out the runing time of worst case scenario of collections.sort() method.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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