Big O Notation

• Sort Times
• Sort Counters
• Table To Compare
• Hashmaps

Sort Times

import java.util.Arrays;
import java.util.Random;

public class sortTimes {


    // selection sort
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
    }
    }

    // bubble sort
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (array[j] > array[j+1]) {
                    // swaps array[j] and array[j+1]
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

    public static void bubbleDoubleSort(double[] array) {
        int n = array.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (array[j] > array[j+1]) {
                    // swaps array[j] and array[j+1]
                    double temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

    // merge sort
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        
        for (i = left; i <= right; i++) {
            arr[i] = temp[i - left];
        }
    }

    // insertion sort
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            if (j + 1 != i) {
                arr[j + 1] = key;
            }
        }
        
    }

    public static double average(double[] arr) {
        double sum = 0;
        for (double num : arr) {
            sum += num;
        }
        return sum / arr.length;
    }
    
    public static void main(String[] args) {

        // populate array with 5000 random elements
        int[] arr0 = new int[5000];
        Random randNum = new Random();
        for (int i = 0; i < 5000; i++) {
           arr0[i] = randNum.nextInt(10000);
        }
        System.out.println("Random numbers = "+Arrays.toString(arr0));
        int arr1[] = Arrays.copyOf(arr0, 5000);
        int arr2[] = Arrays.copyOf(arr0, 5000);
        int arr3[] = Arrays.copyOf(arr0, 5000);
        int arr4[] = Arrays.copyOf(arr0, 5000);



        // create arrays to store times for each sort
        double[] selectionTimes = new double[12];
        double[] bubbleTimes = new double[12];
        double[] mergeTimes = new double[12];
        double[] insertionTimes = new double[12];

        for (int i = 0; i < 12; i++) {
            // selection sort
            long selectionStart = System.nanoTime();
            selectionSort(arr1);
            long selectionEnd = System.nanoTime();
            selectionTimes[i] = (selectionEnd - selectionStart);

            // bubble sort
            long bubbleStart = System.nanoTime();
            bubbleSort(arr2);
            long bubbleEnd = System.nanoTime();
            bubbleTimes[i] = (bubbleEnd - bubbleStart);

            // merge sort
            long mergeStart = System.nanoTime();
            mergeSort(arr3, 0, arr3.length - 1);
            long mergeEnd = System.nanoTime();
            mergeTimes[i] = (mergeEnd - mergeStart);

            // insertion sort
            long insertionStart = System.nanoTime();
            insertionSort(arr4);
            long insertionEnd = System.nanoTime();
            insertionTimes[i] = (insertionEnd - insertionStart);
        }

        bubbleDoubleSort(selectionTimes);
        bubbleDoubleSort(bubbleTimes);
        bubbleDoubleSort(mergeTimes);
        bubbleDoubleSort(insertionTimes);



        double[] trimmedSelectionTimes = new double[selectionTimes.length - 2];
        System.arraycopy(selectionTimes, 1, trimmedSelectionTimes, 0, selectionTimes.length - 2);
        double[] trimmedBubbleTimes = new double[bubbleTimes.length - 2];
        System.arraycopy(bubbleTimes, 1, trimmedBubbleTimes, 0, bubbleTimes.length - 2);
        double[] trimmedMergeTimes = new double[mergeTimes.length - 2];
        System.arraycopy(mergeTimes, 1, trimmedMergeTimes, 0, mergeTimes.length - 2);
        double[] trimmedInsertionTimes = new double[insertionTimes.length - 2];
        System.arraycopy(insertionTimes, 1, trimmedInsertionTimes, 0, insertionTimes.length - 2);


        double selectionAverage = average(trimmedSelectionTimes);
        double bubbleAverage = average(trimmedBubbleTimes);
        double mergeAverage = average(trimmedMergeTimes);
        double insertionAverage = average(trimmedInsertionTimes);

        System.out.println("Selection Sort Average Time: " + selectionAverage);
        System.out.println("Bubble Sort Average Time: " + bubbleAverage);
        System.out.println("Merge Sort Average Time: " + mergeAverage);
        System.out.println("Insertion Sort Average Time: " + insertionAverage);
    


        //System.out.println("Sorted: " + Arrays.toString(arr4));
    }
}
sortTimes.main(null);

Random numbers = [608, 9013, 6590, 4391, 1245, 5021, 271, 9450, 5826, 7866, 7479, 3275, 1408, 4791, 5833, 7066, 1703, 1420, 1059, 2973, 1577, 1560, 3651, 5981, 9293, 3404, 2554, 2186, 3920, 9702, 8089, 5292, 8006, 9465, 5000, 679, 4541, 693, 7766, 1705, 5538, 5097, 9946, 52, 6797, 8130, 9863, 3891, 9896, 301, 3039, 4346, 4141, 3329, 5727, 5582, 6253, 7426, 4135, 5934, 5116, 3796, 2461, 3373, 6458, 1869, 8647, 2669, 8733, 5876, 6054, 8154, 7146, 5564, 1491, 7376, 3826, 823, 9137, 2201, 3097, 1513, 7794, 4407, 1442, 6442, 4486, 5258, 4373, 7991, 8222, 5631, 9475, 5863, 830, 918, 5473, 1013, 9616, 7038, 5551, 8574, 2854, 7631, 8189, 2776, 6743, 5635, 3187, 6380, 1787, 8850, 8462, 4594, 9282, 5784, 9611, 1432, 2142, 37, 5388, 3119, 5553, 1810, 1431, 9635, 1440, 7403, 5550, 5684, 1575, 3405, 8969, 789, 2455, 4461, 9535, 2513, 6586, 5938, 1220, 7781, 1527, 2304, 9996, 7421, 6529, 2242, 5582, 1663, 2602, 6019, 2244, 6254, 2388, 5689, 7166, 9660, 5800, 5471, 3126, 5184, 8400, 6286, 6398, 6112, 7374, 4615, 6053, 3114, 9840, 7135, 4137, 7365, 6811, 5031, 3975, 2575, 324, 3991, 9518, 4114, 4478, 3335, 4401, 2216, 7165, 9898, 1370, 327, 1513, 9639, 5452, 6476, 8718, 4693, 8498, 2048, 1824, 4514, 6323, 4377, 5756, 7520, 7126, 256, 4810, 4861, 8738, 7018, 4031, 1565, 9342, 3125, 5198, 774, 4840, 9153, 5102, 3144, 6977, 9464, 6391, 295, 3589, 3675, 7638, 3782, 3192, 3275, 977, 4162, 6988, 6193, 8900, 696, 1231, 1770, 4633, 3492, 4578, 8675, 6021, 1703, 1332, 5965, 1695, 9300, 5196, 8316, 5165, 4311, 9110, 1042, 5415, 8466, 9108, 5347, 7228, 5094, 6278, 9508, 5827, 2106, 613, 4037, 6474, 5179, 4297, 121, 778, 4800, 3530, 4430, 2844, 1801, 8211, 6637, 1252, 68, 7330, 2543, 5100, 9563, 5772, 3529, 7900, 5069, 3374, 486, 6756, 7895, 5295, 1712, 76, 7311, 1697, 4075, 2755, 8989, 9558, 270, 7715, 9479, 79, 5966, 5638, 2855, 8719, 7177, 7170, 7691, 6542, 9852, 8831, 7112, 9801, 994, 6698, 7148, 7831, 4201, 9922, 3711, 9303, 4690, 4495, 1093, 9973, 1589, 4082, 9987, 2891, 6863, 7271, 2987, 9060, 681, 9992, 8133, 1164, 6118, 3644, 2460, 3107, 5753, 2748, 9459, 5920, 3376, 1253, 9538, 3218, 1137, 89, 1953, 3554, 7071, 5072, 7855, 5508, 7145, 957, 127, 7708, 1007, 5515, 6320, 5422, 9490, 7414, 2232, 3853, 9975, 4517, 3356, 1813, 5128, 3525, 3294, 8117, 6935, 9858, 9060, 6147, 5888, 7918, 8609, 7363, 2266, 1476, 9410, 4611, 7017, 7046, 55, 9454, 4243, 5970, 2795, 3888, 1596, 5523, 322, 8568, 1905, 9492, 6367, 5225, 2958, 7551, 7007, 2939, 2796, 8596, 3189, 6496, 9275, 2405, 4403, 1472, 3175, 1054, 5522, 5781, 1354, 9890, 4910, 9507, 14, 8672, 3872, 479, 9677, 1748, 6969, 3616, 4199, 1498, 5352, 9539, 5439, 6350, 7481, 9592, 8499, 9487, 8427, 2970, 3493, 5266, 475, 2252, 7867, 7618, 2370, 4703, 4720, 4868, 3176, 2336, 1508, 2041, 1251, 3934, 1207, 2093, 544, 57, 8077, 8701, 6461, 4166, 3583, 8326, 4624, 7711, 4942, 2487, 4216, 7735, 7716, 616, 5294, 9867, 8057, 3188, 8311, 6452, 8143, 1682, 9449, 298, 522, 466, 5991, 8994, 7503, 706, 2619, 1031, 24, 5904, 8735, 6615, 9106, 9082, 1544, 4644, 2563, 9521, 3728, 4619, 7851, 6108, 1919, 2465, 3158, 5337, 1204, 5929, 714, 7870, 5781, 9795, 1876, 9294, 3905, 5935, 1482, 7223, 9438, 4254, 5292, 5175, 3685, 1097, 3611, 767, 4214, 5947, 1270, 8720, 200, 1913, 4174, 8418, 961, 674, 773, 1140, 6559, 2674, 1751, 253, 1409, 2384, 6964, 6481, 4453, 6551, 5146, 3967, 5534, 450, 9019, 343, 3745, 6081, 4656, 5657, 5020, 9848, 9482, 1513, 5668, 6870, 9472, 8430, 2138, 707, 4522, 6729, 5482, 386, 8985, 7875, 8351, 7238, 6513, 7055, 4966, 1809, 5668, 111, 365, 8471, 2635, 6243, 6184, 2866, 8756, 2156, 3920, 5871, 5987, 7342, 6072, 8437, 6822, 772, 9629, 1670, 9258, 4397, 3449, 3533, 6371, 5700, 9045, 2199, 700, 7885, 2841, 8639, 7547, 6507, 7105, 3650, 6928, 9007, 5773, 5809, 6682, 5163, 6309, 1076, 5622, 3813, 647, 4395, 7877, 9399, 5215, 8528, 7256, 7059, 9825, 1240, 8747, 8867, 6198, 8905, 6603, 6206, 1297, 3942, 7141, 2071, 5389, 9317, 2285, 288, 4789, 8033, 3944, 8860, 6607, 9515, 7638, 945, 4854, 5915, 3615, 3884, 3330, 4805, 4505, 4863, 902, 4871, 5283, 3109, 5622, 2031, 305, 2919, 7699, 5849, 1253, 8135, 7973, 9541, 1014, 5225, 8132, 807, 6256, 2913, 4914, 6600, 9656, 8967, 8664, 7338, 889, 9047, 7548, 121, 672, 2805, 4508, 8173, 3440, 8558, 5754, 1532, 8211, 8826, 8963, 4076, 5518, 8814, 8653, 8806, 4128, 7054, 4829, 38, 1959, 4751, 6675, 7631, 5375, 3865, 9202, 7020, 8855, 700, 2624, 2752, 4705, 1306, 5558, 8415, 3478, 530, 2980, 5494, 8308, 1053, 9653, 7413, 9558, 4881, 4090, 6557, 1966, 5459, 1141, 4675, 5905, 5257, 5412, 5700, 2335, 4718, 9560, 7988, 6605, 270, 7970, 6207, 8577, 1569, 1289, 2912, 762, 6405, 4474, 559, 5353, 2403, 5276, 4069, 6383, 2708, 7838, 2204, 6709, 9805, 4384, 466, 7458, 6885, 3067, 7404, 1549, 8647, 7630, 8726, 6095, 9058, 6694, 1768, 7603, 7422, 6488, 5477, 7677, 9610, 1422, 2845, 5061, 7249, 8269, 1874, 4111, 9418, 6399, 5128, 6712, 574, 369, 6438, 4558, 6133, 6923, 5353, 12, 5929, 6391, 1063, 1809, 5148, 6064, 464, 2556, 5590, 296, 4737, 3478, 1462, 8006, 8323, 2092, 1305, 8235, 3904, 1928, 2297, 2063, 5957, 1915, 5693, 6973, 2275, 2841, 1150, 3320, 1888, 6032, 713, 6104, 9003, 2886, 768, 9892, 60, 7407, 2572, 8413, 9673, 1720, 9981, 2405, 7333, 9059, 641, 7707, 562, 2831, 6979, 7780, 136, 3907, 2475, 1192, 2878, 1639, 6404, 5254, 7957, 5422, 8362, 1604, 3029, 2116, 7714, 5047, 7006, 9809, 5236, 6875, 544, 343, 2227, 5567, 326, 5549, 8221, 3921, 2381, 6152, 7325, 1522, 7363, 7747, 1502, 4341, 3003, 9627, 7066, 281, 4957, 8874, 2065, 3264, 4281, 8206, 1589, 6363, 8828, 8964, 3554, 4885, 7979, 166, 3483, 4713, 9628, 9119, 9679, 5168, 2917, 503, 1243, 7259, 2380, 9520, 7193, 6969, 4493, 5595, 5878, 1493, 794, 199, 4177, 9536, 2444, 2215, 8446, 4614, 1464, 9071, 7995, 1104, 3933, 9675, 7258, 6229, 2426, 9004, 8397, 1405, 4253, 7328, 6432, 3556, 4325, 9292, 7600, 9208, 8057, 617, 7962, 2447, 7153, 4681, 5070, 2087, 2562, 3620, 3073, 2059, 3400, 4611, 7170, 623, 4331, 6456, 3076, 6265, 9652, 3688, 9930, 252, 5305, 6759, 8434, 7010, 7444, 8734, 2536, 2725, 8706, 4411, 3531, 9626, 39, 2069, 8476, 5354, 1102, 5129, 4274, 4702, 2046, 1222, 1083, 1063, 5337, 1155, 5901, 7880, 814, 1192, 9259, 9264, 6382, 4079, 355, 5064, 3195, 5208, 5636, 1637, 7500, 7683, 1244, 3450, 5166, 3326, 8927, 5981, 9061, 8891, 4373, 1188, 7856, 8412, 4634, 9228, 6970, 7390, 7129, 4006, 5532, 5791, 1042, 6990, 6415, 2142, 1384, 6506, 2640, 9582, 3816, 8795, 9533, 2310, 8643, 1411, 2988, 9192, 9340, 4787, 4314, 2396, 6781, 4751, 5152, 3384, 4020, 4177, 1986, 4878, 731, 1687, 7378, 8530, 5525, 7722, 2113, 4262, 7796, 8508, 9413, 5924, 8776, 3613, 1174, 4808, 402, 569, 5859, 8040, 6102, 2273, 2898, 9424, 1311, 5461, 1636, 1182, 1500, 9099, 342, 7703, 5560, 4703, 2660, 6868, 24, 1384, 600, 2381, 2749, 8642, 8512, 2208, 2377, 9036, 7086, 7501, 5550, 4064, 7545, 4593, 5250, 7595, 5760, 2445, 2143, 1049, 1903, 7699, 7655, 4062, 2570, 381, 6452, 4771, 3270, 3529, 5245, 5227, 1143, 8277, 3157, 8032, 2708, 9251, 286, 4527, 8247, 6761, 2507, 2397, 1216, 1592, 5203, 7428, 9161, 5590, 9072, 6959, 9636, 1018, 9303, 8510, 2385, 4484, 3251, 309, 9068, 3542, 4490, 2551, 7795, 5459, 6305, 299, 436, 5267, 8683, 3592, 8117, 1648, 3900, 3315, 8030, 3264, 1533, 7361, 4064, 3551, 2104, 5115, 9225, 904, 3970, 8286, 7263, 2111, 4168, 4603, 682, 6959, 8498, 3234, 6527, 2475, 2469, 5413, 3078, 6755, 6533, 5692, 6861, 6789, 2983, 5525, 3253, 8909, 5588, 4118, 122, 5643, 8633, 4609, 9697, 6624, 3659, 2402, 4602, 868, 6121, 5176, 9956, 582, 6010, 5742, 9631, 5825, 1989, 6516, 61, 536, 1727, 687, 3826, 2142, 638, 1961, 4731, 1124, 5964, 7606, 1355, 9440, 8440, 165, 7263, 6694, 4231, 9744, 5027, 6630, 8456, 3504, 942, 2673, 6196, 2847, 7321, 2537, 1060, 7995, 6061, 6597, 7389, 5892, 7273, 9693, 7638, 1331, 8083, 4136, 5722, 1910, 6422, 4976, 3977, 9820, 5465, 479, 2329, 4698, 4817, 9576, 4601, 4999, 6652, 1252, 5174, 3418, 6590, 2343, 903, 2062, 6026, 3022, 2995, 4864, 6694, 9752, 2083, 2053, 3296, 3950, 6097, 1642, 9775, 9472, 8463, 9433, 2290, 9006, 613, 2596, 3701, 5311, 7106, 4866, 8115, 7954, 3315, 7779, 7413, 6815, 1314, 4706, 4183, 2680, 1062, 1366, 1564, 3233, 2904, 3540, 8056, 1433, 5014, 4405, 4571, 3572, 7520, 6544, 1118, 7639, 3247, 4212, 1782, 2896, 7893, 3155, 9317, 5743, 8528, 8334, 6879, 9860, 8409, 1081, 2634, 102, 1353, 1547, 1871, 6365, 5034, 1621, 2462, 7214, 5739, 7804, 9166, 5265, 4958, 9045, 9585, 1615, 4284, 8172, 1829, 669, 6376, 9472, 1623, 9216, 8576, 5518, 9043, 2476, 3103, 3929, 4870, 5661, 7136, 4003, 4948, 1265, 2397, 6843, 5894, 3040, 3990, 8915, 8203, 9912, 5630, 9676, 8751, 4378, 1710, 8784, 7049, 2635, 8317, 4172, 5966, 7000, 7351, 5496, 7171, 745, 137, 5893, 9695, 3456, 8831, 6162, 1375, 4463, 7029, 1386, 7155, 1427, 6938, 4653, 2694, 7152, 7155, 9929, 8172, 9594, 4396, 21, 6932, 3582, 8904, 4491, 8972, 523, 441, 2112, 8051, 673, 6075, 7697, 2905, 3924, 3355, 1387, 9075, 5900, 1686, 2630, 4059, 1772, 2556, 6367, 3749, 7420, 4931, 3297, 460, 7862, 2935, 6671, 458, 9226, 1039, 1889, 8758, 1918, 7227, 6121, 4248, 982, 6905, 3873, 6664, 27, 7335, 3218, 7301, 2091, 5619, 6963, 6161, 2862, 5455, 7212, 825, 2640, 1552, 3462, 931, 7087, 6101, 8946, 9152, 6035, 2548, 2434, 5601, 9364, 8624, 7864, 8277, 6269, 967, 5977, 9216, 9116, 8600, 5869, 696, 8946, 3970, 3078, 9769, 5501, 7399, 3754, 3512, 3839, 463, 7246, 9317, 7563, 2009, 7905, 3833, 1612, 6604, 8403, 2143, 8866, 9596, 608, 3919, 8122, 9720, 2669, 6069, 7544, 1664, 3614, 2305, 5108, 2212, 97, 9751, 3422, 920, 3051, 4310, 2927, 2004, 2492, 4806, 5182, 5015, 4337, 4058, 1931, 2955, 6567, 374, 6043, 963, 7591, 394, 5777, 7362, 1746, 571, 2598, 3253, 90, 3955, 2244, 3968, 8714, 8079, 5124, 1127, 323, 8583, 7746, 6642, 9892, 1386, 2170, 7332, 7510, 2887, 5474, 8837, 3105, 6376, 9892, 7738, 542, 841, 8262, 5702, 3499, 7719, 1895, 9931, 3780, 5587, 328, 5065, 6340, 117, 6836, 9671, 5751, 8093, 7646, 1423, 9627, 37, 9622, 5298, 8323, 5411, 4359, 5981, 4391, 9963, 9392, 6756, 9084, 16, 1613, 7771, 6155, 3835, 8209, 9540, 8817, 2772, 5394, 9890, 3379, 3181, 9921, 6092, 6443, 79, 3269, 2653, 179, 7707, 3763, 5096, 2333, 6259, 8588, 6488, 3452, 4785, 67, 3670, 9027, 8309, 1225, 1268, 8056, 5708, 4471, 2870, 213, 5195, 8647, 1296, 8107, 8123, 4000, 8490, 8355, 9775, 6860, 49, 1970, 1249, 4151, 2167, 3527, 6138, 2822, 3850, 5829, 5216, 6226, 9106, 3304, 8361, 2800, 5332, 7318, 8430, 5134, 5476, 3459, 7659, 9804, 87, 3616, 4259, 7348, 8054, 1618, 9425, 7607, 1582, 9515, 4489, 1958, 1845, 3383, 8428, 2634, 8375, 9476, 2762, 8688, 1486, 862, 8146, 4900, 7984, 5527, 1749, 4073, 9730, 5856, 2185, 3667, 3467, 6887, 26, 993, 4675, 9469, 5338, 7626, 3562, 6641, 8504, 4643, 4629, 9854, 9279, 8682, 1283, 7583, 9253, 6178, 5485, 7371, 6644, 107, 9708, 8112, 1478, 2493, 4325, 3968, 5337, 1, 6847, 9106, 5906, 220, 8181, 583, 5885, 9337, 7639, 7403, 1379, 9906, 4427, 5299, 9636, 8619, 497, 2729, 9556, 6923, 2436, 3760, 1378, 7655, 8524, 1318, 355, 2429, 7648, 4694, 4750, 3930, 1656, 8119, 9696, 712, 9841, 9477, 3087, 2408, 1290, 4634, 2924, 5080, 8876, 5960, 6194, 9616, 5238, 4901, 3771, 1087, 6501, 2116, 6801, 6685, 8499, 1388, 4785, 2141, 6727, 8823, 4668, 7746, 1226, 3881, 264, 5626, 5834, 6795, 5956, 7754, 6167, 8803, 776, 1208, 2490, 2402, 6026, 5919, 7590, 5321, 8141, 8947, 1846, 3993, 5348, 9905, 7990, 7654, 9397, 4274, 2878, 2663, 6904, 2428, 6329, 7932, 9054, 8245, 8164, 2124, 6607, 5573, 738, 7211, 4156, 1750, 1899, 6916, 7571, 7835, 1109, 3305, 8960, 1658, 987, 2308, 3120, 5159, 9433, 9592, 9105, 2383, 1034, 3225, 9046, 3278, 8665, 3989, 6567, 4749, 9555, 7645, 4484, 7595, 3630, 5236, 7114, 6791, 1203, 6339, 575, 5880, 1942, 7991, 6135, 4121, 3318, 5784, 4456, 2947, 3456, 2374, 2651, 4697, 1182, 418, 8089, 3370, 6829, 790, 9285, 3383, 7420, 7954, 4169, 9042, 3024, 5236, 9576, 110, 1300, 9267, 6162, 5417, 5102, 8521, 1638, 5971, 9293, 5082, 5729, 3609, 9951, 4501, 2005, 9891, 910, 86, 5910, 3958, 8346, 8773, 9693, 2790, 5458, 5183, 4127, 7372, 9452, 6670, 3272, 9056, 6516, 9368, 4929, 7267, 5953, 3665, 4785, 4540, 8419, 2430, 7215, 1405, 8057, 6759, 3941, 4689, 6287, 5128, 3680, 804, 9716, 757, 7684, 3231, 6345, 4071, 4460, 7086, 2886, 7398, 3584, 4448, 2487, 6053, 5967, 7995, 4147, 4501, 4284, 665, 205, 5639, 405, 9075, 9459, 5026, 7597, 1592, 4788, 1805, 3660, 3817, 639, 7529, 9644, 8725, 8150, 3150, 1940, 7804, 3233, 801, 4514, 2467, 6879, 8415, 4049, 3459, 6424, 56, 9818, 1741, 3517, 2922, 695, 4830, 6001, 6153, 3267, 6667, 1153, 6008, 8173, 7210, 3550, 23, 699, 8428, 204, 1290, 8634, 5562, 9587, 417, 9572, 6571, 1250, 41, 9499, 5568, 9155, 2478, 4049, 2221, 6057, 1147, 1994, 1716, 6151, 1472, 3529, 3823, 4346, 1199, 1240, 249, 8278, 5443, 5571, 7993, 5407, 6829, 7827, 8332, 2062, 7708, 6728, 5871, 2211, 1000, 6224, 2422, 2457, 2348, 6852, 7836, 3189, 9485, 1170, 1031, 3896, 9611, 5605, 4551, 6500, 1588, 2112, 9355, 1883, 5647, 4362, 9343, 4563, 187, 7042, 9350, 1446, 37, 6452, 2704, 1846, 5040, 8788, 6121, 5806, 9044, 3623, 4430, 5123, 8261, 1586, 1900, 7433, 6111, 650, 9687, 2146, 8875, 5930, 6324, 5633, 1121, 3426, 6787, 109, 7306, 8492, 9132, 497, 9072, 3003, 2085, 3792, 3956, 8588, 7613, 758, 7612, 3119, 5928, 5225, 7783, 9438, 4904, 286, 5054, 3323, 4756, 2952, 5177, 8041, 3303, 3388, 843, 4689, 7768, 800, 76, 3925, 9890, 1281, 2113, 8800, 1295, 1396, 8249, 5420, 3798, 1524, 8790, 4766, 2445, 314, 6966, 812, 9021, 4923, 9262, 62, 977, 1931, 9506, 162, 3898, 767, 1523, 6409, 1971, 3088, 4085, 416, 1339, 6876, 2892, 6521, 8516, 7766, 6579, 3559, 8839, 8061, 8376, 7401, 2130, 6683, 871, 2477, 5472, 3396, 1682, 454, 4451, 3150, 4906, 2776, 3856, 7615, 1660, 7104, 1286, 1698, 5115, 561, 7149, 6404, 5429, 9801, 1735, 9787, 7989, 1474, 5158, 1605, 6917, 1940, 3018, 1630, 1806, 2599, 3924, 1292, 7102, 23, 9117, 8085, 1028, 9376, 9516, 8416, 1450, 8905, 9080, 8649, 3888, 1037, 9946, 7949, 9937, 3428, 6685, 5909, 2932, 6992, 3093, 6368, 1570, 5475, 6858, 7193, 6638, 5054, 5599, 8840, 6006, 581, 7075, 7604, 7365, 3422, 5972, 1542, 4690, 6904, 5850, 9721, 5928, 9079, 9799, 5885, 963, 1326, 7641, 6842, 6932, 5974, 1066, 4498, 3697, 3082, 1188, 5743, 3900, 9189, 4148, 2492, 3214, 3875, 2554, 5056, 976, 7013, 2986, 7397, 2054, 6048, 3122, 182, 7785, 1797, 3960, 5126, 6639, 7546, 1024, 2846, 7768, 1975, 9127, 6382, 9448, 9982, 6911, 4949, 9932, 3201, 9911, 8252, 8795, 4695, 6069, 2284, 9466, 1465, 8739, 1616, 7324, 6855, 212, 7141, 2133, 3656, 897, 6029, 3817, 5998, 1861, 4867, 3413, 4008, 3825, 7865, 3497, 2353, 6940, 5678, 8465, 3766, 1819, 9131, 8223, 5252, 5881, 6748, 2919, 8655, 6867, 9996, 4855, 432, 3811, 6569, 9120, 2902, 3014, 7286, 4309, 8717, 4812, 6751, 1599, 5164, 6460, 6327, 4826, 4040, 3058, 1838, 3712, 4006, 7270, 8815, 3872, 2798, 3161, 6165, 6619, 3323, 6734, 5773, 1883, 5839, 3027, 5190, 2127, 3571, 3531, 1221, 9719, 43, 7114, 8581, 8377, 3112, 6300, 7452, 6478, 2728, 4658, 1401, 7837, 3000, 5178, 522, 2225, 6761, 6346, 5066, 3673, 4384, 2408, 5798, 5724, 4312, 2777, 6912, 1526, 1842, 6644, 7085, 5620, 284, 8914, 4746, 6552, 5920, 3541, 2620, 6537, 243, 2178, 7604, 171, 1854, 3228, 7360, 5942, 8985, 4734, 3471, 3701, 9907, 4997, 8253, 6750, 4622, 872, 3308, 7449, 7992, 2789, 2164, 6078, 5284, 8233, 433, 7568, 9751, 5467, 1450, 5792, 5038, 8773, 2146, 5279, 4156, 7488, 9767, 835, 9842, 7500, 8424, 8853, 7447, 7209, 1012, 3429, 23, 6980, 7821, 9611, 9976, 6241, 6412, 3883, 71, 4130, 958, 3268, 1889, 3169, 2395, 5669, 2446, 2080, 3159, 1004, 39, 4330, 8081, 4861, 3928, 2885, 5754, 475, 8049, 1271, 2496, 8678, 5382, 4466, 7416, 3441, 8967, 526, 1257, 6654, 169, 33, 7765, 5705, 6579, 9709, 5651, 1102, 8869, 3286, 8823, 7127, 2163, 4846, 6804, 8502, 4335, 9296, 3880, 156, 196, 6501, 6821, 36, 4015, 3158, 3615, 6910, 9224, 4398, 6401, 6763, 639, 3515, 906, 3170, 7137, 8834, 5062, 2718, 6585, 9116, 1159, 4948, 3299, 5088, 1154, 5284, 28, 1854, 5014, 4379, 5541, 8213, 6838, 3042, 7542, 3106, 9096, 9080, 9920, 7399, 6310, 791, 5483, 7859, 6306, 9685, 3454, 4195, 2343, 3961, 4236, 2885, 2762, 2071, 9483, 4212, 2607, 2730, 1921, 6389, 5704, 8957, 9175, 1821, 5128, 5735, 3551, 349, 2726, 3936, 6834, 3275, 3773, 84, 3026, 1150, 5040, 5299, 9550, 7365, 9355, 1187, 6996, 1173, 5605, 5283, 2192, 462, 5921, 876, 1123, 776, 7603, 3302, 4383, 7455, 7472, 676, 7230, 7176, 5694, 413, 3171, 271, 442, 6264, 5304, 3503, 9161, 8099, 2870, 1757, 8230, 7744, 660, 8753, 9002, 4173, 7718, 337, 2298, 9214, 3990, 4524, 1098, 8249, 9232, 5056, 2383, 8366, 7160, 3465, 4195, 8769, 1190, 9287, 4433, 7014, 6945, 8986, 9535, 8647, 1738, 8045, 364, 9268, 9055, 4412, 5183, 1896, 8400, 2899, 1343, 1316, 5822, 1124, 2817, 75, 3999, 5524, 7724, 6298, 6831, 1700, 3209, 3025, 2960, 3367, 3973, 337, 4546, 2164, 2120, 852, 2797, 4682, 1504, 9316, 6203, 3402, 5911, 7625, 1059, 86, 1044, 4243, 3136, 6069, 6941, 3472, 3136, 7871, 4314, 1962, 6808, 9403, 1428, 1520, 7461, 7891, 812, 992, 7293, 6496, 712, 5278, 5668, 7080, 8408, 7971, 7322, 6192, 5639, 4260, 6338, 8400, 3709, 7390, 6334, 9394, 1329, 4363, 2662, 6901, 140, 9876, 4375, 676, 6328, 1891, 8440, 1151, 3448, 8084, 2679, 7491, 1777, 1448, 8530, 123, 5238, 1733, 5538, 7362, 8545, 653, 1602, 9427, 8173, 1656, 7437, 4703, 1921, 5329, 1157, 1354, 759, 4315, 5584, 2435, 1338, 6750, 637, 1038, 2702, 9442, 5221, 7584, 361, 9078, 9980, 2998, 591, 974, 6, 4579, 5755, 2615, 9334, 788, 8905, 2519, 6322, 961, 1954, 870, 2530, 6354, 286, 5123, 1272, 2459, 5853, 9317, 1225, 4006, 8049, 7967, 1209, 3068, 4419, 9246, 1813, 63, 742, 434, 8106, 5831, 5497, 6679, 6387, 2279, 1253, 4367, 4719, 9947, 3222, 4333, 7921, 2673, 7639, 9232, 5345, 6736, 1814, 1515, 9488, 1897, 8183, 3933, 3769, 9225, 1988, 1650, 7266, 9433, 1505, 4581, 1634, 4034, 2493, 4528, 8604, 8784, 8309, 9682, 4266, 946, 147, 219, 2901, 7466, 7012, 791, 4464, 8615, 1496, 5669, 6565, 2941, 6802, 8338, 4759, 4686, 2318, 1815, 9110, 9495, 1026, 5068, 2593, 6249, 9485, 2759, 5478, 5683, 3789, 1253, 4069, 4617, 8717, 9908, 2051, 4659, 9963, 6874, 2570, 1715, 8087, 4198, 8589, 5076, 4519, 7601, 3464, 9388, 5255, 9104, 2390, 3151, 254, 3993, 2989, 3920, 2444, 8848, 2069, 6563, 176, 7469, 1382, 708, 118, 4523, 9774, 4910, 9021, 8287, 2337, 7481, 7479, 9139, 7307, 739, 6809, 4846, 3889, 8250, 3634, 1714, 7958, 2675, 569, 210, 8681, 7722, 1567, 686, 3532, 7766, 4771, 5101, 975, 3880, 4532, 7701, 251, 3472, 2913, 5001, 1482, 7308, 8380, 9792, 451, 5870, 3614, 1598, 6133, 201, 6756, 6257, 9705, 8664, 8390, 9546, 4665, 1547, 1496, 6790, 2447, 6303, 6410, 7065, 7622, 7016, 7034, 8198, 4573, 3037, 2362, 7500, 5050, 2145, 4459, 4656, 2299, 7545, 8632, 8755, 7191, 6575, 4048, 3377, 4355, 5010, 3179, 8069, 3345, 5816, 6253, 9132, 8755, 9201, 2793, 7669, 2557, 889, 1773, 3217, 8777, 1769, 8443, 2076, 7139, 3834, 6695, 8792, 3972, 1368, 4732, 5283, 5965, 8511, 1690, 4309, 3193, 5381, 9706, 4808, 6117, 1556, 4466, 419, 5196, 5153, 2131, 4597, 2362, 9422, 4607, 1707, 1890, 9032, 8825, 830, 7675, 8526, 7765, 9116, 1237, 6543, 9998, 6177, 7689, 8174, 2134, 5361, 7295, 2901, 2776, 5621, 3481, 4755, 2009, 6576, 3597, 8532, 8237, 1213, 6288, 5899, 9558, 8247, 5693, 894, 72, 1284, 8612, 9118, 4744, 8767, 1088, 3410, 4482, 4497, 5153, 63, 1993, 5915, 2808, 6742, 6345, 2882, 1041, 6202, 7528, 151, 7482, 3132, 5211, 4530, 466, 2069, 886, 9738, 9085, 9679, 5259, 8004, 7892, 5184, 9380, 4822, 9481, 3252, 9355, 919, 6760, 1415, 1062, 5413, 4329, 7452, 368, 4546, 9569, 7692, 6434, 7035, 2824, 4510, 7457, 4566, 3398, 7247, 9921, 1736, 4167, 6815, 5768, 8161, 9310, 2872, 8445, 6021, 3397, 9627, 7710, 9927, 9490, 4585, 657, 1987, 9141, 2842, 9474, 1737, 4605, 8446, 4140, 465, 4299, 1102, 5779, 191, 1023, 8430, 365, 3941, 1390, 2689, 7441, 7471, 5413, 2281, 1655, 191, 4727, 3849, 4111, 1893, 6002, 1353, 7550, 5483, 7920, 726, 3827, 1131, 5530, 1539, 8584, 4813, 4150, 1360, 6788, 3648, 3073, 7829, 9965, 5332, 3847, 4139, 1867, 1842, 7391, 6583, 6151, 5337, 3348, 1876, 3906, 6262, 1230, 844, 6274, 7647, 5232, 6802, 8167, 5036, 6058, 3119, 3884, 5586, 9262, 9544, 2169, 3453, 4415, 8584, 9846, 7514, 4150, 3535, 265, 9390, 1503, 7799, 6528, 423, 5408, 878, 2363, 8733, 9337, 4901, 1744, 3075, 2838, 9396, 8578, 7088, 8674, 7, 5035, 9349, 9078, 9417, 6662, 3963, 4975, 4252, 6698, 5130, 4094, 8339, 2369, 8168, 3448, 2428, 1559, 6172, 3630, 9100, 4381, 6030, 5703, 9912, 2828, 5437, 7529, 1102, 951, 6588, 1430, 7247, 218, 4314, 7139, 4713, 2255, 6268, 9236, 5652, 6015, 6121, 2451, 5769, 3445, 3315, 4816, 3738, 3758, 8269, 9186, 690, 7549, 6429, 9404, 6778, 8939, 9039, 683, 117, 4603, 6691, 6923, 2153, 7676, 5444, 5352, 3035, 2039, 2934, 7026, 9605, 9256, 9995, 5418, 3478, 1850, 2754, 5450, 3094, 3755, 8813, 9233, 3940, 5087, 1518, 7756, 5695, 9584, 3917, 2352, 6589, 6514, 5704, 3507, 331, 197, 6584, 9994, 5586, 2980, 2172, 9293, 5026, 3002, 9716, 8023, 1566, 4468, 2187, 858, 7811, 209, 5586, 5071, 4502, 4711, 6421, 7835, 9082, 3983, 733, 861, 1354, 9904, 8593, 4227, 4409, 649, 4393, 1389, 3043, 4696, 5985, 6105, 7264, 1912, 1479, 3597, 2613, 7527, 3217, 5412, 8998, 3717, 6862, 8671, 7420, 1976, 8551, 1949, 959, 6477, 1889, 437, 7936, 7081, 7122, 6224, 3798, 4989, 7421, 724, 8195, 4456, 6812, 4234, 8033, 8262, 3513, 1505, 6575, 4230, 6313, 588, 7810, 8970, 1333, 902, 490, 4135, 5766, 5366, 2834, 6588, 7997, 3421, 6931, 8384, 2909, 7724, 950, 4564, 7926, 2435, 132, 1831, 2590, 484, 9948, 6232, 8429, 5638, 6399, 5878, 6773, 2646, 748, 4420, 3452, 1511, 7379, 4696, 1176, 2714, 1448, 6642, 566, 4281, 5415, 9994, 887, 3757, 2158, 9538, 4376, 79, 1691, 1323, 9516, 7435, 8402, 3715, 7992, 4817, 4043, 1819, 3771, 8997, 1479, 2215, 9543, 1879, 5725, 9567, 7344, 7453, 4789, 6739, 4496, 9020, 3327, 7835, 3909, 7685, 9441, 667, 216, 8587, 6428, 6534, 2283, 4931, 5354, 1450, 1566, 6661, 8966, 57, 9693, 4959, 887, 4568, 8266, 3177, 7690, 8368, 9970, 6371, 9148, 929, 8687, 9098, 4881, 4806, 4106, 4985, 6979, 9492, 6954, 7436, 3563, 7725, 5646, 1152, 5045, 6161, 2514, 1607, 675, 7508, 1617, 8, 2705, 1338, 9144, 7170, 1856, 6382, 851, 8096, 8913, 6290, 1862, 6280, 8703, 593, 8106, 2030, 1337, 6880, 2706, 70, 5163, 8211, 6184, 9559, 681, 2909, 5321, 6746, 7400, 1983, 4026, 7250, 1016, 6881, 7334, 8901, 4865, 862, 4901, 7576, 7400, 1305, 8394, 1050, 9487, 7502, 6297, 2519, 7175, 9044, 9523, 1532, 8466, 494, 9039, 6234, 6697, 5776, 2679, 2387, 9751, 6527, 1772, 6866, 4160, 3393, 1863, 4727, 7106, 6084, 5646, 6336, 6902, 9851, 3807, 67, 2835, 9698, 5947, 3511, 9456, 146, 6178, 8835, 5971, 1232, 2135, 7694, 90, 5200, 5999, 2342, 389, 760, 6172, 1004, 1582, 7295, 3760, 348, 2743, 52, 6401, 1402, 5055, 4490, 3928, 24, 3376, 353, 8373, 9924, 4792, 8736, 4322, 4814, 673, 9598, 786, 2743, 3823, 4577, 9414, 2213, 3398, 7533, 7692, 4404, 6134, 4814, 5765, 663, 2836, 3601, 49, 5547, 4198, 1852, 6554, 6892, 3498, 430, 6313, 1456, 1043, 5233, 9160, 3906, 5426, 7180, 7093, 9258, 1053, 9733, 3680, 3175, 9534, 6468, 834, 7422, 11, 8722, 2058, 6796, 8221, 2912, 1813, 7959, 5167, 836, 9336, 6035, 8869, 5263, 4413, 4337, 6182, 2426, 792, 8706, 7432, 5854, 4309, 7849, 487, 5922, 8976, 6702, 8481, 2799, 3841, 5726, 8289, 8864, 4034, 9536, 1014, 7253, 7774, 7171, 5023, 5607, 9367, 9603, 8229, 8294, 9092, 9018, 8933, 669, 5478, 7507, 9576, 8967, 453, 9513, 1745, 6859, 4907, 4542, 7923, 1347, 8717, 505, 1372, 1131, 9746, 7238, 5874, 4596, 1937, 4417, 5561, 4248, 8987, 1133, 9150, 9912, 578, 6463, 5970, 6913, 9461, 8024, 7830, 493, 4201, 8271, 5376, 1157, 4805, 716, 568, 7556, 9722, 6289, 3153, 6583, 5741, 8260, 5303, 5169, 8099, 71, 3873, 1259, 7752, 2856, 643, 6968, 2443, 2147, 6436, 6663, 4473, 1286, 1846, 322, 1909, 621, 8407, 8099, 9121, 7804, 1507, 3653, 1356, 5643, 6452, 7128, 3512, 9739, 2807, 5711, 6598, 631, 4764, 4772, 753, 9382, 1866, 1164, 595, 8652, 1932, 9780, 6744, 3472, 7980, 3754, 429, 5401, 4555, 2697, 3940, 7025, 4474, 7420, 1992, 6059, 1336, 7827, 4695, 3617, 9416, 8835, 7776, 5142, 5085, 3960, 6618, 5851, 4021, 2582, 2607, 8669, 4912, 2861, 6740, 1563, 5500, 5371, 246, 6805, 9023, 1851, 466, 5440, 4911, 7835, 640, 5478, 7073, 219, 9933, 9002, 2396, 2273, 8420, 2041, 8985, 6698, 3753, 1532, 8234, 2091, 4610, 4842, 1604, 853, 3362, 586, 6170, 1687, 9810, 7815, 7959, 3438, 7870, 4108, 9112, 4151, 7610, 9070, 3315, 9572, 7439, 3529, 5560, 7693, 326, 1906, 2499, 4590, 8960, 2460, 4043, 7135, 6640, 9079, 9546, 9857, 8869, 3730, 9721, 3603, 1143, 433, 6152, 148, 8749, 4314, 5575, 7507, 6409, 8425, 4099, 3155, 8865, 3907, 2720, 9402, 219, 7943, 6224, 1081, 660, 6832, 2925, 4501, 3789, 8696, 5337, 5508, 7314, 8647, 8111, 3043, 2984, 3625, 7621, 1668, 9011, 2989, 5265, 4901, 1425, 6457, 9189, 7835, 1222, 4507, 2728, 5454, 6117, 9531, 9091, 9629, 5432, 4844, 548, 6483, 7693, 1089, 4146, 4305, 8301, 5676, 1198, 7627, 9673, 4417, 7027, 3487, 9427, 7962, 442, 9343, 2262, 4596, 940, 6128, 579, 3254, 6724, 2155, 7898, 1745, 2240, 1201, 7265, 4931, 2292, 3195, 4644, 4422, 3915, 4303, 8713, 3205, 3916, 1422, 1358, 1167, 1397, 4059, 7026, 4164, 502, 1558, 7501, 3244, 396, 3206, 2876, 1095, 6024, 2870, 1597, 1599, 5628, 182, 259, 4457, 7505, 2754, 7686, 4955, 6040, 4015, 9899, 359, 9323, 6306, 5340, 3766, 5375, 5755, 2739, 7088, 8281, 8686, 520, 5207, 666, 4242, 2740, 1475, 6936, 1042, 2370, 2008, 2970, 5026, 2961, 6804, 9727, 3963, 9928, 6740, 7900, 7175, 6343, 7766, 6928, 1289, 5909, 6825, 310, 6995, 5244, 8017, 4183, 2763, 1229, 9687, 6825, 8247, 8608, 9741, 5959, 4933, 6733, 1663, 366, 5431, 2640, 1141, 2946, 1452, 3597, 8901, 7291, 298, 4384, 8357, 7711, 3399, 9103, 750, 1581, 4535, 110, 1916, 5491, 5264, 7967, 5730, 4045, 2121, 3012, 6202, 2987, 1041, 4274, 4394, 5021, 5196, 1188, 8482, 3822, 3319, 1257, 6226, 9770, 6781, 7019, 7193, 3468, 9234, 1357, 7544, 7753, 8684, 3392, 7220, 7843, 7778, 9778, 3403, 9419, 3085, 4707, 1822, 3126, 6411, 1477, 6188, 9530, 6194, 1776, 3247, 5350, 289, 6416, 4511, 9532, 6770, 4972, 4021, 3931, 7116, 8483, 3691, 9981, 3269, 9572, 8158, 2009, 7925, 6282, 5365, 2134, 4022, 7858, 5804, 862, 7991, 6779, 9129, 4378, 9791, 9033, 159, 4736, 7374, 5350, 1105, 3333, 5327, 2214, 1214, 3488, 7226, 437, 474, 4061, 2183, 1247, 7214, 3787, 7629, 8731, 6182, 8163, 1800, 101, 280, 7557, 2632, 7735, 2868, 4240, 2086, 8211, 3959, 1758, 2578, 9263, 8442, 7002, 3527, 6686, 4439, 9327, 9632, 4519, 1243, 9902, 7029, 8580, 2007, 4475, 2173, 9610, 4721, 1541, 3911, 6975, 5127, 352, 4964, 5773, 3011, 609, 6715, 6801, 3498, 4997, 4336, 9424, 9007, 3102, 7039, 4648, 6949, 3899, 6642, 9902, 5425, 243, 9458, 7785, 7597, 9182, 2555, 6121, 2537, 2864, 4440, 3349, 9885, 2515, 7789, 4945, 3513, 6464, 7715, 1624, 9597, 6793, 8829, 1820, 5172, 5910, 4938, 231, 7419, 7738, 8468, 2348, 8416, 1137, 149, 7615, 8870, 4777, 3081, 9518, 7108, 9785, 5646, 3915, 4861, 722, 1303, 9079, 9514, 5505, 4529, 252, 5395, 8638, 3325, 6551, 5054, 5525, 7756, 6736, 9646, 9294, 5097, 2967, 5516, 6267, 7055, 5709, 2675, 6478, 9563, 7372, 3749, 7556, 6173, 4324, 6635, 2849, 7544, 3875, 8778, 5065, 1673, 4944, 6001, 5432, 5620, 1205, 8655, 4832, 4825, 5014, 3089, 6205, 4182, 9986, 6329, 5862, 182, 229, 1130, 5986, 3703, 2631, 9808, 2387, 281, 7749, 5453, 9988, 1763, 9290, 6269, 1003, 2303, 233, 4283, 171, 3285, 986, 9084, 3834, 3686, 2655, 681, 6153, 543, 8081, 5915, 5669, 2925, 4188, 7375, 6488, 4415, 1971, 8233, 5805, 4647, 322, 8900, 9791, 4571, 3086, 9223, 8988, 6440, 4779, 3124, 2907, 774, 9050, 3242, 4007, 1494, 3900, 2890, 4695, 9927, 1672, 3702, 1468, 6409, 357, 1413, 2726, 761, 4581, 8132, 1811, 9834, 6462, 8294, 1461, 3717, 2101, 8876, 1407, 7687, 7689, 3008, 5548, 9977, 9946, 3803, 2860, 2013, 7668, 6471, 1739, 1684, 7660, 3614, 3776, 3916, 4389, 8673, 6175, 6407, 2943, 3765, 2347, 3799, 4974, 8647, 2892, 3925, 4546, 4576, 5128, 960, 5592, 7828, 1057, 4995, 8796, 1749, 2972, 1087, 761, 5700, 4041, 5560, 2943, 1143, 6068, 2908, 1360, 3926, 7990, 6637, 4055, 3104, 968, 5600, 3141, 522, 8502, 830, 1913, 6439, 9484, 3176, 2284, 7908, 2960, 3063, 4406, 4650, 3947, 2289, 2016, 1942, 133, 7544, 2327, 1637, 9676, 9836, 9449, 1577, 2609, 7713, 3584, 6025, 4815, 4795, 7128, 8052, 3000, 5814, 9215, 6614, 6990, 5074, 1016, 3011, 4651, 5227, 8235, 7264, 9918, 9030, 7053, 3121, 6547, 9832, 9447, 1757, 2205, 8897, 4341, 3197, 2626, 8773, 5870, 8164, 6691, 5499, 4843, 5321, 183, 3039, 4694, 31, 1459, 4114, 3825, 1621, 88, 7633, 7167, 7065, 7945, 5219, 5715, 1272, 5655, 3355, 7011, 5105, 1674, 62, 3592, 4135, 8926, 7166, 1461, 3589, 9897, 4373, 6994, 1611, 3317, 3742, 6244, 6599, 734, 4860, 3498, 3983, 5913, 3518, 6742, 5739, 1150, 8730, 3895, 2960, 5748, 918, 8431, 9014, 5128, 6327, 773, 2779, 330, 1600, 8602, 8672, 1412, 3276, 9664, 9489, 5031, 150, 7163, 2754, 3987, 7733, 5416, 1285, 6851, 3110, 6421, 2777, 51, 8705, 4268, 4940, 2608, 1006, 4175, 96, 1082, 9424, 3105, 2540, 4712, 9663, 8735, 1001, 9592, 8548, 4138, 1869, 6897, 9101, 4977, 9989, 2007, 1600, 143, 2250, 8074, 1388, 5182, 3270, 1324, 4027, 6007, 5392, 9789, 4084, 2088, 6484, 8325, 8398, 5344, 5678, 8013, 7758, 3130, 8676, 8458, 8609, 1075, 6387, 7703, 1893, 2425, 8146, 4621, 9329, 4003, 6819, 5298, 3894, 9287, 9704, 6524, 1981, 7996, 9586, 400, 4047, 1741, 9652, 5852, 9347, 8101, 7014, 7293, 1762, 9869, 997, 9197, 1831, 8160, 6056, 476, 9251, 5976, 5694, 7466, 5293, 4183, 8179, 9967, 390, 5779, 4162, 7431, 3369, 2782, 4627, 2062, 9441, 8977, 7525, 6323, 8982, 8645, 3127, 9916, 6447, 8446, 1297, 8262, 5435, 3173, 9920, 4550, 9691, 5568, 3950, 2369, 9479, 8992, 3647, 6885, 2801, 3558, 4663, 6754, 7126, 4978, 7834, 649, 5376, 2730, 3516, 2543, 9208, 8964, 2391, 429, 4681, 9185, 3050, 9032, 7360, 2165, 3646, 4616, 8528, 5655, 6260, 8839, 5443, 9937]
Selection Sort Average Time: 1.1234103E7
Bubble Sort Average Time: 8068029.8
Merge Sort Average Time: 340483.7
Insertion Sort Average Time: 10687.7

Sort Counters

public class sortSteps {

    
    // selection sort
    public static void selectionSort(int[] arr) {
        int selectionCompare = 0;
        int selectionSwap = 0;
        System.out.println("Selection Sort");

        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) { 
                selectionCompare ++; // comparing two values
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
                selectionSwap ++; // swapping two values 
            }
        }
        System.out.println("Number of Comparisons: " + selectionCompare);
        System.out.println("Number of Swaps: " + selectionSwap + "\n");
    }

    // bubble sort
    public static void bubbleSort(int[] array) {
        int bubbleCompare = 0;
        int bubbleSwap = 0;
        System.out.println("Bubble Sort");

        int n = array.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                bubbleCompare ++; // comparing two values 
                if (array[j] > array[j+1]) {
                    // swaps array[j] and array[j+1]
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    bubbleSwap ++; //swapping two values
                }
            }
        }
        System.out.println("Number of Comparisons: " + bubbleCompare);
        System.out.println("Number of Swaps: " + bubbleSwap + "\n");
    }

    // merge sort
        static int mergeCompare = 0;
        static int mergeSwap = 0;
    public static void mergeSort(int[] arr, int left, int right) {
        
        // System.out.println("Merge Sort");

        if (left < right) {
            mergeCompare++;
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        
        while (i <= mid && j <= right) {
            mergeCompare++;
            mergeCompare++;
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];

            } else {
                temp[k++] = arr[j++];
            }
        }
        mergeCompare++;
        
        while (i <= mid) {
            mergeCompare++;
            temp[k++] = arr[i++];
        }
        mergeCompare++;
        
        while (j <= right) {
            mergeCompare++;
            temp[k++] = arr[j++];
        }
        mergeCompare++;
        
        for (i = left; i <= right; i++) {
            mergeSwap++;
            arr[i] = temp[i - left];
        }
        // System.out.println("Number of Comparisons: " + mergeCompare);
        // System.out.println("Number of Swaps: " + mergeSwap + "\n");
    }

    // insertion sort
    public static void insertionSort(int[] arr) {
        int insertionCompare = 0;
        int insertionSwap = 0;
        System.out.println("Insertion Sort");

        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
                insertionSwap++;
                insertionCompare++;
            }
            insertionCompare++;
            if (j + 1 != i) {
                arr[j + 1] = key;
                insertionSwap++;
            }
        }
        System.out.println("Number of Comparisons: " + insertionCompare);
        System.out.println("Number of Swaps: " + insertionSwap + "\n");
        
    }


    public static void main(String[] args) {
        int[] arr0 = new int[5000];
        Random randNum = new Random();
        for (int i = 0; i < 5000; i++) {
           arr0[i] = randNum.nextInt(10000);
        }
        System.out.println("Random numbers = "+Arrays.toString(arr0));

        // int arr1[] = new int[arr0.length];
        // System.arraycopy(arr0, 0, arr1, 0, 5000);
        // int arr2[] = new int[arr0.length];
        // System.arraycopy(arr0, 0, arr2, 0, 5000);
        // int arr3[] = new int[arr0.length];
        // System.arraycopy(arr0, 0, arr3, 0, 5000);
        // int arr4[] = new int[arr0.length];
        // System.arraycopy(arr0, 0, arr4, 0, 5000);

        int arr1[] = Arrays.copyOf(arr0, 5000);
        int arr2[] = Arrays.copyOf(arr0, 5000);
        int arr3[] = Arrays.copyOf(arr0, 5000);
        int arr4[] = Arrays.copyOf(arr0, 5000);


        // selection sort
        selectionSort(arr1);

        // bubble sort
        bubbleSort(arr2);

        //merge sort
        System.out.println("Merge Sort");
        mergeSort(arr3, 0, arr3.length - 1);
        System.out.println("Number of Comparisons: " + mergeCompare);
        System.out.println("Number of Swaps: " + mergeSwap + "\n");

        // insertion sort
        insertionSort(arr4);
    }
    
    
}
sortSteps.main(null);

Random numbers = [2138, 2019, 3836, 5040, 2166, 9757, 5629, 3312, 5669, 102, 544, 487, 3929, 2353, 6979, 4837, 4887, 6758, 889, 7515, 3734, 7682, 2194, 1750, 6022, 8474, 9778, 4854, 6717, 3629, 4227, 410, 940, 6886, 1046, 3946, 8497, 2635, 9413, 2881, 9542, 6901, 8036, 8900, 390, 9388, 22, 1635, 8400, 9726, 6284, 4619, 8132, 59, 5384, 1894, 2074, 1728, 1968, 8128, 2546, 5295, 4685, 5830, 4918, 8407, 5955, 5965, 2747, 1973, 4363, 1037, 7350, 2343, 4076, 8920, 1372, 696, 3673, 5098, 6914, 7197, 8036, 94, 3459, 5883, 6703, 5547, 4720, 3363, 19, 9098, 4049, 5436, 1722, 6277, 5434, 8347, 9094, 4797, 3129, 4929, 21, 5736, 9851, 800, 9404, 293, 1742, 9195, 4384, 6381, 9857, 8394, 2915, 5592, 6712, 3943, 4540, 9577, 364, 104, 2655, 984, 2255, 2633, 3036, 4361, 2413, 3845, 6740, 4638, 78, 1889, 4965, 1606, 7624, 7893, 3078, 3376, 9809, 1688, 8078, 2000, 3569, 3415, 7135, 1805, 8934, 5537, 2016, 6196, 2930, 9810, 5929, 4685, 9039, 6954, 6343, 1448, 499, 2905, 4271, 1155, 2878, 1818, 6735, 6235, 224, 6361, 7088, 9820, 1240, 7810, 5864, 1080, 8631, 2808, 2076, 7808, 8162, 2974, 8994, 4769, 8198, 3717, 3332, 4909, 4214, 435, 5713, 9125, 2064, 6396, 6893, 7681, 7903, 3760, 9609, 4780, 3865, 5729, 2957, 6014, 8424, 6623, 8466, 8455, 5765, 8337, 7340, 2325, 2192, 2994, 9316, 1219, 412, 1622, 708, 7134, 6264, 6248, 4140, 5684, 8761, 5553, 6146, 9515, 6082, 3239, 9477, 3212, 2406, 9216, 2178, 8954, 3444, 9281, 4031, 5331, 4032, 5447, 7813, 2818, 6083, 7201, 9596, 8621, 8393, 8872, 6846, 9794, 6664, 7565, 8525, 2825, 2624, 589, 8240, 2502, 8478, 7523, 9288, 9071, 394, 3626, 8770, 5684, 5553, 5837, 325, 2959, 5709, 4222, 6282, 1897, 1247, 6607, 6892, 7285, 2031, 3472, 1445, 6366, 8666, 6869, 6168, 9945, 7610, 7379, 7373, 3494, 4468, 5912, 2534, 1673, 5771, 8244, 8241, 1647, 4962, 4471, 3814, 3055, 6286, 4744, 8992, 9806, 1033, 2240, 8744, 4127, 3827, 6065, 7949, 5509, 6147, 9558, 5680, 5126, 6092, 792, 7212, 2255, 9115, 1465, 9059, 7118, 9340, 8465, 7731, 6256, 316, 9315, 439, 9351, 6568, 12, 5946, 7751, 9781, 2567, 8582, 7885, 8105, 1663, 107, 1916, 5975, 1634, 7531, 7366, 8488, 7038, 7233, 1604, 436, 588, 6210, 50, 3649, 3158, 5516, 890, 9650, 6245, 6924, 8587, 2592, 2427, 1436, 4709, 3782, 6986, 648, 9172, 7846, 8031, 9745, 7111, 4089, 2511, 9819, 3612, 6100, 780, 193, 890, 9382, 3107, 553, 9274, 7005, 1094, 6033, 6946, 4217, 4561, 9176, 6415, 2232, 2315, 8378, 2271, 6657, 1659, 8547, 1769, 7564, 1220, 981, 9, 6862, 7439, 3813, 1628, 2482, 2195, 1487, 404, 9843, 2916, 1146, 120, 2310, 7589, 7909, 9020, 7556, 155, 417, 2616, 1398, 3663, 1929, 6599, 3929, 1295, 603, 5103, 977, 7763, 2939, 136, 3465, 1399, 6477, 9434, 8968, 5162, 9775, 4535, 4879, 3697, 4457, 5266, 79, 7512, 3997, 5307, 6488, 2806, 1801, 8521, 8796, 1884, 5147, 306, 131, 2459, 3300, 4330, 1063, 3071, 8901, 5189, 943, 6267, 7350, 7050, 1432, 7282, 3142, 4103, 6639, 1567, 1660, 5003, 8172, 2962, 6172, 5156, 185, 3208, 3589, 4694, 9344, 693, 1239, 8628, 4162, 1873, 3426, 9838, 6803, 4732, 8569, 3975, 5443, 4847, 9589, 8337, 6616, 3601, 4631, 3783, 7207, 1858, 7557, 2311, 6529, 5560, 7542, 1003, 2922, 3171, 6232, 2579, 5205, 8175, 4062, 3744, 9195, 6262, 1000, 2463, 7722, 2015, 3914, 976, 6410, 1831, 1838, 8786, 7115, 2298, 9670, 4124, 9242, 9166, 9193, 6443, 498, 6109, 367, 1923, 1263, 3677, 7416, 1940, 3710, 7501, 6294, 5291, 8817, 8126, 4555, 6369, 7806, 8379, 28, 5348, 5991, 6215, 6021, 6240, 8500, 3122, 2999, 4186, 5916, 4375, 3388, 4137, 9171, 8869, 9627, 753, 333, 4344, 9831, 7677, 6561, 1300, 4914, 7001, 2313, 7517, 2607, 3993, 2773, 5733, 516, 7913, 3039, 9699, 5022, 3793, 2409, 7804, 1007, 2293, 6050, 353, 5714, 9223, 4072, 6853, 6767, 3769, 5592, 8041, 5978, 1491, 3073, 9862, 3270, 1549, 5366, 2583, 3015, 4058, 2114, 2512, 3157, 4449, 1637, 2894, 60, 5736, 3645, 3213, 2625, 5776, 3952, 3552, 8399, 2680, 3797, 4432, 5438, 2990, 9923, 6916, 5333, 1161, 7537, 5706, 4375, 4236, 2477, 7871, 9353, 3543, 1656, 929, 1315, 2400, 3278, 7518, 3237, 9210, 8659, 4600, 4001, 5871, 937, 8183, 9798, 6495, 3599, 1915, 2957, 8213, 8931, 8029, 3260, 8322, 9687, 1841, 2407, 3801, 4929, 459, 7991, 7190, 3869, 6970, 2659, 9292, 8846, 1925, 8954, 4441, 8049, 9953, 8771, 6328, 3186, 8876, 4428, 7987, 6328, 7433, 6462, 6386, 8971, 9592, 5810, 4676, 9270, 9361, 5453, 9497, 8583, 2077, 5718, 6491, 3956, 4162, 9976, 1031, 9911, 5209, 3218, 6091, 6778, 8781, 6828, 2573, 590, 8610, 3749, 1557, 3733, 5263, 199, 4232, 9616, 1273, 7212, 5875, 4674, 6718, 2922, 1648, 8163, 9067, 9961, 2568, 6400, 2906, 4966, 6389, 3360, 4764, 3696, 1426, 6658, 7535, 4095, 6354, 9922, 7964, 5748, 3626, 4650, 1583, 1148, 1868, 2501, 1588, 1486, 193, 5535, 203, 8676, 1170, 8664, 1975, 7782, 9362, 2023, 9816, 9409, 428, 6267, 8771, 4823, 5012, 4669, 1355, 8912, 125, 5473, 3167, 7855, 8647, 2603, 7488, 4015, 8850, 7439, 5580, 9324, 2995, 465, 716, 5182, 7986, 3130, 150, 6399, 830, 764, 864, 5662, 6925, 1405, 5666, 3676, 8340, 831, 9622, 7668, 8656, 4016, 9231, 6072, 2878, 301, 9427, 6342, 3789, 3025, 5127, 7465, 5166, 4171, 6198, 4316, 6645, 8622, 8812, 2617, 2911, 5923, 1813, 1008, 5167, 169, 9597, 4659, 1639, 2860, 6068, 5278, 399, 8050, 3520, 2852, 4661, 834, 6095, 9316, 178, 6272, 4119, 3210, 1797, 6867, 1292, 5554, 3534, 9368, 8414, 2840, 9513, 1551, 7883, 4043, 3844, 4499, 2744, 240, 4959, 2136, 1752, 8434, 9727, 3500, 9126, 5655, 559, 7535, 2613, 6941, 5653, 2271, 7906, 8723, 3084, 492, 9970, 4453, 8594, 9051, 6349, 6576, 6096, 1990, 1639, 1139, 5793, 6912, 2807, 6982, 8737, 7399, 838, 1940, 3508, 1922, 4085, 9780, 9073, 2425, 3995, 3622, 4889, 6531, 1514, 8712, 2775, 4394, 8093, 2168, 5925, 5692, 1088, 1348, 5256, 3739, 5516, 9661, 7962, 1540, 1822, 330, 5650, 3405, 6402, 8761, 4786, 4582, 1217, 9184, 3741, 1426, 4964, 2802, 8515, 2752, 9172, 9661, 1402, 6065, 7984, 7024, 5114, 1198, 9466, 1097, 8277, 5010, 9055, 3020, 9506, 4098, 8384, 6448, 5333, 2718, 2817, 324, 9164, 8223, 9342, 6031, 1112, 1008, 9861, 1317, 1190, 9625, 8148, 7845, 5433, 3094, 5776, 8063, 8886, 7974, 1935, 3411, 1388, 4783, 3346, 597, 7822, 7327, 3907, 1052, 9582, 702, 1687, 665, 9111, 5391, 3359, 6469, 8103, 7813, 929, 7508, 3943, 370, 366, 6325, 9321, 2059, 3344, 7947, 7821, 1143, 6386, 9174, 9616, 6838, 1132, 2330, 9057, 78, 8633, 2594, 5953, 6353, 5303, 5293, 5431, 3883, 1930, 8790, 4221, 2551, 9261, 3281, 7306, 2240, 1734, 7889, 1581, 4053, 437, 6887, 8563, 7830, 5337, 2934, 5605, 3291, 4239, 2641, 3041, 3636, 2631, 549, 1714, 8091, 5541, 3891, 3135, 2390, 9553, 1333, 7774, 3224, 476, 754, 3427, 7815, 4912, 2381, 249, 9848, 5858, 520, 1931, 5702, 9110, 4742, 5903, 4050, 6543, 7261, 7967, 1556, 2898, 8058, 4438, 4576, 9205, 2335, 5428, 7140, 3546, 1144, 7758, 7086, 6834, 4731, 741, 8970, 7904, 2813, 6833, 5464, 4251, 6929, 3577, 4924, 366, 955, 3970, 7535, 4272, 9395, 9634, 515, 844, 9797, 2943, 9540, 3532, 7605, 8313, 8522, 6231, 2240, 2561, 9355, 9364, 7054, 1269, 9933, 8793, 8564, 6937, 7129, 6661, 1254, 2659, 2075, 1110, 2857, 4434, 9206, 2775, 9606, 2188, 8325, 490, 9482, 5827, 4348, 6254, 1066, 1556, 5740, 2157, 3700, 7868, 2293, 7493, 321, 2230, 3014, 897, 2775, 9381, 544, 3731, 5931, 6827, 8424, 224, 7763, 4884, 6763, 8872, 7866, 3426, 125, 5280, 844, 4805, 5514, 3934, 4769, 9446, 4285, 4048, 8423, 561, 5759, 4922, 3591, 2173, 710, 2170, 474, 9290, 5759, 1049, 1093, 3349, 9223, 5937, 9023, 2554, 8563, 6837, 9331, 9847, 9983, 8178, 4721, 6585, 1715, 8640, 9646, 3206, 6978, 8372, 7932, 9126, 4348, 2182, 6517, 4126, 500, 569, 9137, 6026, 1771, 5244, 4247, 1015, 2891, 6365, 7551, 2202, 9776, 7269, 3094, 720, 7968, 9571, 2187, 6851, 7644, 57, 8486, 6966, 7694, 6941, 1512, 2622, 5202, 5437, 2638, 3261, 465, 5427, 8095, 3211, 5097, 7632, 7541, 1939, 8392, 5799, 5784, 2519, 2455, 5113, 197, 3793, 7092, 6697, 1102, 72, 999, 3228, 3756, 1739, 3254, 7183, 6911, 4525, 2388, 8196, 2166, 1581, 9492, 3018, 6729, 64, 9691, 5095, 531, 2269, 6147, 1653, 9646, 7381, 8060, 1399, 983, 1774, 5854, 7095, 7888, 9530, 2553, 8093, 7252, 3784, 5293, 2093, 6197, 7719, 1829, 3166, 8401, 6178, 5598, 8963, 5283, 6589, 8150, 8392, 6886, 1851, 6320, 8346, 9284, 105, 9300, 5074, 749, 1402, 530, 64, 7171, 9535, 7719, 193, 6482, 6499, 5704, 8861, 7773, 9888, 4827, 5823, 2691, 3698, 7894, 6706, 6097, 9142, 5327, 4164, 5777, 1967, 6050, 5241, 9584, 8069, 5249, 1247, 5693, 9641, 1301, 7562, 6669, 7034, 8355, 3979, 3003, 9405, 1242, 3521, 844, 3709, 7401, 140, 8561, 1887, 3022, 7418, 6647, 5376, 1208, 4257, 2616, 7453, 4878, 8008, 1332, 351, 4152, 1426, 7162, 705, 9067, 4855, 4527, 1759, 5139, 6352, 5474, 669, 1576, 6175, 8742, 6497, 8355, 489, 8846, 5598, 4282, 8561, 1240, 382, 1751, 2515, 1776, 5002, 2887, 3081, 6629, 8425, 4782, 1917, 4296, 9124, 3271, 8988, 4608, 5650, 297, 8467, 6555, 4005, 7446, 4809, 2815, 63, 1277, 5705, 7535, 1762, 5375, 3994, 6153, 5043, 7214, 6044, 6764, 2314, 5154, 8257, 4134, 1641, 3717, 3286, 8764, 2023, 6894, 397, 3283, 935, 7131, 217, 59, 4522, 2391, 3460, 1659, 5565, 667, 4864, 9079, 1392, 7633, 40, 3678, 53, 4675, 8563, 6976, 5201, 2562, 5573, 3965, 8594, 5779, 801, 1400, 9197, 7859, 3406, 2411, 7491, 9083, 7701, 996, 2607, 3519, 2628, 6317, 9503, 5777, 499, 650, 9740, 7283, 8385, 6651, 2135, 5465, 1849, 3792, 5538, 1628, 6535, 7836, 9625, 8490, 400, 947, 3211, 3019, 6227, 3837, 2377, 1951, 4315, 8460, 7689, 6787, 2958, 3530, 6343, 3043, 9189, 9164, 8073, 5385, 3287, 8371, 7821, 7603, 6452, 6769, 7170, 2579, 9772, 4392, 1440, 7936, 4714, 2926, 7429, 3145, 7008, 877, 9724, 4698, 2816, 4359, 6396, 4151, 5891, 8598, 7962, 7989, 5818, 1121, 2540, 1448, 3744, 7595, 1196, 3159, 6168, 2822, 7253, 9964, 7383, 6133, 8525, 7703, 2016, 4271, 2174, 6034, 457, 1455, 2674, 9759, 311, 2151, 9643, 5102, 4762, 3589, 525, 1259, 5207, 4638, 3017, 532, 1726, 551, 1894, 8840, 6103, 1987, 2718, 7994, 8990, 9639, 9250, 9221, 8760, 2553, 2475, 1305, 9441, 9046, 5662, 6548, 452, 8610, 1419, 7373, 1094, 1514, 9939, 5065, 7535, 8758, 3507, 4032, 2790, 43, 6257, 3273, 6408, 9693, 5010, 7474, 4740, 9281, 6069, 8828, 4102, 5552, 288, 6275, 2702, 9863, 2533, 9036, 3148, 7595, 7440, 7559, 4043, 7611, 2176, 931, 1015, 1310, 639, 8673, 4396, 635, 3200, 8464, 1468, 199, 6292, 8279, 4941, 584, 8649, 9890, 829, 24, 7488, 7044, 9426, 7846, 7577, 9115, 8770, 6727, 7261, 9968, 1404, 6714, 4744, 2445, 7410, 6872, 193, 6218, 5780, 9850, 6887, 640, 2889, 1957, 7449, 9086, 5948, 8832, 146, 698, 6401, 678, 1328, 9711, 5219, 7655, 6048, 9572, 4347, 7017, 8967, 2558, 1055, 8556, 2207, 9308, 9524, 2218, 3484, 1519, 4722, 1117, 6010, 2573, 4291, 8731, 5925, 8747, 4566, 3805, 6421, 1063, 8631, 9421, 2676, 584, 7763, 7357, 5020, 9325, 3434, 1749, 7442, 8514, 9366, 4564, 8265, 978, 2354, 1992, 6373, 5878, 201, 9896, 2445, 1643, 7181, 8174, 4284, 7873, 4928, 578, 3796, 9295, 9586, 4690, 8479, 6388, 8471, 9118, 8067, 5305, 3380, 4671, 3329, 3043, 5590, 6360, 5531, 9732, 3376, 3620, 5296, 6721, 3023, 7903, 4885, 5725, 5947, 497, 7793, 5588, 2252, 1861, 6245, 6917, 1430, 5639, 534, 3463, 1939, 1340, 7704, 1324, 3564, 9324, 9097, 4850, 2275, 6570, 6456, 6022, 1216, 708, 1456, 2852, 5030, 8757, 5364, 2121, 3922, 8376, 5433, 5545, 1663, 4760, 7338, 8237, 8728, 3714, 4140, 9796, 1387, 6108, 7056, 6298, 6438, 8495, 6862, 2022, 2466, 1343, 68, 3373, 4280, 123, 2986, 4004, 8052, 6192, 9824, 7010, 9381, 7896, 2631, 4532, 8477, 719, 1753, 8731, 3499, 8135, 1991, 7808, 8259, 6321, 1997, 263, 4135, 348, 6963, 3409, 4005, 2474, 9859, 6395, 7756, 1213, 6081, 5140, 5083, 7458, 2636, 5244, 6392, 8835, 7424, 6568, 3546, 1776, 6006, 5442, 4980, 8760, 5241, 8078, 6991, 5297, 3460, 8935, 7874, 5495, 3581, 2647, 7792, 1233, 9369, 7397, 1519, 8847, 3291, 7769, 3088, 8223, 7740, 667, 3712, 1408, 3880, 6890, 5610, 4573, 2387, 8904, 5782, 5579, 4406, 7602, 162, 5246, 8330, 2414, 1052, 6277, 4880, 3101, 9497, 1798, 5274, 5296, 9125, 2916, 4297, 5062, 9800, 909, 3749, 8531, 2992, 2464, 2466, 8717, 3985, 4220, 9429, 7200, 4518, 2995, 4739, 8866, 5298, 9981, 5218, 5136, 1608, 7929, 6543, 3671, 8051, 9102, 4395, 4878, 7699, 6384, 3042, 1408, 3893, 46, 2137, 3976, 3405, 2617, 9572, 8150, 2034, 6031, 8273, 6830, 9415, 7780, 2244, 8031, 4754, 7442, 5872, 6321, 6186, 7239, 8895, 4584, 3826, 8173, 3870, 8373, 2556, 1560, 984, 1867, 3884, 5544, 4813, 2607, 4506, 8237, 3967, 8072, 979, 8874, 153, 5846, 8397, 1955, 6061, 9488, 5365, 2800, 8888, 1669, 5335, 4164, 8355, 4052, 73, 455, 8777, 5607, 2725, 9374, 8464, 5370, 2032, 2029, 4646, 3354, 4700, 1795, 538, 3960, 8006, 1811, 4259, 6492, 1917, 1219, 4193, 2086, 9424, 445, 1758, 3792, 1570, 3635, 3297, 4912, 8510, 9999, 2911, 4586, 6608, 4312, 8558, 4178, 6151, 5281, 4679, 9102, 3350, 3292, 1079, 457, 1201, 7868, 1298, 2820, 5082, 3592, 4661, 8216, 2712, 2075, 631, 6599, 3760, 3032, 4362, 5776, 51, 7450, 660, 7008, 436, 6810, 917, 6950, 3716, 3802, 5588, 5823, 7548, 4638, 4938, 7968, 7830, 1114, 2027, 1458, 4297, 3734, 7420, 3624, 9263, 1791, 293, 9228, 852, 4311, 8245, 7575, 8749, 6604, 8396, 7039, 6851, 358, 3514, 2666, 1995, 2874, 2769, 9473, 9955, 6060, 505, 6497, 6746, 4385, 9600, 6410, 7660, 7474, 8747, 8186, 5898, 7292, 7278, 7716, 7330, 5573, 388, 1098, 6288, 2409, 6140, 2186, 7105, 4322, 4368, 4643, 7775, 8358, 5443, 4233, 2926, 2618, 8294, 5854, 4017, 6789, 6886, 8897, 954, 9183, 7462, 8499, 7261, 6312, 2245, 9731, 7071, 9989, 3980, 3436, 2512, 3429, 4966, 2020, 6226, 4161, 5772, 4325, 3109, 7570, 8780, 1081, 2897, 6541, 5701, 286, 1039, 9161, 2194, 281, 7253, 5841, 6321, 3990, 7660, 7269, 7374, 3518, 9999, 6747, 2337, 1777, 3681, 3859, 5632, 5363, 7195, 4664, 2962, 4355, 9842, 7058, 6418, 4198, 2001, 1416, 8076, 2291, 344, 2818, 2663, 8151, 4017, 2061, 4303, 5800, 5434, 9752, 3981, 4375, 3236, 7724, 2166, 9887, 8647, 8, 5773, 5306, 7152, 6938, 3525, 1426, 5432, 1113, 5048, 8645, 754, 6671, 8621, 6273, 2000, 9908, 8777, 6559, 6514, 2742, 5013, 1069, 6829, 5573, 423, 7107, 724, 5226, 7520, 4503, 2758, 7272, 9137, 9996, 6387, 171, 7611, 9221, 3100, 7308, 4802, 1144, 3510, 1334, 4620, 1389, 3243, 8131, 1132, 9286, 1421, 336, 6790, 4456, 8616, 9648, 4942, 727, 7331, 8988, 2738, 3616, 4146, 6983, 6096, 9375, 6411, 2687, 2517, 5857, 9746, 8991, 5364, 4980, 6756, 4306, 3439, 6107, 9644, 8691, 1028, 6318, 7702, 560, 7, 2366, 2238, 5100, 1512, 8997, 356, 9763, 3377, 3708, 574, 2936, 4431, 6854, 2809, 1418, 794, 6698, 5230, 6694, 2466, 830, 1101, 2150, 248, 4542, 3977, 4151, 9670, 7132, 4016, 6488, 3244, 5346, 8340, 2654, 488, 3235, 5659, 6773, 4369, 1583, 432, 1312, 4096, 9653, 3539, 4193, 9068, 3554, 5092, 1909, 9168, 9688, 2471, 8935, 7419, 4635, 6612, 9524, 8484, 5301, 3407, 8270, 5704, 4952, 1999, 8026, 6034, 1891, 8477, 3509, 629, 702, 5226, 5811, 505, 2192, 1885, 567, 4976, 6560, 1800, 3423, 227, 8216, 4294, 6167, 4702, 8101, 8211, 1374, 9812, 2603, 7223, 8518, 7696, 3382, 225, 5364, 8362, 6043, 6029, 2791, 9490, 5612, 3393, 645, 5309, 9083, 6730, 3585, 7529, 8774, 2141, 5209, 8542, 3472, 4284, 6668, 6466, 337, 1240, 1225, 5193, 3523, 8205, 7906, 9112, 7565, 9103, 2207, 1668, 5309, 351, 3023, 2876, 3726, 330, 5226, 3936, 6714, 8446, 3730, 5580, 9816, 9625, 3095, 5637, 2646, 2240, 5833, 4334, 6690, 952, 5912, 4839, 322, 7269, 1864, 6915, 1444, 3325, 6161, 5253, 4143, 5624, 2754, 1175, 4248, 551, 4821, 8870, 5249, 8445, 7454, 2429, 1291, 190, 1229, 6924, 541, 1603, 6835, 7812, 7741, 727, 3185, 1058, 3770, 6754, 6523, 6038, 3644, 3471, 2956, 8448, 9491, 3835, 899, 5222, 2557, 5949, 8315, 1443, 9220, 9756, 4249, 5823, 5827, 9282, 8270, 9111, 7464, 2859, 8620, 8425, 8245, 5113, 2486, 1103, 5409, 4664, 2239, 229, 636, 3929, 7989, 4136, 4367, 6013, 5398, 797, 5521, 4672, 8416, 1132, 9479, 2207, 9239, 1399, 8851, 8711, 8783, 7930, 7453, 6108, 7850, 2801, 6031, 8866, 6395, 320, 2889, 9020, 9897, 6307, 3397, 319, 319, 2563, 4550, 8017, 8352, 2994, 5786, 7603, 6136, 6195, 3742, 4041, 4189, 6921, 8448, 2050, 8004, 2602, 8911, 3832, 5521, 1951, 2670, 1110, 9142, 4731, 232, 4961, 9372, 4725, 8750, 4852, 960, 2660, 8364, 2844, 532, 4983, 1577, 5596, 2310, 5470, 5789, 8270, 4286, 7256, 8893, 3463, 9105, 3194, 6401, 838, 2931, 5048, 5047, 1849, 1049, 4723, 5889, 2907, 1724, 831, 5017, 5790, 9978, 3792, 1604, 7489, 8726, 3952, 1844, 7134, 688, 7728, 7720, 4387, 2143, 153, 8622, 602, 1946, 7549, 8505, 4503, 8694, 9263, 2349, 5358, 8426, 9244, 1127, 415, 8014, 4196, 9642, 1999, 5186, 5017, 9060, 6324, 7051, 4147, 9615, 7436, 3464, 8669, 5459, 3995, 2290, 48, 121, 7167, 802, 8409, 9530, 321, 4141, 2346, 309, 4171, 9386, 9226, 3520, 9552, 4677, 537, 7622, 7149, 2348, 9237, 2943, 8218, 2853, 2482, 7165, 2716, 4738, 1833, 1906, 8154, 2893, 4432, 5999, 9658, 4398, 7266, 4584, 1400, 7196, 6794, 7219, 8050, 2160, 8673, 1567, 9859, 8101, 9810, 9873, 3594, 2507, 5798, 6281, 8150, 1995, 4914, 7395, 1280, 8308, 6201, 4153, 4997, 1476, 1902, 2407, 5551, 7618, 298, 4039, 6079, 3576, 2998, 3546, 1800, 527, 6998, 7255, 9531, 3186, 6082, 2542, 4827, 8004, 5282, 2150, 6348, 9790, 918, 1732, 7901, 8784, 5007, 4829, 6351, 4345, 8301, 5106, 5665, 9298, 9286, 8394, 9258, 3748, 9504, 2510, 1714, 4314, 651, 9758, 8541, 1105, 1694, 2609, 4100, 2907, 44, 1513, 3809, 8499, 483, 9653, 7864, 700, 1249, 1024, 3693, 6386, 9011, 9239, 2550, 4273, 7179, 3735, 3982, 7348, 4957, 6837, 1666, 7030, 8838, 4231, 3627, 9973, 9546, 3487, 2553, 7668, 1401, 3384, 2377, 2239, 972, 4601, 6979, 2698, 3458, 7351, 9458, 5362, 2978, 680, 7520, 4341, 5116, 2865, 7422, 2285, 816, 5648, 7981, 9495, 2170, 934, 8876, 1202, 4265, 2444, 686, 9011, 6219, 7110, 5927, 3973, 2983, 8133, 9395, 9838, 3702, 7655, 5923, 5773, 9246, 9449, 4661, 640, 7757, 5148, 9822, 482, 3982, 9429, 5703, 3312, 811, 2159, 865, 3357, 6912, 9659, 1223, 1339, 5687, 4279, 3407, 874, 4182, 4797, 2316, 5454, 6673, 9778, 3091, 3576, 9820, 3775, 4423, 4135, 2642, 9580, 4451, 8311, 1835, 6760, 804, 1287, 7325, 6774, 9409, 9800, 4098, 8417, 8023, 7026, 6194, 4639, 149, 9873, 4845, 7124, 3105, 1932, 4647, 8990, 4022, 5862, 8672, 9725, 7835, 4813, 3519, 1717, 6608, 5424, 5547, 5596, 9463, 382, 2789, 9742, 157, 5609, 8757, 1393, 6388, 1866, 495, 2450, 8334, 1582, 4209, 5950, 9656, 365, 6365, 4589, 2945, 2347, 4254, 8920, 1125, 1560, 280, 7611, 2826, 6514, 2161, 8214, 3158, 682, 3013, 3981, 6443, 2052, 4379, 4304, 8465, 5767, 4642, 7797, 6670, 757, 4742, 1664, 4900, 4405, 1653, 1396, 8919, 1820, 985, 8980, 8249, 1818, 2050, 7139, 4660, 4176, 4817, 3273, 5284, 6079, 5203, 6118, 1102, 8443, 3736, 9553, 177, 4959, 735, 6570, 9224, 5259, 64, 3614, 936, 3928, 5509, 7256, 3228, 395, 6006, 292, 7611, 6392, 400, 2319, 9843, 8350, 4577, 8842, 3844, 8128, 1202, 7421, 2123, 6980, 1889, 7929, 5833, 9428, 842, 8934, 2528, 6834, 3490, 7611, 1082, 2089, 6032, 7179, 4085, 6494, 5848, 7276, 4671, 389, 8550, 5156, 2618, 5920, 2147, 7260, 8123, 6227, 1174, 390, 6517, 482, 5562, 5835, 2494, 6475, 9448, 1997, 2778, 5937, 9281, 779, 5052, 173, 3706, 6211, 4246, 8697, 9317, 1505, 8872, 1191, 7992, 4118, 493, 5131, 4044, 1652, 2494, 1898, 8339, 4166, 1537, 7578, 6807, 7868, 5666, 312, 4363, 1907, 6716, 2953, 5457, 8963, 7475, 8792, 3592, 1763, 6753, 1006, 6510, 4727, 5516, 7968, 3674, 1897, 4769, 8274, 4879, 6166, 6911, 1162, 8734, 2895, 8706, 7279, 2907, 9391, 2058, 3311, 2521, 29, 8135, 640, 5669, 6071, 611, 3102, 6156, 4542, 4541, 1123, 538, 1857, 1005, 9989, 1328, 9106, 3833, 7434, 3265, 4340, 6307, 5606, 265, 9270, 732, 8165, 1643, 4585, 8122, 6948, 5173, 5021, 8897, 8505, 9938, 4218, 6624, 7075, 6428, 9082, 9099, 715, 6315, 4948, 8577, 6602, 6879, 6547, 6585, 4853, 5606, 133, 9502, 6004, 5722, 4671, 3812, 3312, 4554, 8014, 3893, 1562, 6083, 4408, 6509, 3800, 8907, 8385, 7710, 5562, 1786, 9082, 5713, 8571, 5574, 6995, 8218, 467, 7993, 1537, 7686, 5417, 5393, 8955, 3236, 2054, 4388, 2590, 6589, 9957, 4621, 5313, 865, 2294, 1015, 5698, 800, 2705, 7093, 4703, 9553, 7992, 4556, 5185, 3170, 7638, 846, 6723, 1661, 6115, 1492, 4688, 4820, 5641, 2151, 7722, 2201, 9953, 9243, 2439, 5324, 1126, 6536, 6582, 433, 2892, 3862, 3344, 6221, 9881, 6820, 553, 6973, 9041, 3109, 7573, 7331, 5888, 5656, 9687, 9806, 8112, 8179, 4389, 485, 1946, 5884, 456, 6897, 8921, 1011, 8271, 6660, 7546, 3150, 9714, 4745, 2863, 4882, 7956, 5000, 7267, 4796, 5458, 326, 6345, 4122, 1801, 2007, 1885, 1800, 5636, 5090, 5483, 8122, 8914, 7568, 7326, 3059, 2758, 6543, 2849, 2384, 8952, 1193, 562, 6404, 3721, 2588, 869, 2881, 3252, 1462, 8676, 8560, 3919, 3151, 6131, 2525, 4993, 8979, 7009, 6610, 6909, 874, 8459, 2541, 2717, 8614, 9195, 7969, 6442, 8873, 4431, 4503, 9607, 864, 2644, 1726, 2942, 3087, 2272, 5974, 7954, 842, 9854, 5445, 6212, 2334, 2244, 9907, 2577, 9098, 9553, 825, 2967, 2269, 4179, 4257, 3048, 1597, 7253, 3049, 3976, 6049, 7237, 4554, 9793, 1868, 1603, 5840, 5718, 3623, 3749, 7109, 3540, 6441, 695, 6942, 2067, 3285, 4848, 5889, 6188, 6992, 3712, 6449, 7846, 2894, 3894, 2856, 5225, 6553, 3598, 5393, 4835, 1804, 6632, 3743, 8600, 4914, 5091, 5469, 420, 7318, 9479, 9938, 7884, 1398, 3987, 4640, 3267, 4681, 6299, 1722, 4008, 506, 5043, 3456, 93, 8609, 8073, 4904, 114, 2476, 5580, 1275, 1808, 2127, 395, 1913, 4610, 5589, 2601, 9449, 6765, 4753, 3452, 4977, 1232, 8678, 4292, 2511, 3574, 4831, 217, 4162, 1320, 1980, 685, 6472, 96, 6249, 1360, 8868, 7561, 509, 3458, 9707, 3538, 2572, 2772, 652, 3585, 4777, 8423, 2554, 5428, 780, 8758, 7063, 3346, 4860, 6208, 3470, 4064, 2057, 5837, 6029, 7152, 6024, 6178, 2078, 4612, 7564, 8959, 2256, 144, 6429, 1061, 6710, 798, 3592, 4581, 4940, 5739, 2835, 3188, 4610, 9294, 843, 8410, 8503, 1224, 3084, 3690, 1346, 2966, 2940, 9468, 7039, 5732, 6436, 8806, 9733, 1261, 3564, 9225, 1712, 4765, 386, 1944, 9424, 3591, 855, 3107, 8685, 6018, 2870, 9057, 4037, 3006, 770, 4220, 7988, 9877, 2379, 9574, 9007, 1836, 3884, 3674, 5917, 4840, 8660, 3885, 6146, 1166, 9486, 9572, 2617, 2675, 1344, 5023, 9181, 1858, 8861, 2642, 2452, 3148, 4263, 7972, 3977, 2393, 7828, 720, 5332, 5436, 8972, 7113, 7304, 2597, 9469, 6395, 73, 7216, 2330, 1228, 4905, 5211, 1239, 4930, 2589, 4629, 8889, 4766, 3600, 7954, 1438, 213, 8724, 2635, 5161, 32, 4592, 4770, 1479, 6201, 1018, 1331, 4931, 2646, 7474, 102, 9666, 6978, 89, 2512, 317, 4550, 1565, 2090, 441, 4935, 3426, 3673, 7748, 6265, 3870, 4620, 8237, 4674, 3825, 2053, 1568, 5737, 6206, 4782, 8350, 8924, 635, 8541, 5957, 5697, 7057, 1778, 3841, 4724, 1888, 5005, 5006, 2944, 9283, 908, 3785, 7321, 715, 4674, 8018, 8645, 7402, 2836, 3648, 2859, 2095, 412, 6481, 2963, 4969, 992, 7724, 3965, 7769, 9998, 5686, 4798, 2920, 7390, 1725, 8934, 1826, 7257, 1219, 7868, 2734, 5463, 5579, 4618, 6476, 6212, 7993, 2277, 7690, 6108, 7929, 1813, 5650, 6982, 4544, 6851, 5699, 8829, 1126, 9824, 2730, 5289, 904, 2498, 8748, 477, 6713, 9705, 419, 6969, 3536, 5040, 9876, 6847, 7186, 6127, 4761, 6387, 7293, 9870, 223, 3707, 4542, 7140, 7342, 2438, 4047, 2668, 4560, 4537, 2545, 9321, 7840, 6804, 3281, 7040, 4097, 6260, 7898, 9300, 4392, 1409, 248, 3728, 9159, 5831, 7076, 9548, 406, 2866, 8113, 5010, 8448, 7619, 6865, 1067, 8488, 2160, 932, 9699, 9734, 9815, 8287, 251, 449, 770, 245, 525, 2506, 6630, 1717, 6953, 8307, 3269, 5503, 5278, 123, 6292, 5876, 5173, 744, 4967, 8425, 935, 2127, 9401, 8407, 1231, 3314, 9159, 3, 9994, 2982, 8412, 9109, 2091, 9808, 4199, 7783, 5499, 9420, 5256, 9628, 1549, 1818, 4234, 7002, 6480, 3910, 8537, 8389, 3390, 3985, 7269, 7066, 2161, 2097, 1568, 8884, 932, 1826, 9153, 1791, 6263, 6391, 9883, 7511, 7997, 7890, 6855, 1451, 2624, 9035, 8013, 8116, 6804, 4608, 2546, 124, 6745, 8217, 8955, 8861, 9210, 8935, 7152, 775, 4578, 8377, 9004, 829, 1054, 2219, 3377, 5820, 2862, 8107, 584, 4601, 1909, 6905, 2646, 8486, 6767, 4730, 7994, 1073, 9842, 8841, 1938, 4905, 9053, 3819, 1454, 4014, 6590, 7597, 4684, 8532, 4768, 9132, 1138, 1379, 7105, 2529, 6379, 335, 1329, 1623, 1960, 4831, 6358, 9002, 3336, 3531, 5933, 1950, 7730, 855, 395, 7417, 3743, 8502, 8497, 4702, 7109, 5821, 8830, 8167, 7373, 7846, 9534, 3118, 2374, 9069, 1440, 5480, 3315, 3963, 9974, 7583, 2415, 4892, 1861, 8890, 9921, 3583, 508, 2907, 5050, 9962, 9746, 6213, 4827, 7799, 9048, 3415, 8308, 9214, 6877, 2937, 6327, 5632, 4784, 9203, 3419, 7550, 3568, 2565, 8573, 3716, 5296, 1830, 4592, 7654, 5942, 524, 789, 6677, 5346, 6436, 2502, 445, 8540, 1999, 9660, 8446, 1574, 4506, 976, 7765, 1009, 7272, 3758, 103, 859, 3966, 614, 2554, 9029, 8618, 1197, 5055, 979, 3281, 3536, 4847, 8461, 1316, 9432, 7905, 275, 7918, 6761, 6646, 685, 701, 8196, 7570, 1968, 6938, 6829, 662, 540, 9974, 4470, 5486, 9090, 9203, 1818, 6740, 131, 2925, 9879, 7344, 8852, 3571, 9442, 333, 3742, 3926, 7998, 9176, 737, 5165, 4439, 247, 4233, 3345, 6009, 3028, 7688, 828, 4782, 7653, 2195, 2025, 4228, 6810, 2105, 1032, 8412, 6834, 5262, 1633, 7327, 9481, 3766, 7346, 4811, 2930, 764, 1110, 395, 5357, 2402, 8964, 5045, 7718, 7539, 3985, 7661, 810, 3604, 4099, 1191, 1638, 2042, 3876, 346, 3870, 2533, 1599, 9263, 406, 9929, 2234, 7033, 2001, 7613, 7967, 2542, 3475, 9468, 6393, 1235, 3349, 7657, 5128, 5751, 69, 5104, 4369, 2198, 3575, 4360, 6292, 3965, 2877, 3380, 3947, 7149, 5262, 168, 8877, 9992, 6837, 8393, 5708, 1305, 3673, 6445, 4817, 3152, 2389, 8514, 6721, 7979, 243, 6891, 5532, 4384, 2297, 6804, 9891, 1878, 32, 630, 1219, 9156, 4493, 5366, 1090, 2961, 2543, 2824, 8933, 2315, 1572, 2306, 3435, 3331, 7415, 7675, 4122, 9973, 522, 1986, 3780, 6213, 5227, 2730, 6325, 1397, 2439, 5987, 6636, 5859, 1816, 7316, 9604, 4943, 5004, 8660, 14, 6426, 4452, 233, 3708, 9627, 2661, 72, 1772, 1579, 6238, 5658, 5151, 8192, 4167, 8495, 8229, 2598, 6114, 4476, 9591, 57, 4769, 5424, 7937, 640, 2148, 7509, 3274, 5523, 4028, 1682, 801, 5181, 5729, 4461, 3846, 8076, 9789, 6734, 5986, 9045, 8371, 9374, 6163, 9989, 6991, 1934, 9768, 9187, 5964, 5365, 5830, 9265, 860, 1313, 1205, 3696, 1047, 9214, 2986, 1315, 3139, 1188, 6801, 1276, 8827, 554, 8918, 5763, 6400, 121, 2672, 3077, 9721, 252, 9371, 5273, 6136, 2739, 9313, 7294, 5275, 4743, 1653, 7296, 3835, 6888, 6859, 3881, 565, 674, 4151, 9204, 8131, 749, 6481, 6124, 1974, 3684, 3649, 2836, 7953, 4813, 1660, 5456, 6453, 1959, 8491, 528, 1589, 6338, 8757, 4380, 5093, 4840, 9241, 4651, 2372, 3146, 4010, 8654, 1043, 6565, 7958, 9097, 1841, 4499, 5669, 434, 3780, 6525, 2347, 3362, 710, 8590, 9913, 6696, 2202, 8707, 7063, 6653, 9721, 5759, 2838, 8850, 1214, 6907, 7493, 6757, 602, 7418, 9987, 9843, 4676, 8203, 7819, 391, 9329, 8648, 8225, 2720, 7852, 9627, 5815, 4449, 9090, 1424, 2220, 8850, 3516, 9989, 6530, 7748, 2810, 8589, 7786, 8674, 4713, 8436, 5630, 7667, 1280, 6350, 3931, 7179, 4701, 6633, 2841, 6641, 6311, 5696, 1561, 2812, 287, 8225, 9050, 7142, 3816, 4118, 3063, 6051, 6288, 2879, 753, 1722, 7306, 7281, 4644, 7938, 8170, 4216, 504, 1848, 8636, 3896, 4231, 8604, 4593, 9473, 6757, 6620, 7255, 8177, 9777, 4872, 3539, 4755, 9783, 1861, 5806, 9493, 2448, 29, 1481, 8071, 9207, 771, 9039, 4751, 8552, 5444, 918, 346, 3527, 7785, 832, 2909, 2713, 8217, 5588, 8074, 7523, 6156, 9428, 9549, 6238, 826, 4108, 3478, 388, 6561, 9894, 1457, 2906, 5141, 9836, 1713, 6617, 4626, 9739, 5899, 3658, 1118, 8096, 206, 4014, 4265, 226, 9041, 3639, 7478, 5163, 8421, 1303, 6355, 2964, 2057, 9987, 7892, 4700, 7837, 5219, 9311, 3493, 4734, 3289, 1072, 460, 2735, 5995, 156, 7923, 7257, 206, 130, 6156, 681, 8625, 4829, 6884, 4455, 4852, 6759, 5593, 7768, 84, 1800, 1466, 2553, 7140, 4636, 6714, 6412, 8616, 6418, 8608, 1663, 9969, 6928, 8525, 7751, 5152, 9956, 2859, 8092, 2921, 9158, 8399, 8574, 1686, 2201, 5435, 341, 2916, 8256, 1715, 2310, 5310, 7821, 4985, 689, 3413, 1252, 7991, 7959, 4697, 8623, 2553, 3177, 358, 4779, 3076, 6156, 4045, 8239, 9239, 329, 2254, 9548, 8844, 4449, 4303, 2640, 3291, 2877, 6636, 7493, 6060, 9635, 4331, 8567, 1654, 1556, 9738, 8242, 3609, 4099, 1447, 3657, 4613, 5088, 9372, 5523, 1237, 5378, 998, 3952, 5883, 8292, 3408, 3562, 2488, 4902, 2609, 9463, 312, 9764, 3742, 6186, 6712, 467, 1917, 7929, 4518, 7048, 903, 5673, 5716, 3923, 3785, 9701, 7879, 440, 8904, 6910, 9826, 9982, 9758, 2956, 4202, 2672, 6469, 5635, 7542, 3202, 4799, 945, 1862, 9262, 3264, 995, 6316, 4235, 4600, 9367, 2427, 4239, 9041, 1900, 4379, 4235, 6577, 6966, 7029, 9749, 7660, 3886, 7969, 2803, 9082, 2022, 698, 3379, 3232, 7658, 2171, 3768, 8110, 7394, 5881, 2622, 9172, 5396, 8268, 3934, 7378, 3062, 8842, 4509, 8378, 1809, 9506, 80, 1908, 2881, 7506, 7434, 8606, 8393, 8870, 5349, 5854, 3, 3806, 6607, 5270, 9285, 2394, 4076, 9314, 8143, 5108, 1737, 3360, 3793, 5818, 4817, 3229, 330, 8343, 2264, 9304, 6395, 3645, 2660, 9958, 938, 9010, 1548, 1233, 546, 7988, 1177, 5325, 9063, 3833, 2681, 7753, 8599, 4487, 5938, 3134, 4876, 9933, 4643, 4487, 638, 4028, 6022, 7709, 646, 7398, 866, 5582, 8222, 6801, 6606, 602, 7604, 264, 2399, 5897, 7500, 3215, 3938, 3004, 6725, 3600, 2581, 8159, 516, 1127, 9615, 7959, 4060, 9782, 3536, 1566, 5440, 5318, 9683, 1768, 8767, 2971, 2641, 5472, 926, 2130, 9215, 2149, 195, 9033, 5415, 7707, 5469, 6860, 5700, 8255, 2449, 2168, 8886, 2490, 1088, 4989, 7302, 2177, 4772, 7029, 772, 4359, 9945, 9755, 1084, 4352, 808, 2425, 6086, 3987, 6478, 3, 813, 8090, 8348, 8010, 6551, 6937, 5768, 5982, 2643, 489, 560, 3859, 8242, 8272, 4942, 1374, 6747, 8623, 2791, 9564, 6306, 3928, 3102, 7183, 5475, 7577, 1238, 9638, 2696, 2009, 4612, 4840, 5323, 5582, 9027, 4061, 3701, 4409, 2257, 4537, 2916, 1535, 4998, 9430, 6219, 7764, 3092, 5581, 6947, 9782, 9402, 7520, 7711, 4579, 5491, 6791, 8654, 7224, 8956, 4165, 1802, 6424, 3, 182, 1949, 5589, 7019, 647, 8883, 8926, 6459, 1170, 7274, 596, 6646, 1589, 5718, 4298, 4005, 2142, 7617, 5562, 1745, 4197, 815, 5966, 5997, 278, 2304, 7681, 2399, 2025, 559, 3459, 3503, 3008, 6135, 8274, 1800, 3596, 5494, 2380, 8540, 2460, 6345, 2814, 8965, 9140, 8582, 8839, 7749, 1382, 6153, 62, 5166, 2079, 5494, 8348]
Selection Sort
Number of Comparisons: 12497500
Number of Swaps: 4990

Bubble Sort
Number of Comparisons: 12497500
Number of Swaps: 6235305

Merge Sort
Number of Comparisons: 137040
Number of Swaps: 61808

Insertion Sort
Number of Comparisons: 6240304
Number of Swaps: 6240292

Table To Compare

Sort	Time	Comparisons	Swaps	Complexity
Selection	7798775.2	12497500	4989	O(n^2)
Bubble	5728395.3	12497500	6146037	O(n)
Merge	371920.1	137018	61808	O(n log n)
Insertion	10518.4	6151036	6151027	O(n^2)

Hashmaps

import java.util.HashMap;
import java.lang.Integer;
import java.util.Scanner;

public class Hash {
    public static void main(String[] args) {

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] arrayA = new int[70000]; //creating new hash map with 70000 possible values 

        for (int i = 0; i < 70000; i++) {
            Integer key = (int) (Math.random() * 70000); //using math random to map the different keys 
            map.put(key, key);
            arrayA[i] = key;
        }

        System.out.println("LookUp | BinarySearch");

        double total_lookup = 0;
        double total_binary = 0;

        // get num to search for from scanner
        Scanner sc = new Scanner(System.in);
        Integer num = sc.nextInt(); 

        for (int i = 0; i < 12; i++) {
            
            // check look up time 
            String str = "|      ";
            long lookup = (lookUp(map, num));
            total_lookup += lookup;
            str += (lookup + "    | ");
            
            // check binary search time
            int[] arrayB = new int[70000];
            System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length);
            long binary = (binarySearchTime(arrayB, num));
            total_binary += binary;
            str += (binary+ "   |  ");

            System.out.println(str);
        }

        System.out.println("-------------------------------");
        System.out.println("Average time for lookup: " + (total_lookup / 12) + " | For binary search:" + (total_binary / 12) + "");
    }

    public static long lookUp(HashMap<Integer, Integer> map, Integer key) {
        long start = System.nanoTime(); //searching for the key from the hash table and counting the time it takes 
        map.containsKey(key);
        long end = System.nanoTime();
        return (end - start);
    }

    public static long binarySearchTime(int[] numArray, Integer key) {
        // must be sorted in increasing to decreasing order to search 
        long start = System.nanoTime();
        // binary search 
        int low = 0;
        int high = numArray.length - 1; //last index of the sortedArray, is equal to its length – 1.
        int mid = low  + ((high - low) / 2); // better than just ((high - low) / 2); because accounts for greater numbers
        while (low <= high) { //When the method runs for the first time the low is 0 znd high is equal to its length – 1.
            if (numArray[mid] < key) { // while loop compares the key with the array value of the middle index of the sortedArray.
                low = mid + 1;
            } else if (numArray[mid] == key) {
                break;
            } else {  //If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.
                high = mid - 1;
            }
            mid = low  + ((high - low) / 2);
        }
            // overall algorithm is comparing the key value to the middle element to eliminate halves that it cant be part of
        long end = System.nanoTime();
        return (end - start); //overall time it takes 
    }
}

Hash.main(null);

LookUp | BinarySearch
|      25788    | 4743   |  
|      1269    | 4522   |  
|      851    | 6435   |  
|      1302    | 6094   |  
|      908    | 9112   |  
|      961    | 5639   |  
|      32022    | 5490   |  
|      2113    | 6132   |  
|      699    | 4522   |  
|      1297    | 5262   |  
|      307    | 2502   |  
|      325    | 2297   |  
-------------------------------
Average time for lookup: 5653.5 | For binary search:5229.166666666667