Write a Java program to implement and test the quicksort fun

Write a Java program to implement and test the quicksort function. This simple implementation will sort an array of integers. Upload the .java file into A5 folder of icollege.

The grading program will run at least these tests:

Calls quicksort(NULL, 0) to make sure that it doesn\'t crash.

Calls quicksort to sort an array with just one element.

Calls quicksort to sort an array with 1000 elements (containing the numbers 0 through 1000 in a random order).

Calls quicksort to sort an array that contains 1000 elements with two copies of the numbers from 0 to 499. Check that the array is correct after sorting.

Calls quicksort to sort an array that contains the numbers 0 through 25 already sorted.

Calls quicksort to sort an array that contains the numbers 25 through 0 in reverse order.

Solution

Code:

import java.util.Arrays;

public class Main{

public static void main(String args[]) {
   QuickSort algorithm = new QuickSort();
   int[] array1 = {};
   int[] array2 = {2};
   int[] array3 = {482, 95, 414, 713, 125, 60, 988, 699, 299, 762, 635, 113, 185, 589, 120, 492, 558, 412, 864, 184, 907, 365, 830, 244, 160, 890, 343, 156, 420, 549, 850, 284, 939, 522, 526, 704, 552, 560, 883, 759, 545, 965, 248, 785, 37, 104, 954, 792, 955, 253, 831, 884, 905, 437, 672, 179, 12, 813, 141, 525, 333, 467, 276, 643, 590, 901, 324, 336, 11, 725, 521, 660, 250, 213, 133, 930, 963, 462, 82, 693, 329, 972, 950, 26, 887, 337, 360, 742, 858, 452, 441, 753, 692, 62, 918, 601, 106, 899, 538, 102, 838, 990, 897, 987, 847, 758, 247, 426, 745, 192, 597, 969, 738, 958, 96, 346, 579, 976, 201, 927, 146, 428, 361, 585, 818, 220, 669, 659, 422, 405, 358, 42, 252, 249, 953, 837, 947, 230, 410, 348, 641, 821, 652, 349, 49, 915, 719, 638, 782, 134, 576, 856, 535, 404, 111, 865, 176, 936, 816, 487, 347, 501, 995, 977, 429, 731, 903, 642, 627, 448, 511, 143, 181, 272, 374, 895, 384, 294, 169, 267, 290, 564, 119, 350, 741, 880, 362, 33, 633, 312, 855, 109, 565, 238, 455, 268, 445, 474, 136, 469, 401, 279, 465, 658, 91, 443, 10, 795, 914, 657, 212, 216, 433, 687, 138, 604, 683, 507, 722, 353, 472, 103, 980, 3, 269, 774, 694, 854, 395, 799, 59, 986, 882, 751, 911, 457, 40, 288, 888, 631, 496, 951, 304, 876, 859, 889, 852, 788, 978, 684, 101, 926, 442, 180, 675, 493, 870, 732, 524, 786, 197, 925, 874, 447, 277, 88, 76, 240, 909, 598, 323, 804, 632, 505, 357, 440, 130, 616, 56, 685, 485, 569, 673, 842, 307, 266, 959, 162, 117, 153, 791, 470, 596, 929, 803, 4, 919, 772, 264, 665, 36, 750, 573, 399, 730, 771, 132, 480, 234, 881, 340, 43, 580, 263, 931, 828, 542, 144, 208, 481, 73, 737, 241, 61, 686, 707, 584, 712, 812, 48, 233, 151, 625, 354, 326, 46, 270, 325, 140, 551, 586, 752, 841, 757, 546, 166, 205, 473, 698, 129, 571, 898, 67, 893, 215, 793, 702, 807, 853, 497, 504, 736, 368, 334, 174, 371, 998, 308, 568, 744, 593, 199, 280, 488, 21, 236, 70, 518, 256, 718, 985, 257, 322, 23, 678, 341, 131, 366, 780, 543, 817, 300, 8, 402, 695, 974, 319, 217, 418, 650, 315, 530, 206, 411, 158, 345, 636, 783, 382, 152, 763, 289, 848, 293, 940, 913, 477, 728, 375, 305, 661, 999, 173, 14, 605, 148, 471, 344, 97, 647, 900, 0, 328, 400, 938, 592, 164, 369, 432, 378, 352, 193, 534, 285, 857, 44, 644, 2, 624, 610, 595, 63, 992, 292, 829, 503, 47, 484, 912, 910, 338, 464, 973, 225, 520, 656, 214, 769, 716, 663, 387, 356, 599, 960, 302, 790, 777, 916, 547, 836, 863, 468, 112, 379, 1000, 681, 58, 32, 628, 891, 6, 271, 849, 964, 875, 275, 690, 105, 945, 389, 449, 298, 550, 137, 824, 760, 894, 421, 163, 16, 952, 390, 87, 729, 928, 170, 634, 259, 342, 559, 466, 540, 922, 726, 386, 761, 171, 833, 629, 243, 682, 866, 92, 510, 22, 490, 223, 35, 570, 394, 110, 149, 614, 982, 278, 30, 498, 993, 446, 203, 77, 869, 827, 127, 229, 723, 311, 107, 306, 640, 114, 517, 724, 27, 475, 626, 923, 639, 666, 52, 740, 397, 529, 273, 908, 126, 574, 41, 335, 671, 476, 314, 186, 89, 844, 224, 709, 383, 630, 735, 710, 251, 872, 902, 222, 66, 835, 142, 839, 339, 417, 779, 381, 717, 392, 944, 577, 155, 237, 948, 578, 53, 191, 805, 971, 124, 28, 83, 188, 380, 801, 961, 770, 500, 531, 408, 756, 781, 486, 364, 654, 846, 100, 309, 108, 743, 688, 906, 81, 822, 609, 528, 295, 734, 79, 555, 566, 966, 135, 419, 514, 93, 968, 826, 885, 862, 787, 453, 231, 413, 942, 123, 161, 949, 602, 425, 25, 670, 515, 31, 513, 617, 218, 80, 24, 19, 991, 823, 74, 645, 228, 776, 265, 877, 85, 359, 749, 209, 747, 456, 427, 603, 409, 594, 332, 516, 499, 794, 450, 932, 700, 984, 733, 461, 808, 491, 754, 691, 255, 303, 430, 651, 619, 989, 680, 200, 648, 204, 581, 90, 536, 313, 537, 588, 587, 98, 527, 767, 983, 202, 994, 297, 871, 227, 39, 646, 815, 867, 391, 607, 444, 355, 415, 393, 622, 145, 937, 115, 172, 260, 168, 873, 55, 376, 51, 84, 385, 554, 261, 979, 210, 86, 809, 219, 351, 775, 892, 198, 373, 367, 245, 720, 190, 122, 321, 755, 463, 438, 435, 286, 99, 1, 962, 921, 611, 934, 706, 878, 317, 957, 34, 784, 618, 459, 5, 920, 57, 254, 868, 620, 879, 667, 523, 310, 330, 495, 178, 282, 45, 563, 69, 407, 572, 291, 165, 211, 843, 943, 331, 705, 121, 689, 71, 460, 583, 802, 679, 608, 194, 886, 479, 50, 434, 509, 177, 207, 283, 116, 221, 851, 941, 182, 924, 677, 403, 519, 825, 567, 78, 195, 424, 94, 996, 674, 981, 708, 439, 54, 478, 649, 739, 701, 860, 773, 612, 797, 29, 301, 896, 7, 591, 372, 532, 778, 561, 668, 541, 508, 15, 721, 377, 935, 703, 18, 226, 539, 370, 662, 548, 20, 613, 615, 811, 917, 274, 748, 553, 167, 398, 764, 806, 653, 798, 933, 489, 904, 281, 711, 235, 810, 796, 64, 13, 789, 72, 556, 512, 621, 189, 746, 175, 800, 157, 582, 296, 17, 600, 431, 416, 458, 768, 819, 9, 483, 557, 956, 423, 606, 406, 242, 765, 232, 861, 727, 196, 187, 832, 258, 997, 502, 139, 363, 820, 970, 544, 946, 65, 159, 664, 766, 38, 183, 150, 388, 714, 655, 676, 506, 967, 128, 454, 239, 834, 494, 320, 975, 327, 287, 715, 154, 118, 845, 533, 562, 246, 75, 575, 147, 436, 840, 623, 318, 814, 316, 396, 68,697, 451,637,262,696};
   int[] array4 = {15, 43, 168, 408, 425, 133, 153, 251, 393, 253, 2, 445, 251, 284, 381, 317, 330, 157, 475, 12, 3, 252, 94, 243, 497, 11, 410, 15, 434, 280, 53, 117, 396, 211, 41, 183, 72, 252, 356, 353, 3, 398, 31, 276, 374, 439, 419, 97, 119, 182, 380, 411, 208, 214, 71, 111, 112, 25, 39, 308, 359, 472, 181, 370, 9, 361, 64, 227, 388, 381, 26, 147, 461, 188, 358, 330, 212, 460, 133, 19, 193, 331, 122, 483, 49, 383, 76, 437, 226, 428, 112, 290, 27, 80, 78, 27, 474, 24, 424, 56, 454, 129, 99, 157, 7, 364, 404, 455, 218, 433, 64, 261, 20, 97, 283, 149, 319, 12, 271, 235, 58, 100, 68, 253, 463, 256, 202, 191, 37, 316, 174, 247, 266, 275, 6, 399, 70, 445, 187, 145, 4, 14, 305, 211, 405, 190, 191, 288, 498, 74, 16, 44, 284, 473, 120, 321, 83, 322, 315, 415, 459, 131, 390, 139, 489, 197, 106, 83, 210, 150, 465, 451, 209, 436, 221, 289, 200, 46, 11, 307, 142, 384, 227, 434, 152, 385, 371, 229, 73, 84, 187, 427, 222, 402, 103, 81, 230, 380, 287, 68, 277, 306, 268, 51, 23, 238, 160, 55, 149, 98, 321, 163, 427, 383, 302, 403, 139, 220, 453, 160, 75, 448, 301, 163, 312, 153, 29, 322, 476, 2, 240, 38, 338, 262, 430, 58, 169, 172, 470, 274, 481, 486, 142, 236, 120, 107, 494, 291, 165, 271, 479, 113, 388, 305, 386, 409, 62, 229, 213, 33, 220, 212, 456, 285, 82, 325, 482, 221, 248, 387, 444, 84, 171, 332, 233, 438, 336, 329, 256, 303, 474, 384, 30, 246, 280, 86, 454, 399, 464, 250, 281, 70, 137, 143, 216, 18, 338, 177, 401, 101, 259, 44, 340, 358, 299, 449, 331, 34, 299, 392, 92, 433, 162, 54, 167, 285, 147, 103, 485, 309, 54, 116, 378, 127, 52, 156, 235, 36, 114, 118, 86, 194, 143, 77, 265, 414, 219, 158, 459, 357, 195, 257, 161, 394, 210, 415, 324, 420, 249, 224, 421, 463, 155, 269, 69, 389, 242, 487, 8, 30, 374, 336, 364, 491, 180, 359, 401, 457, 385, 371, 306, 129, 460, 479, 186, 288, 496, 351, 185, 116, 194, 334, 108, 80, 260, 455, 408, 484, 67, 446, 146, 34, 90, 21, 94, 61, 457, 451, 22, 278, 150, 339, 17, 35, 56, 287, 467, 183, 230, 178, 254, 104, 481, 197, 245, 244, 144, 60, 173, 225, 488, 377, 448, 246, 270, 204, 464, 38, 244, 426, 318, 206, 6, 443, 297, 126, 282, 203, 310, 45, 491, 152, 100, 412, 240, 397, 362, 289, 432, 372, 96, 348, 154, 198, 196, 476, 231, 93, 29, 55, 487, 295, 199, 51, 9, 132, 365, 343, 406, 379, 164, 363, 42, 318, 140, 87, 470, 184, 435, 416, 291, 202, 294, 53, 52, 255, 480, 478, 469, 223, 356, 342, 361, 89, 92, 228, 272, 395, 442, 395, 370, 312, 313, 110, 201, 236, 410, 135, 485, 471, 355, 298, 32, 424, 368, 1, 345, 265, 483, 468, 170, 130, 107, 444, 168, 75, 466, 215, 207, 354, 376, 420, 259, 36, 290, 189, 495, 442, 196, 241, 346, 50, 90, 342, 14, 111, 378, 109, 432, 400, 213, 130, 91, 226, 350, 134, 135, 23, 405, 161, 368, 438, 310, 10, 104, 185, 498, 496, 469, 367, 472, 262, 24, 37, 127, 430, 231, 59, 176, 177, 232, 234, 390, 125, 462, 141, 4, 349, 453, 273, 69, 494, 99, 344, 225, 314, 350, 275, 298, 369, 48, 467, 207, 166, 156, 352, 316, 179, 35, 162, 333, 391, 123, 412, 77, 353, 108, 344, 495, 78, 272, 375, 488, 484, 239, 169, 335, 132, 243, 422, 466, 425, 192, 351, 320, 257, 301, 72, 65, 203, 294, 447, 123, 122, 493, 88, 363, 296, 414, 431, 216, 59, 109, 189, 28, 389, 497, 478, 341, 297, 62, 67, 372, 281, 327, 63, 209, 166, 324, 329, 5, 13, 278, 377, 134, 79, 181, 273, 79, 340, 138, 45, 376, 349, 423, 61, 239, 76, 439, 126, 446, 263, 193, 95, 255, 171, 366, 407, 182, 40, 39, 327, 365, 409, 205, 357, 5, 477, 155, 449, 489, 145, 360, 136, 124, 403, 311, 118, 140, 95, 394, 48, 8, 237, 404, 441, 307, 176, 128, 473, 268, 175, 188, 20, 337, 205, 393, 276, 456, 85, 190, 0, 28, 267, 260, 326, 40, 437, 429, 110, 146, 333, 458, 10, 303, 154, 60, 208, 125, 264, 115, 201, 73, 323, 480, 144, 138, 450, 247, 452, 443, 490, 413, 49, 91, 379, 269, 400, 233, 490, 114, 441, 274, 477, 254, 317, 277, 217, 105, 387, 382, 258, 461, 367, 93, 447, 347, 74, 57, 219, 435, 218, 106, 346, 131, 328, 26, 482, 63, 450, 172, 195, 283, 215, 426, 178, 402, 313, 292, 304, 22, 417, 7, 167, 105, 186, 158, 421, 81, 148, 151, 429, 141, 33, 222, 32, 418, 102, 354, 164, 101, 339, 151, 119, 174, 16, 428, 264, 165, 373, 19, 18, 335, 136, 270, 214, 121, 345, 411, 237, 279, 416, 71, 293, 261, 192, 314, 124, 87, 355, 308, 234, 398, 440, 465, 315, 337, 66, 343, 159, 249, 121, 360, 21, 332, 362, 419, 286, 397, 13, 180, 128, 17, 492, 65, 492, 417, 31, 198, 352, 325, 199, 89, 422, 248, 47, 309, 41, 117, 300, 0, 468, 217, 263, 223, 302, 286, 232, 396, 311, 323, 320, 258, 341, 242, 436, 369, 266, 334, 328, 228, 423, 279, 250, 88, 304, 204, 46, 241, 206, 413, 85, 418, 431, 282, 366, 200, 392, 493, 293, 113, 82, 319, 159, 50, 375, 98, 475, 391, 238, 175, 462, 25, 245, 267, 57, 348, 382, 170, 224, 386, 300, 96, 148, 184, 458, 296, 47, 452, 179, 406, 486, 407, 1, 373, 295, 137, 43, 102, 471, 66, 326, 347, 173, 115, 42, 440, 292};
   int[] array5 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25};
   int[] array6 = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
       algorithm.print(array1);
       algorithm.print(array2);
       algorithm.print(array3);
       algorithm.print(array4);
       algorithm.print(array5);
       algorithm.print(array6);

}

}

class QuickSort {

private int input[];
private int length;

private void sort(int[] numbers) {

if (numbers == null || numbers.length == 0) {
return;
}
this.input = numbers;
length = numbers.length;
quickSort(0, length - 1);
}

private void quickSort(int low, int high) {
int i = low;
int j = high;

// pivot is middle index
int pivot = input[low + (high - low) / 2];

// Divide into two arrays
while (i <= j) {

while (input[i] < pivot) {
i++;
}
while (input[j] > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
// move index to next position on both sides
i++;
j--;
}
}

// calls quickSort() method recursively
if (low < j) {
quickSort(low, j);
}

if (i < high) {
quickSort(i, high);
}
}

private void swap(int i, int j) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
public void print(int[] array){
  
System.out.println(\"Unsorted array :\" + Arrays.toString(array));

QuickSort algorithm = new QuickSort();

// sorting integer array using quicksort algorithm
algorithm.sort(array);

// printing sorted array
System.out.println(\"Sorted array :\" + Arrays.toString(array));
}
}

Output: