CODEWITHSUNDEEP
javasortingbenchmarkingbubble-sortnanotime
lchristina26
lchristina26

Reputation: 205

Java: Using System.nanoTime() sorting function taking too long to execute

I am trying to get the total elapsed time for various sort methods at differing array sizes. I am able to get the elapsed time for size = 100, 1000, 10000, and 100000, but when I try 1000000 it just keeps running without giving the result(I assume 1000000 is just too big?). Is there any way to get the elapsed time using nanoTime where it will compile in a reasonable amount of time? Any help would be great!

My program:

import java.util.Random;

public class Sorting {

public static void printArray(int[] array) {
    System.out.print("The Array: ");
    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
    System.out.println();
}

public static void exchange(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void selectionSort(int[] array) {
    for (int fill = 0; fill < array.length - 2; fill++) {
        int minPos = fill;
        for (int j = fill + 1; j < array.length; j++) {
            if (array[j] < array[minPos]) {
                minPos = j;
            }
        }
        exchange(array, fill, minPos);
    }
}

public static void bubbleSort(int[] array) {
    for(int last = array.length - 1; last > 0; last--){
        for(int i = 0; i < last; i ++){
            if(array[i + 1] < array[i]){
                exchange(array, i, i + 1);
            }
        }
    }
}


public static void main(String[] args) {
    int size = 1000000;
    Random rand = new Random();
    int[] arrayToSort = new int[size];
    for (int i = 0; i < size; i++) {
        arrayToSort[i] = rand.nextInt(size);
    }

    //printArray(arrayToSort);
    long startSelect = System.nanoTime();        
    selectionSort(arrayToSort);
    long estSelectTime = System.nanoTime() - startSelect;
    System.out.println("elapsed time after Selection sort for n = " + size + " : " + estSelectTime);
    //printArray(arrayToSort);
//        long startBubble = System.nanoTime();                
//        bubbleSort(arrayToSort);
//        long estBubTime = (System.nanoTime() - startBubble)/size;
//        System.out.println("elapsed time after Bubble sort for n = " + size + " : " + estBubTime);
    //printArray(arrayToSort);

}

}

Upvotes: 1

Views: 842

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533880

If I run for

 100K =>   4.7 secs
 200K =>  18.5 secs
 500K => 116.7 secos
1000K => 4 mins (estimated)

Note: If I change the selection sort like this

public static void selectionSort(int[] array) {
    for (int fill = 0; fill < array.length - 2; fill++) {
        int minPos = fill;
        int minValue = array[minPos];
        for (int j = fill + 1; j < array.length; j++) {
            if (array[j] < minValue) {
                minPos = j;
                minValue = array[j];
            }
        }
        exchange(array, fill, minPos);
    }
}

The 200K takes 14.6 secs instead of 18.5.

Upvotes: 0

Thomas
Thomas

Reputation: 182083

Bubble sort runs in quadratic time, so for each zero you add, the sorting will take 100 times as long. I would guess you can sort 10,000 numbers in the blink of an eye, but it might take a few seconds for 100,000, and therefore at least a few minutes for 1,000,000.

Upvotes: 7

Related Questions