1

Can someone please tell me why does method timeCalc2 that measures insertion sort returns 0 ? For example i use arrays above 100000 elements.

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

public class Sort {

    private static int[] readArray(int arraySize) {
        Random r = new Random();
        int[] arr = new int[arraySize];

            for (int i=0; i<arr.length; i++) {
                arr[i] = r.nextInt(arraySize);
            }
        return arr;
    }

    private static void insertionSort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > current) {
                    arr[j + 1] = arr[j];
                    j = j - 1;
            }
            arr[j + 1] = current;
        }
    }

    private static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
                int min_ind = i;
                for (int j = i+1; j<arr.length; j++)
                    if (arr[j] < arr[min_ind])
                        min_ind = j;
                    int temp = arr[min_ind];
                    arr[min_ind] = arr[i];
                    arr[i] = temp;
        }
    }

    private static double timeCalc1(int[] array) {
        double start1 = System.currentTimeMillis();
        selectionSort(array);
        double finish1 = System.currentTimeMillis();
        return (finish1 - start1) / 1000;
    }

    private static double timeCalc2(int[] array) {
        double start2 = System.currentTimeMillis();
        insertionSort(array);
        double finish2 = System.currentTimeMillis();
        return (finish2 - start2) / 1000;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Input array1 size  : ");
        int[] arr1 = readArray(sc.nextInt());
        System.out.println("Input array2 size: ");
        int[] arr2 = readArray(sc.nextInt());
        System.out.println("Input array3 size : ");
        int[] arr3 = readArray(sc.nextInt());
        int[] arr1a = arr1.clone();
        int[] arr2a = arr2.clone();
        int[] arr3a = arr3.clone();

        selectionSort(arr1);
        selectionSort(arr2);
        selectionSort(arr3);
            
        insertionSort(arr1a);
        insertionSort(arr2a);
        insertionSort(arr3a);

        System.out.println(Arrays.toString(arr1a) + "\n" + Arrays.toString(arr2a) + "\n" +Arrays.toString(arr3a) + "\n");

        System.out.println("Sort time[s] array 1 by search is: " + timeCalc1(arr1));
        System.out.println("Sort time[s] array 1 by inserion is: " + timeCalc2(arr1a));

        System.out.println("Sort time[s] array 2 by search is: " + timeCalc1(arr2));
        System.out.println("Sort time[s] array 2 by inserion is: " + timeCalc2(arr2a));

        System.out.println("Sort time[s] array 3 by search is: " + timeCalc1(arr3));
        System.out.println("Sort time[s] array 3 by inserion is: " + timeCalc2(arr3a));
    }
}
`
Proximo_224
  • 37
  • 8
  • 3
    I suggest you start by reading https://stackoverflow.com/questions/504103 (TL;DR: benchmarking is hard...) But if you believe your insertion sort might not actually be working, I suggest you validate the arrays afterwards. – Jon Skeet Dec 08 '21 at 15:41
  • 5
    Note that by the time you run the `timeCalc` methods, you've *already sorted the arrays*. So you're testing how long it takes to sort an already-sorted array... – Jon Skeet Dec 08 '21 at 15:43
  • So `timeCalc` should be placed before sorting ? – Proximo_224 Dec 08 '21 at 15:44
  • 2
    Your time calc methods include sorting. Why would you do any sorting outside of them? – azurefrog Dec 08 '21 at 15:45
  • 1
    You may try `System.nanoTime()` if only to see whether it makes a difference. – Ole V.V. Dec 08 '21 at 15:51
  • It sure takes some seconds to sort an array above 100000 elenents. – Proximo_224 Dec 08 '21 at 15:52
  • I entered sizes 1000, 10000 and 100000 into your program and got (sorry about the lack of readability): Sort time[s] array 1 by search is: 0.0 Sort time[s] array 1 by inserion is: 0.0 Sort time[s] array 2 by search is: 0.023 Sort time[s] array 2 by inserion is: 0.0 Sort time[s] array 3 by search is: 2.167 Sort time[s] array 3 by inserion is: 0.0 – Ole V.V. Dec 08 '21 at 16:34
  • 1
    When I left out the initial sorting of the arrays, I got the following times: 0.004, 0.002, 0.021, 0.028, 2.172, 0.704. So no zeroes at all. – Ole V.V. Dec 08 '21 at 16:37
  • Thank you. The initial sorting needs to be deleted and than timeCalc methods work fine. But how to print one sorted array before time count methods ???? – Proximo_224 Dec 08 '21 at 16:41
  • 1
    Do I understand the last question? Call `timeCalcN()`, store the return value in a variable, print the array, then print the return value? What am I missing? – Ole V.V. Dec 08 '21 at 19:10

0 Answers0