0

I have a project to sort array[500000] using quickSort algorithm, I've implemented quickSort like this:

public void sort (int[] array){
        sort(array, 0, array.length - 1);
    }

private void sort (int[] array, int start, int end){
        if (start >= end) {
            return;
        }

        var boundary = partition(array, start, end);
        sort(array, start, boundary - 1);
        sort(array, boundary + 1, end);
    }

    private int partition(int[] array, int start, int end){
        var pivot = array[end];
        var boundary = start - 1;
        for (int i = start; i <= end; i++)
            if (array[i] <= pivot)
                swap(array, i, ++boundary);

        return boundary;
    }

    private void swap(int[] array, int index1, int index2){
        var temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

So I check it; First, I create array with 500000 elements, using some other class (No need to post), and then I get a copy of the array to be able to use it as unsorted again. When I pass the first array to the first object and calculate the runtime, I get something around 300ms, but when I sort the second array (Copy of first unsorted array), I get something around 150000ms. The question is; why these 2 objects which are made from one class, sort the same array in a very different time? Note that I used both System.currentTimeMillies(); and System.nanoTime();, No difference. Also ran it on both linux and Window, no difference again.

Edited: Main Class:

public static void main(String[] args) {
        
        var arrayBuilder = new ArrayBuilder();
        var firstArray = arrayBuilder.getArray();
        var secondArray = arrayBuilder.getArray();
        
        var quickSort1 = new QuickSort();
        long firstSortStart = System.nanoTime();
        quickSort1.sort(firstArray);
        long firstSortEnd = System.nanoTime();
        long firstSortTotal = firstSortEnd - firstSortStart;
        System.out.format("Original QuickSort (Version 1) took %d nano seconds. \n", firstSortTotal);
        
        var quickSort2 = new QuickSort();
        long secondSortStart = System.nanoTime();
        quickSort2.sort(secondArray);
        long secondSortEnd = System.nanoTime();
        long secondSortTotal = secondSortEnd - secondSortStart;
        System.out.format("Changed QuickSort (Version 2) took %d nano seconds. \n", secondSortTotal);
//      this takes ~183861470 nano seconds
        quickSorter2.sort(copiedArray);
//      this takes ~218316931575 nano secondes
th-mhmn
  • 15
  • 7
  • Benchmark.NET? That isn't a thing in java world, perhaps @Fildor thought this was a C# question. The proper tool for benchmarking is [JMH](https://openjdk.java.net/projects/code-tools/jmh/). – rzwitserloot Nov 04 '20 at 17:25
  • Are you sure you've copied the array? Running quick sort on an already sorted array can be very slow. – OrangeDog Nov 04 '20 at 17:33
  • It's better to post code than to describe it. What is the "first object"? What does it do? Does it sort the array? By what method? If you post a [mcve] instead, we'd be able to see for ourselves if you are really copying the array, if the other object does something more clever than you think etc. – RealSkeptic Nov 04 '20 at 17:46
  • It would be cleaner to set `startTime` and calculate the timespan only in `sort(int[] array)`. Currently if you reuse an instance of your sorter class it will use the start time of when the instance was created (because that is when `startTime` is set) and not when sorting started. So every subsequent sorting done by that instance will appear to take longer than the previous one. – Marcono1234 Nov 04 '20 at 21:21
  • @OrangeDog ; Yes, I copied. You can see in main class I posted. – th-mhmn Nov 05 '20 at 10:38
  • @RealSkeptic ; Everything is really clear. First object sorts first array, second one sorts second array (which is exactly the same as firsst array - unsorted) – th-mhmn Nov 05 '20 at 10:39
  • @Marcono1234; I also did that, but I get the exact same time. Thanks for your comment. – th-mhmn Nov 05 '20 at 10:40
  • Not just about the time, my laptop fan starts working when second sorting starts doing its job – th-mhmn Nov 05 '20 at 10:41

1 Answers1

1

This does not copy the array:

var copiedArray = array;

What it does is declare another variable pointing to the same array. Running quicksort on an already sorted array is usually very slow.

To actually copy an array in Java, you need to do e.g.:

var copiedArray = Arrays.copyOf(array, array.length);

Any remaining time differences will likely be due to JIT optimisations. Use a benchmarking system like JMH to account for them.

Edit:
Now you've changed it to two different random arrays, so the runtime difference is now due to the elements being different.

OrangeDog
  • 36,653
  • 12
  • 122
  • 207