CS1103 Programming Assignment Unit 1 - Sort arrays using different sorting methods and compare their times

Questions

Please find out how long it takes to sort a large array using both a sorting method that you write and using Java’s built-in sorting method.

1. Codes

import java.util.Arrays;

/**
 * This program is to find out how long it takes to sort a large array using
 * both a sorting method that one write and using Java's built-in sorting method.
 * The results are as follows:
 * array sizes      selectionSort() runtimes       Arrays.sort() runtimes
 * 1,000                   5 ms                             1 ms
 * 10,000                  61 ms                            5 ms
 * 100,000                 4720 ms                          77 ms
 *
 * @author Zhiyao He
 */
public class SortRuntimes {
    /**
     * Declare a constant for initializing the array.
     */
    private static final int SIZE = 10000;

    /**
     * Selection sort
     *
     * @param elements an array passed to the selectionSort() method
     */
    public static void selectionSort(int[] elements) {
        for (int j = 0; j < elements.length - 1; j++) {
            int minIndex = j;
            for (int k = j + 1; k < elements.length; k++) {
                if (elements[k] < elements[minIndex]) {
                    minIndex = k;
                }
            }
            int temp = elements[j];
            elements[j] = elements[minIndex];
            elements[minIndex] = temp;
        }
    }

    /**
     * Insertion sort
     *
     * @param elements an array passed to the insertionSort() method
     */
    public static void insertionSort(int[] elements) {
        for (int j = 1; j < elements.length; j++) {
            int temp = elements[j];
            int possibleIndex = j;
            while (possibleIndex > 0 && temp < elements[possibleIndex - 1]) {
                elements[possibleIndex] = elements[possibleIndex - 1];
                possibleIndex--;
            }
            elements[possibleIndex] = temp;
        }
    }

    /**
     * Create two identical arrays and fill them with random integers.
     * Then use selectionSort() and Arrays.sort() to sort the array, and record the time.
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr1 = new int[SIZE];
        int[] arr2 = new int[SIZE];

        // Initialize the two arrays with random integers.
        // The arrays have identical contents.
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = (int) (Integer.MAX_VALUE * Math.random());
            arr2[i] = arr1[i];
        }

        // Sort the first array using selection sort. Record the time and print it out.
        long startTime = System.currentTimeMillis();
        selectionSort(arr1);
        long runTime = System.currentTimeMillis() - startTime;

        System.out.println("selectionSort runtimes: " + runTime + " ms");


        // Sort the second array using Arrays.sort. Record the time and print it out.
        startTime = System.currentTimeMillis();
        Arrays.sort(arr2);
        runTime = System.currentTimeMillis() - startTime;

        System.out.println("Arrays.sort runtimes: " + runTime + " ms");
    }
}

2. Outputs

When the array size is 1000:

selectionSort runtimes: 5 ms
Arrays.sort runtimes: 1 ms

Process finished with exit code 0

When the array size is 10,000:

selectionSort runtimes: 61 ms
Arrays.sort runtimes: 5 ms

Process finished with exit code 0

When the array size is 100,000:

selectionSort runtimes: 4720 ms
Arrays.sort runtimes: 77 ms

Process finished with exit code 0

​

---

This is the ending, thanks for reading.

---