Java Program Use the selection sort to sort n numbers Determ

Java Program:

Use the selection sort to sort n numbers. Determine the value of n for which the elapsed time of your sort is about 10 seconds. Double n (i.e., double the number of numbers to sort) and sort. What is the sorting time for the new value of n? Double n again and determine the sorting time. What happens to the sorting time each time you double n? Estimate how long sorting one billion numbers would take.

Solution

1.For N=175000 Selection sort takes:10 seconds.

2.Doubling N=35000. it takes roughly : 42 seconds

3.Doubling again :N=425000 it takes: 94 seconds

4. For N=1 billion It will give

Exception in thread \"main\" java.lang.OutOfMemoryError: Java heap space
   at Codechef.main(Main.java:40)

===Code====

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

public class MySelectionSort {

   public static int[] doSelectionSort(int[] arr) {

       for (int i = 0; i < arr.length - 1; i++) {
           int index = i;
           for (int j = i + 1; j < arr.length; j++)
               if (arr[j] < arr[index])
                   index = j;

           int smallerNumber = arr[index];
           arr[index] = arr[i];
           arr[i] = smallerNumber;
       }
       return arr;
   }

   static void shuffleArray(int[] ar) {
       // If running on Java 6 or older, use `new Random()` on RHS here
       Random rnd = ThreadLocalRandom.current();
       for (int i = ar.length - 1; i > 0; i--) {
           int index = rnd.nextInt(i + 1);
           // Simple swap
           int a = ar[index];
           ar[index] = ar[i];
           ar[i] = a;
       }
   }

   public static void main(String a[]) {
       int[] arr1 = new int[1000000000];
       for (int i = 0; i < 1000000000; i++) {
           arr1[i] = i;
       }
       shuffleArray(arr1);
       long startTime = System.currentTimeMillis();
       int[] arr2 = doSelectionSort(arr1);
       long endTime = System.currentTimeMillis();
       System.out.println(\"Time taken:\" + (endTime - startTime) / 1000+\" seconds\");
       /*for (int i : arr2) {
           System.out.print(i);
           System.out.print(\", \");
       }*/
   }
}