Passing arrays to the sorting methods to find their execution time

Question

I'm assigned this project where I need to find execution time for different arrays. My code is working completely fine except for the part when my array moves from selection sort to bubble and from bubble to insertion and to merge. The problem is when my array which random number between 1 - 1000 is getting passed to selection sort and it sorts it out and that sorted array is getting passed to rest of the sorting method. I tried going through my code again but I can't find what the problem is. Am I supposed to populate an array or something?

Any help is appreciated

package sorting;

import java.util.Arrays;
import java.util.Random;
import java.lang.Math;
import java.io.*;
import java.util.*;

public class sorting {

public static void main(String[] args) {

    double[] arr1 = getArray(10000);
    double[] arr2 = getArray(20000);
    double[] arr3 = getArray(40000);
    double[] arr4 = getArray(80000);

    System.out.println("Problem 1: Selection sort, Bubble sort, Insertion sort, and Merge sort with thier execution time");
    System.out.println("");

    System.out.printf("%12s%15s%15s%17s%13s\n", "Number of Elements |", "Selection Sort", "Bubble Sort", "Insertion Sort", "Merge Sort");
    System.out.println("--------------------------------------------------------------------------------");

    long b = System.currentTimeMillis();
    long startTime = System.currentTimeMillis();

    selectionSort(arr1);
    long endTime = System.currentTimeMillis();
    long executionTime = endTime - startTime;
    System.out.printf("%11s", arr1.length);
    System.out.printf("%18s%2s", executionTime, " ms");


    startTime = System.currentTimeMillis();
    bubbleSort(arr1);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    insertionSort(arr1);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    (new MergeSort()).mergeSort(arr1);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s\n", executionTime, " ms");

    System.out.printf("%11s", arr2.length);
    startTime = System.currentTimeMillis();
    selectionSort(arr2);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%18s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    bubbleSort(arr2);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    insertionSort(arr2);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    (new MergeSort()).mergeSort(arr2);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s\n", executionTime, " ms");

    System.out.printf("%11s", arr3.length);
    startTime = System.currentTimeMillis();
    bubbleSort(arr3);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%18s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    bubbleSort(arr3);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    insertionSort(arr3);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    (new MergeSort()).mergeSort(arr3);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s\n", executionTime, " ms");

    System.out.printf("%11s", arr4.length);
    startTime = System.currentTimeMillis();
    bubbleSort(arr4);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%18s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    bubbleSort(arr4);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    insertionSort(arr4);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s", executionTime, " ms");

    startTime = System.currentTimeMillis();
    (new MergeSort()).mergeSort(arr4);
    endTime = System.currentTimeMillis();
    executionTime = endTime - startTime;
    System.out.printf("%12s%2s\n", executionTime, " ms");


}

 public static double[] getArray(int n){
    double[] arr = new double[n];
    for(int i=0; i<n; i++){
        arr[i] = ((double)(Math.random()*1000));
    }
    return arr;
}


public static void selectionSort(double[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {

        double min = arr[i];
        int currentMin = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                currentMin = j;
            }
        }
        if (currentMin != i) {
            arr[currentMin] = arr[i];
            arr[i] = min;

        }
    }

}

public static double[] insertionSort(double[] arr) {
    double temp;
    for (int i = 1; i < arr.length; i++) {

        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
    return arr;
}

public static double[] bubbleSort(double[] arr) {
    double temp;
    for (int i = 0; i < arr.length; i++) {
        // bubble up
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

            }
        }
    }
    return arr;
}

public static class MergeSort {

    private double[] array;
    private double[] temp;
    private int length;

    public double[] mergeSort(double[] arr) {
        this.array = arr;
        this.length = arr.length;
        this.temp = new double[length];
        merge1(0, length - 1);
        return arr;
    }

    private void merge1(int left, double right) {

        if (left < right) {
            double middle = left + (right - left) / 2;
            merge1(left, middle);
            merge1((int) (middle + 1), right);
            merge2(left, middle, right);
        }
    }

    private void merge2(int left, double middle, double right) {

        for (int i = left; i <= right; i++) {
            temp[i] = array[i];
        }
        int i = left;
        int j = (int) (middle + 1);
        int k = left;
        while (i <= middle && j <= right) {
            if (temp[i] <= temp[j]) {
                array[k] = temp[i];
                i++;
            } else {
                array[k] = temp[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = temp[i];
            k++;
            i++;
        }

    }
}
}

This is what I'm getting output as Problem 1: Selection sort, Bubble sort, Insertion sort, and Merge sort with thier execution time

Number of Elements | Selection Sort    Bubble Sort   Insertion Sort   Merge 
Sort
----------------------------------------------------------------------------

  10000                85 ms          31 ms          31 ms          16 ms
  20000               385 ms         100 ms         123 ms          10 ms
  40000              3085 ms         401 ms         347 ms           8 ms
  80000             13231 ms        1972 ms        1484 ms          35 ms

Is the problem that after selection sort the others get the sorted array to process? — Naman, Sep 17 '17 at 15:03
Your outputs looks reasonable based on the complexity of the various sorting methods. Have you tried using a debugger here to find the exact line(s) where the problem is taking place? Most SO users won't have the time to read through your entire pasted code, let alone test it in an IDE. — Tim Biegeleisen, Sep 17 '17 at 15:04
Yes. They are supposed to receive new array for every time it moves on to a different sorting method — Jason Smith, Sep 17 '17 at 15:05

Naman · Accepted Answer · 2017-09-17T15:09:41.097

0

The problem is when my array which random number between 1 - 1000 is getting passed to selection sort and it sorts it out and that sorted array is getting passed to rest of the sorting method

You shall find out the root of the cause at Is Java "pass-by-reference" or "pass-by-value"?

For you, this is because you are passing the value of the array arr1 when you call

selectionSort(arr1);

The manipulations done to arr1 in this case updates the arr1. The next time you pass this to the

bubbleSort(arr1); // this uses the updated array.

You can update your code to use the randomly generated array from your existing method :

selectionSort(getArray(10000)); // similarily for other cases

edited Sep 17 '17 at 15:09

answered Sep 17 '17 at 15:06

Naman

27,789
26
218
353

1

How can I fix it? I've to create a total of 16 arrays with different variables? – Jason Smith Sep 17 '17 at 15:09
@Jason Smith. Updated in the answer. You don't need to create arrays ideally if all you're doing is evaluate the processing time and not storing the data or its context. – Naman Sep 17 '17 at 15:10
1

Got it. Thanks. I'm fairly new to programming. We started coding last year so I'm still a learner – Jason Smith Sep 17 '17 at 15:11
@JasonSmith Cool. If it helps, do mark it as an answer. :) – Naman Sep 17 '17 at 15:12
1

Thank you very much – Jason Smith Sep 17 '17 at 15:17

Passing arrays to the sorting methods to find their execution time

1 Answers1