import java.util.ArrayList;
import java.util.Random;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import javax.swing.JOptionPane;

public class SortComparisons {

    final static int billion = 1000000000;

    public static void main(String[] args) {
        Random generator = new Random();
        long t1;
        long t2;
        while (true) {
            String input = JOptionPane.showInputDialog("Enter the array size");
            if (input == null) {
                break;
            }
            int size = Integer.parseInt(input);
            int[] big = new int[size];
            for (int i = 0; i < size; i++) {
                big[i] = generator.nextInt(billion);
            }// end for
            big[1] = big[0];
            big[2] = big[0];
            // insertion sort on ints
            if (size <= 100000) {
                int[] bigInsertion = new int[size];
                for (int i = 0; i < size; i++) {
                    bigInsertion[i] = big[i];
                }
                t1 = System.currentTimeMillis();
                Sorts.insertionSort(bigInsertion);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " ints with the insertion sort took " + (t2 - t1) + " milliseconds.");
            }

            // merge sort on ints
            {
                int[] bigMerge = new int[size];
                for (int i = 0; i < size; i++) {
                    bigMerge[i] = big[i];
                }
                t1 = System.currentTimeMillis();
                Sorts.mergeSort(bigMerge);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " ints with the merge sort took " + (t2 - t1) + " milliseconds.");
            }

            // quick sort on ints
            {
                int[] bigQuick = new int[size];
                for (int i = 0; i < size; i++) {
                    bigQuick[i] = big[i];
                }
                t1 = System.currentTimeMillis();
                Sorts.quickSort(bigQuick);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " ints with the quick sort took " + (t2 - t1) + " milliseconds.");
            }

            // Java sort on ints
            {
                int[] bigJava = new int[size];
                for (int i = 0; i < size; i++) {
                    bigJava[i] = big[i];
                }
                t1 = System.currentTimeMillis();
                Arrays.sort(bigJava);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " ints with the Java sort took " + (t2 - t1) + " milliseconds.");
            }

            // insertion sort with Integer
            if (size < 10000) {
                Integer[] ints = new Integer[size];
                for (int i = 0; i < size; i++) {
                    ints[i] = new Integer(big[i]);
                } // end for
                t1 = System.currentTimeMillis();
                Sorts.insertionSort(ints);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " Integers with the insertion sort took " + (t2 - t1) + " milliseconds.");
            }

            // merge sort with Integer
            {
                Integer[] ints = new Integer[size];
                for (int i = 0; i < size; i++) {
                    ints[i] = big[i];
                } // end for
                t1 = System.currentTimeMillis();
                Sorts.mergeSort(ints);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " Integers with the merge sort took " + (t2 - t1) + " milliseconds.");
            }

            // quick sort with Integer
            {
                Integer[] ints = new Integer[size];
                for (int i = 0; i < size; i++) {
                    ints[i] = big[i];
                } // end for
                t1 = System.currentTimeMillis();
                Sorts.quickSort(ints);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " Integers with the quick sort took " + (t2 - t1) + " milliseconds.");
            }

            // Java sort with Integer
            {
                Integer[] ints = new Integer[size];
                for (int i = 0; i < size; i++) {
                    ints[i] = big[i];
                } // end for
                t1 = System.currentTimeMillis();
                Arrays.sort(ints);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " Integers with the Java sort took " + (t2 - t1) + " milliseconds.");
            }
            // quick sort with Strings
            {
                String[] s = new String[size];
                for (int i = 0; i < size; i++) {
                    s[i] = "" + generator.nextInt(billion);
                }// end for
                t1 = System.currentTimeMillis();
                Sorts.quickSort(s);
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " Strings with the quick sort took " + (t2 - t1) + " milliseconds.");
            }
            {
                String[] s = new String[size];
                for (int i = 0; i < size; i++) {
                    s[i] = "" + generator.nextInt(billion);
                }// end for
                t1 = System.currentTimeMillis();
                Sorts.quickSort(s,new LengthComparator());
                t2 = System.currentTimeMillis();
                JOptionPane.showMessageDialog(null, "Sorting " + size + " Strings with the length comparator with the quick sort took " + (t2 - t1) + " milliseconds.");
            }
        }// end while
    }// end main

    static class LengthComparator implements Comparator<String> {
        public int compare(String lhs, String rhs ) {
            int lengthDiff = rhs.length() - rhs.length();
            if( lengthDiff == 0 ) return lhs.compareTo(rhs);
            return lengthDiff;
        }
    }

} // end SortComparisons