import java.util.*;

class JavaRace {

public static void main(String args[]) {

long start, stop;

// taken array of 1000 elements to get some significant time as small array sorting will get executed within small time interval

int arr[] = { 675, 532, 903, 20, 112, 995, 277, 965, 472, 887, 485, 131, 380, 85, 494, 336, 145, 545, 204, 471,

232, 447, 882, 802, 525, 281, 564, 389, 323, 833, 445, 860, 369, 778, 784, 514, 612, 893, 257, 51, 333,

93, 283, 158, 59, 469, 144, 158, 96, 320, 481, 723, 977, 816, 413, 482, 44, 190, 851, 999, 593, 147,

211, 587, 446, 55, 964, 687, 189, 282, 655, 163, 35, 269, 377, 440, 578, 612, 211, 280, 93, 25, 749,

305, 679, 979, 34, 365, 243, 134, 794, 23, 605, 63, 727, 863, 613, 499, 886, 132, 489, 395, 566, 464,

300, 376, 535, 1000, 670, 685, 504, 172, 533, 562, 214, 118, 669, 239, 999, 1, 108, 811, 288, 820, 787,

922, 433, 606, 196, 175, 305, 404, 910, 890, 304, 697, 879, 549, 882, 132, 70, 829, 764, 699, 236, 869,

675, 928, 831, 641, 307, 757, 415, 666, 506, 29, 992, 982, 825, 696, 791, 318, 367, 944, 534, 650, 569,

279, 389, 445, 875, 430, 871, 683, 16, 748, 884, 205, 950, 169, 565, 585, 533, 768, 734, 187, 238, 708,

191, 793, 23, 190, 230, 620, 515, 761, 470, 469, 509, 785, 426, 393, 480, 181, 619, 327, 789, 6, 157,

356, 642, 735, 698, 200, 17, 95, 190, 866, 921, 722, 175, 174, 684, 64, 307, 893, 207, 227, 966, 296,

70, 591, 913, 459, 174, 567, 121, 82, 971, 259, 121, 925, 338, 217, 978, 54, 994, 48, 887, 120, 139,

640, 784, 755, 105, 817, 760, 201, 906, 782, 994, 568, 40, 939, 989, 98, 870, 978, 598, 701, 149, 882,

931, 267, 471, 947, 129, 629, 36, 245, 401, 289, 690, 67, 580, 325, 816, 190, 925, 408, 172, 426, 110,

828, 336, 425, 532, 139, 953, 784, 178, 473, 26, 845, 1000, 902, 829, 91, 150, 254, 21, 794, 937, 523,

442, 259, 405, 107, 797, 994, 273, 973, 850, 192, 933, 798, 92, 685, 326, 345, 29, 985, 850, 35, 412,

959, 170, 428, 257, 237, 501, 378, 808, 592, 197, 370, 657, 941, 916, 56, 265, 52, 197, 542, 98, 650,

528, 703, 372, 736, 92, 757, 796, 325, 259, 947, 120, 893, 2, 990, 470, 645, 323, 903, 837, 148, 613,

46, 597, 14, 973, 534, 2, 820, 282, 173, 490, 470, 534, 411, 803, 760, 813, 975, 368, 804, 691, 779,

705, 158, 46, 39, 538, 52, 777, 769, 956, 990, 892, 340, 579, 144, 265, 356, 666, 471, 780, 737, 814,

769, 838, 434, 954, 704, 242, 904, 845, 399, 114, 639, 972, 660, 544, 386, 671, 526, 272, 59, 130, 957,

354, 329, 656, 14, 597, 255, 676, 14, 384, 516, 184, 820, 835, 726, 692, 279, 810, 1, 275, 12, 399, 22,

203, 706, 856, 733, 706, 815, 293, 237, 545, 204, 898, 710, 970, 819, 405, 607, 850, 996, 67, 801, 151,

377, 738, 27, 470, 351, 89, 680, 16, 983, 990, 144, 372, 779, 71, 619, 579, 390, 932, 987, 221, 869,

591, 669, 49, 137, 303, 348, 41, 73, 311, 740, 560, 510, 306, 359, 257, 761, 157, 282, 64, 831, 453,

711, 418, 974, 525, 604, 808, 161, 857, 213, 538, 716, 260, 503, 328, 912, 11, 794, 948, 986, 730, 342,

726, 598, 776, 816, 496, 361, 333, 432, 902, 569, 9, 663, 192, 378, 332, 704, 953, 823, 516, 766, 865,

381, 958, 203, 258, 251, 657, 716, 314, 813, 854, 66, 107, 209, 54, 459, 661, 343, 260, 175, 1, 214, 88,

406, 948, 309, 191, 27, 661, 440, 206, 984, 754, 999, 361, 724, 785, 508, 541, 234, 957, 250, 831, 882,

20, 883, 187, 586, 435, 354, 562, 577, 948, 370, 41, 774, 114, 806, 296, 302, 242, 710, 600, 531, 732,

206, 759, 560, 618, 854, 708, 530, 662, 642, 650, 380, 863, 950, 516, 512, 229, 722, 479, 717, 701, 396,

298, 291, 222, 188, 690, 875, 854, 786, 863, 529, 802, 954, 113, 685, 490, 475, 703, 388, 639, 331, 181,

556, 272, 49, 242, 335, 102, 508, 457, 208, 701, 276, 56, 818, 372, 237, 894, 912, 909, 680, 222, 816,

256, 801, 507, 51, 53, 705, 636, 883, 495, 839, 898, 566, 610, 279, 985, 923, 116, 297, 619, 276, 77,

641, 93, 527, 800, 788, 279, 704, 622, 375, 316, 386, 717, 518, 85, 889, 977, 972, 351, 989, 682, 863,

66, 848, 573, 884, 183, 458, 545, 596, 26, 218, 21, 914, 658, 26, 913, 636, 895, 315, 740, 163, 304,

774, 129, 472, 108, 463, 824, 345, 190, 992, 138, 437, 720, 535, 501, 318, 553, 970, 673, 103, 394, 740,

484, 388, 674, 697, 347, 460, 744, 469, 449, 472, 456, 421, 774, 233, 79, 457, 571, 750, 212, 628, 42,

422, 992, 457, 239, 665, 670, 650, 489, 744, 168, 855, 424, 593, 141, 557, 260, 863, 426, 648, 904, 376,

778, 322, 146, 716, 738, 75, 434, 1, 795, 929, 382, 166, 350, 448, 640, 416, 425, 108, 83, 942, 428, 91,

769, 633, 618, 292, 855, 681, 7, 134, 519, 409, 83, 920, 253, 544, 672, 739, 886, 296, 67, 563, 229,

395, 840, 299, 19, 235, 878, 201, 134, 305, 372, 462, 356, 237, 320, 308, 747, 618, 899, 481, 105, 788,

680, 508, 887, 869, 18, 803, 23, 107, 533, 568, 497, 542, 628, 242, 420, 752, 525, 45, 418, 199, 203,

604, 975, 962, 562, 579, 963, 182, 490, 238, 665, 118, 233, 260, 992, 950, 617, 620, 24, 345, 936, 551,

970, 883, 274, 477, 596, 36, 118, 994, 894, 837, 625, 271, 762, 691, 87, 938, 305, 469, 387, 224, 480,

798, 7, 576, 509, 504, 420, 48, 239, 755, 579, 825, 130, 865, 495, 117, 603, 641, 25, 505, 246, 456, 70,

626, 868, 898, 589, 60, 944, 534, 380, 535, 346, 671, 612, 623, 99, 883, 196, 934, 95, 31, 601, 645,

617, 131, 693, 623, 736, 292, 87, 560, 730, 756 };

// storing intial time in start variable

start = System.currentTimeMillis();

arr = populateReverseArray(arr);

arr = insertionSort(arr);

// storing ending time in stop variable

stop = System.currentTimeMillis();

// Printing execution time by calculating the difference of stop and stop

System.out.println("Reverse Array sorted with insertion sort (ms): " + (stop - start));

// storing intial time in start variable

start = System.currentTimeMillis();

arr = populateNearlySortedArray(arr);

arr = insertionSort(arr);

// storing ending time in stop variable

stop = System.currentTimeMillis();

// Printing execution time by calculating the difference of stop and stop

System.out.println("Nearly sorted Array, sorted with insertion sort (ms): " + (stop - start));

start = System.currentTimeMillis();

arr = populateReverseArray(arr);

// System.out.println(Arrays.toString());

arr = bubbleSort(arr);

stop = System.currentTimeMillis();

System.out.println("Reverse Array sorted with bubble sort (ms): " + (stop - start));

start = System.currentTimeMillis();

arr = populateNearlySortedArray(arr);

// System.out.println(Arrays.toString(bubbleSort(arr)));

arr = bubbleSort(arr);

stop = System.currentTimeMillis();

System.out.println("Nearly sorted Array, sorted with bubble sort (ms): " + (stop - start));

start = System.currentTimeMillis();

// System.out.println();

int index = linearSearch(arr, 47);

stop = System.currentTimeMillis();

System.out.println("Time required to search a a element by Linear Search (ms): " + (stop - start));

start = System.currentTimeMillis();

arr = bubbleSort(arr);

// System.out.println();

index = binarySearch(arr, 0, arr.length - 1, 47);

stop = System.currentTimeMillis();

System.out.println("Time required to search a a element by Binary Search (ms): " + (stop - start));

}

static int[] insertionSort(int arr[]) {

int n = arr.length;

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

int index = arr[i];

int j = i - 1;

while (j >= 0 && arr[j] > index) {

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = index;

}

return arr;

}

static int[] bubbleSort(int arr[]) {

int n = arr.length;

for (int i = 0; i < n - 1; i++)

for (int j = 0; j < n - i - 1; j++)

if (arr[j] > arr[j + 1]) {

// swapping temp and arr[i] if arr of j is greater than arr of j+1

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

return arr;

}

// function to reverse the array

static int[] populateReverseArray(int arr[]) {

int a[] = new int[arr.length];

for (int i = arr.length - 1; i >= 0; i--) {

a[i] = arr[i];

}

return a;

}

// function to get nearly sorted the array

// to get a nearly sorted array we are sorting the array with inbuilt sort

// function and then displacing some data

static int[] populateNearlySortedArray(int arr[]) {

Arrays.sort(arr);

int tmp = arr[0];

arr[0] = arr[arr.length - 1];

arr[arr.length - 1] = tmp;

tmp = arr[1];

arr[1] = arr[arr.length - 2];

arr[arr.length - 2] = arr[1];

return arr;

}

public static int linearSearch(int arr[], int num) {

int n = arr.length;

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

if (arr[i] == num)

return i;

}

// -1 denotes element not found

return -1;

}

// recusrsively searching the element using binary search

public static int binarySearch(int arr[], int l, int r, int num) {

if (r >= l) {

int mid = l + (r - l) / 2;

if (arr[mid] == num)

return mid;

if (arr[mid] > num)

return binarySearch(arr, l, mid - 1, num);

return binarySearch(arr, mid + 1, r, num);

}

// -1 denotes element not found

return -1;

}

}

Psuedo Code for this