/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.Arrays;
//export JVM_ARGS="-Xmx1024m -XX:MaxPermSize=256m";

public class ArrayMaker {

// Java implementation to print
// the string in Lexicographical order
// Used for index in heap
    static int x = -1;

// Predefining the heap array
    static String[] heap = new String[200000];
    static String[] heapSorted = new String[0];

// Defining formation of the heap
        static void heapForm(String k) {
        x++;

        heap[x] = k;

        int child = x;

        String tmp;

        int index = x / 2;

        // Iterative heapiFy
        while (index >= 0) {

            // Just swapping if the element
            // is smaller than already
            // stored element
            if (heap[index].compareTo(heap[child]) > 0) {

                // Swapping the current index
                // with its child
                tmp = heap[index];
                heap[index] = heap[child];
                heap[child] = tmp;
                child = index;

                // Moving upward in the
                // heap
                index = index / 2;
            } else {
                break;
            }
        }
    }

// Defining heap sort
    static void heapSort() {
        int left1, right1;

        while (x >= 0) {
            String k;
            k = heap[0];

            // Taking output of
            // the minimum element
            heapSorted = Arrays.copyOf(heapSorted, heapSorted.length + 1);
            heapSorted[heapSorted.length - 1] = k;
//            System.out.print(k + " ");

            // Set first element
            // as a last one
            heap[0] = heap[x];

            // Decrement of the
            // size of the string
            x = x - 1;

            String tmp;

            int index = 0;

            int length = x;

            // Initilizing the left
            // and right index
            left1 = 1;

            right1 = left1 + 1;

            while (left1 <= length) {

                // Process of heap sort
                // If root element is
                // minimum than its both
                // of the child then break
                if (heap[index].compareTo(heap[left1]) <= 0
                        && heap[index].compareTo(heap[right1]) <= 0) {
                    break;
                } // Otherwise checking that
                // the child which one is
                // smaller, swap them with
                // parent element
                else {

                    // Swapping
                    if (heap[left1].compareTo(heap[right1]) < 0) {
                        tmp = heap[index];
                        heap[index] = heap[left1];
                        heap[left1] = tmp;
                        index = left1;
                    } else {
                        tmp = heap[index];
                        heap[index] = heap[right1];
                        heap[right1] = tmp;
                        index = right1;
                    }
                }

                // Changing the left index
                // and right index
                left1 = 2 * left1;
                right1 = left1 + 1;
            }
        }
    }

// Utility function
    static void sort(String k[]) {

        // To heapiFy
        for (int i = 0; i < 2000; i++) {
            heapForm(k[i]);
        }

        // Calling heap sort function
        heapSort();
    }

    static String getAlphaNumericString(int n) {

        // chose a Character random from this String
        String AlphaNumericString = "abcdefghijklmnopqrstuvxyz";

        // create StringBuffer size of AlphaNumericString
        StringBuilder sb = new StringBuilder(n);

        for (int i = 0; i < n; i++) {

            // generate a random number between
            // 0 to AlphaNumericString variable length
            int index
                    = (int) (AlphaNumericString.length()
                    * Math.random());

            // add Character one by one in end of sb
            sb.append(AlphaNumericString
                    .charAt(index));
        }

        return sb.toString();
    }

    public static void main(String[] args) {
//        String[] arr = new String[200000];
//        String arrays[][] = new String[25][200000];
//        for(int i = 0; i < arrays.length; i++){
//            for(int j = 0; j < arr.length; j++){
//                arrays[i][j] = ArrayMaker.getAlphaNumericString(i);
//                System.out.println(arrays[i][j]);
//            }
//
//        }
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = ArrayMaker.getAlphaNumericString(5);
//            System.out.print(arr[i] + " ");
//        }
//        System.out.println("\nSorted:");
//        long start = System.nanoTime();
//        sort(arr);
//        long end = System.nanoTime();

        System.out.println("Arrlen\tStrLen\tHeap\tRadix");
        System.out.println("======\t======\t====\t=====");

        for (int i = 0; i < 25; i++) {
            String arr2[] = new String[2000];
            for (int j = 0; j < arr2.length; j++) {
                arr2[j] = ArrayMaker.getAlphaNumericString(j + 1);
            }
            long start = System.nanoTime();
            sort(arr2);
            long end = System.nanoTime();
            long time = (end - start) / 1000000;
            System.out.println(arr2.length + "\t" + arr2[i].length() + "\t" + time);

        }

//        for (int i = 0; i < heapSorted.length; i++) {
//            System.out.print(heapSorted[i] + " ");
//        }
//        System.out.println("\nHeapSort time to complete: " + (end - start) / 1000000);
//        System.out.println(ArrayMaker.getAlphaNumericString(2));
    }

}