Confused about averaging the duration of different sorting algorithms based on input size?

Question

I am trying to write a method comparing the run times of four different sorting algorithms (mergesort, quicksort, heapsort, insertionsort). I am trying to time each algorithm with each iteration of the for loop, which increases the array size of a randomly generated array each loop. The code that I have works but takes way too much time. At the end of the loop, I am calculating the average time each sorting algorithm took over the arrays from size 1 to 100.

Note: generateArray(num) just creates an array filled with random integers of size num.

I'm not such a great coder, what would be a way to implement it better?

Here's the code snippet:

static void testArrays() {
    ThreadMXBean bean = ManagementFactory.getThreadMXBean();
    long insertionCount=0, mergeCount=0, 
            quickCount=0, heapCount = 0;

    for (int i=1; i<100; i++) {
        long[] A = generateArray(i);
        long[] copy1 = A.clone();
        long[] copy2 = A.clone();
        long[] copy3 = A.clone();

        long startTime1 = bean.getCurrentThreadCpuTime();
        insertionSort(A);
        long endTime1 = bean.getCurrentThreadCpuTime();
        long duration = endTime1 - startTime1;
        insertionCount = insertionCount + duration;

        long startTime2 = bean.getCurrentThreadCpuTime();
        mergeSort(copy1);
        long endTime2 = bean.getCurrentThreadCpuTime();
        long mergeDuration = endTime2 - startTime2;
        mergeCount = mergeCount + mergeDuration;

        long startTime3 = bean.getCurrentThreadCpuTime();
        heapSort(copy2);
        long endTime3 = bean.getCurrentThreadCpuTime();
        long heapDuration = endTime3 - startTime3;
        heapCount = heapCount + heapDuration;


        long startTime4 = bean.getCurrentThreadCpuTime();
        quickSort(copy3);
        long endTime4 = bean.getCurrentThreadCpuTime();
        long quickDuration = endTime4 - startTime4;
        quickCount = quickCount + quickDuration;

    } 
    long averageIS = insertionCount/10000;
    long averageMS = mergeCount/10000;
    long averageHS = heapCount/10000;
    long averageQS = quickCount/10000;
    System.out.println("Insertion Sort Avg: " + averageIS);
    System.out.println("MergeSort Avg: " + averageMS);
    System.out.println("HeapSort Avg: " + averageHS);
    System.out.println("QuickSort Avg: " + averageQS);
}

You may find some useful and interesting information [here: How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Ole V.V., Mar 25 '18 at 11:17
An alternative would be to avoid micro-bench marking by using much larger arrays. The issue here is that the sorts with time complexity O(n^2) will take too long on arrays large enough for sorts with time complexity O(n log(n)) to take long enough to make comparisons easy. There's also the issue of arrays small enough to fit entirely in cache, versus arrays that are a least some multiple of cache size. — rcgldr, Mar 25 '18 at 15:52

score 1 · Answer 1 · answered Apr 06 '18 at 14:52

There are a comparative sort and a distribute sort.

The comparison sort method is a method of performing sorting by comparing two key values to be compared at a time and exchanging them

Distributed sorting is a method of dividing data into several subsets based on key values, and sorting each subset to sort the whole.

It is generally known that Quick Sort is the fastest. In the worst case, n² occurs when the pivot is at its minimum and maximum values. To avoid this, use pivots randomly or Media-Of-Three Partitioning. On average, it produces the best performance.

Insertion Sort is the fastest for already sorted data. If they are already sorted, they are compared only with the first element.

The time complexity of the algorithms described above is as follows.

O (n²): Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, Quick Sort

O (n log n): Heap Sort, Merge Sort

O (kn): Radix Sort (k has a constraint that it can perform well at 4-byte integers with low digits and low digits).

Confused about averaging the duration of different sorting algorithms based on input size?

1 Answers1