Write a Java program to implement and test the quicksort fun

Write a Java program to implement and test the quicksort function

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

import java.util.Random;

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

public class QuickSort {
  
public static int partitionArray (int arr[], int start, int end)
{
int pivot = arr[end]; // pivot
int smaller = (start - 1); // Index of smaller element
int temp;
  
for (int j = start; j <= end- 1; j++)
{
if (arr[j] <= pivot)
{
smaller++;
temp = arr[smaller];
arr[smaller] = arr[j];
arr[j] = temp;
}
}
  
temp = arr[smaller+1];
arr[smaller+1] = arr[end];
arr[end] = temp;
  
return (smaller + 1);
}
  
public static void quickSort(int arr[], int start, int end)
{
if(arr == null)
{
System.out.println(\"Please pass a valid array.\");
return;
}
if (start < end)
{
//Partition the array based on the partition function defined.
int partition_index = partitionArray(arr, start, end);

// Separately sort elements before
// partition and after partition
quickSort(arr, start, partition_index - 1);
quickSort(arr, partition_index + 1, end);
}
}
  
public static void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
System.out.print(arr[i] + \" \");
  
System.out.println();
}
  
public static void main(String[] args)
{
Random random = new Random();
  
quickSort(null, 0, 0);
  
int[] arr = new int[1000];
  
//Below array will be filled with random numbers in range 0 to 1000
for(int i=0;i<1000;i++)
arr[i] = random.nextInt(1001);
  
System.out.print(\"Before Sorting : \");
printArray(arr);
  
quickSort(arr, 0, 999);
  
System.out.print(\"After Sorting : \");
printArray(arr);
  
int[] arr1 = {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};
  
System.out.print(\"Before Sorting : \");
printArray(arr1);
  
quickSort(arr1, 0, 24);
  
System.out.print(\"After Sorting : \");
printArray(arr1);
  
int[] arr2 = {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};
System.out.print(\"Before Sorting : \");
printArray(arr2);
  
quickSort(arr2, 0, 24);
  
System.out.print(\"After Sorting : \");
printArray(arr2);
}
  
}

OUTPUT:

run:
Please pass a valid array.
Before Sorting : 365 198 614 391 134 743 548 387 315 730 181 710 867 638 934 476 734 816 685 699 222 141 784 860 903 940 207 250 959 282 471 833 101 833 937 931 820 97 664 628 175 493 885 362 734 897 805 218 541 426 172 295 400 115 380 241 688 307 23 318 321 601 61 545 770 556 768 278 903 544 990 440 666 546 813 914 974 525 878 676 898 409 896 896 1000 226 735 353 471 771 475 917 976 648 289 937 372 588 784 464 390 414 976 24 803 919 284 646 398 587 585 751 77 514 878 607 291 79 970 273 189 5 508 939 562 16 644 177 798 363 962 387 677 920 94 873 58 844 694 442 490 840 325 947 938 433 823 44 659 991 470 263 220 866 158 872 155 448 812 420 836 523 171 100 684 250 453 240 710 965 13 308 631 254 678 994 856 503 115 822 663 696 757 158 272 194 292 105 580 454 469 582 96 522 848 581 22 34 975 634 18 621 978 268 342 97 803 23 599 812 938 722 367 914 640 26 339 490 161 620 724 127 534 578 653 172 173 871 64 831 979 180 28 110 615 624 718 937 948 440 289 465 703 884 127 976 970 375 505 133 629 952 597 648 584 665 228 413 274 78 812 725 468 883 653 657 836 663 258 755 17 116 380 706 786 192 460 144 533 39 345 191 743 160 695 520 945 308 329 642 308 829 429 349 292 886 474 549 588 874 648 299 74 58 721 19 769 94 750 165 298 755 575 858 665 827 633 403 46 331 997 722 241 805 360 560 91 638 804 783 470 941 798 845 514 395 561 676 842 309 979 119 956 176 437 533 355 297 493 160 489 561 273 480 461 597 562 216 250 231 319 187 675 839 587 722 800 998 723 608 41 168 913 966 212 985 797 236 347 579 959 567 92 159 133 49 5 314 79 8 120 149 818 405 155 93 260 972 875 780 944 32 158 719 370 80 900 655 444 895 994 381 475 995 595 761 762 676 910 979 220 998 627 827 994 855 590 96 683 974 502 969 837 825 885 382 331 26 76 309 795 649 46 212 748 790 538 344 950 988 498 293 526 279 836 846 789 836 792 693 83 204 603 816 32 908 923 63 0 83 330 400 639 52 124 80 92 360 797 721 725 376 707 273 639 985 905 16 386 383 771 382 832 452 899 417 405 330 116 720 455 627 450 628 685 648 167 249 372 971 169 425 81 957 900 635 595 324 65 99 177 590 480 125 908 675 719 71 317 837 168 718 564 580 394 677 370 135 88 279 11 97 222 216 172 39 323 268 773 426 472 166 667 348 569 878 883 630 398 582 16 718 653 794 563 783 293 427 81 406 309 372 205 789 855 700 917 883 590 483 579 836 592 16 962 416 465 204 673 694 554 408 603 773 341 625 826 435 226 375 194 52 353 690 982 756 392 370 516 543 343 483 333 190 402 820 817 762 920 175 175 525 409 61 320 30 31 974 467 5 728 896 120 611 94 185 459 753 917 343 112 436 189 387 655 100 987 52 271 206 943 247 606 749 747 980 68 724 167 782 179 356 371 37 115 285 142 673 110 476 583 896 771 329 25 702 811 594 974 596 148 131 68 892 419 750 469 24 871 403 347 326 308 949 775 75 459 922 799 769 448 512 950 353 248 930 110 883 417 214 650 954 527 867 845 982 540 532 711 902 585 542 445 85 545 513 516 677 182 790 840 550 721 43 681 812 169 665 607 901 424 845 361 113 449 761 566 853 630 615 705 313 475 663 485 276 793 626 733 514 309 227 650 525 963 748 33 211 119 261 309 873 200 647 493 286 850 385 799 951 602 94 645 165 402 575 64 355 467 295 993 721 499 10 398 576 951 686 701 837 73 178 877 785 295 956 74 359 653 965 664 249 781 404 879 815 188 579 970 82 600 219 845 880 970 889 361 579 999 327 854 431 301 491 989 979 770 368 722 778 666 782 453 712 73 959 843 77 79 890 340 720 855 916 42 533 124 864 418 935 898 140 653 91 49 40 708 181 417 786 662 143 444 520 88 975 723 395 862 330 516 614 349 34 938 901 669 846 781 690 835 537 281 45 925 781 843 554 714 463 109 259 85 997 645 789 521 89 61 875 315 405 84 562 422 25 470 633 480 345 473 673 877 720 1000 125 740 888 144 963 88 879 263 806 67 625 715 42 907 860 234 596 668 245 626 334 516 9 247 410 596 91 667 760 917 977 227 169 241 200 743 308 64 352 650 395 264 991 154 952 634 5 612 23 872 969 668 52 540 592 281 750 418 97 748 614 747 87 338 426 614 963 981 914 574 99 8 604 868 302
After Sorting : 0 5 5 5 5 8 8 9 10 11 13 16 16 16 16 17 18 19 22 23 23 23 24 24 25 25 26 26 28 30 31 32 32 33 34 34 37 39 39 40 41 42 42 43 44 45 46 46 49 49 52 52 52 52 58 58 61 61 61 63 64 64 64 65 67 68 68 71 73 73 74 74 75 76 77 77 78 79 79 79 80 80 81 81 82 83 83 84 85 85 87 88 88 88 89 91 91 91 92 92 93 94 94 94 94 96 96 97 97 97 97 99 99 100 100 101 105 109 110 110 110 112 113 115 115 115 116 116 119 119 120 120 124 124 125 125 127 127 131 133 133 134 135 140 141 142 143 144 144 148 149 154 155 155 158 158 158 159 160 160 161 165 165 166 167 167 168 168 169 169 169 171 172 172 172 173 175 175 175 176 177 177 178 179 180 181 181 182 185 187 188 189 189 190 191 192 194 194 198 200 200 204 204 205 206 207 211 212 212 214 216 216 218 219 220 220 222 222 226 226 227 227 228 231 234 236 240 241 241 241 245 247 247 248 249 249 250 250 250 254 258 259 260 261 263 263 264 268 268 271 272 273 273 273 274 276 278 279 279 281 281 282 284 285 286 289 289 291 292 292 293 293 295 295 295 297 298 299 301 302 307 308 308 308 308 308 309 309 309 309 309 313 314 315 315 317 318 319 320 321 323 324 325 326 327 329 329 330 330 330 331 331 333 334 338 339 340 341 342 343 343 344 345 345 347 347 348 349 349 352 353 353 353 355 355 356 359 360 360 361 361 362 363 365 367 368 370 370 370 371 372 372 372 375 375 376 380 380 381 382 382 383 385 386 387 387 387 390 391 392 394 395 395 395 398 398 398 400 400 402 402 403 403 404 405 405 405 406 408 409 409 410 413 414 416 417 417 417 418 418 419 420 422 424 425 426 426 426 427 429 431 433 435 436 437 440 440 442 444 444 445 448 448 449 450 452 453 453 454 455 459 459 460 461 463 464 465 465 467 467 468 469 469 470 470 470 471 471 472 473 474 475 475 475 476 476 480 480 480 483 483 485 489 490 490 491 493 493 493 498 499 502 503 505 508 512 513 514 514 514 516 516 516 516 520 520 521 522 523 525 525 525 526 527 532 533 533 533 534 537 538 540 540 541 542 543 544 545 545 546 548 549 550 554 554 556 560 561 561 562 562 562 563 564 566 567 569 574 575 575 576 578 579 579 579 579 580 580 581 582 582 583 584 585 585 587 587 588 588 590 590 590 592 592 594 595 595 596 596 596 597 597 599 600 601 602 603 603 604 606 607 607 608 611 612 614 614 614 614 615 615 620 621 624 625 625 626 626 627 627 628 628 629 630 630 631 633 633 634 634 635 638 638 639 639 640 642 644 645 645 646 647 648 648 648 648 649 650 650 650 653 653 653 653 653 655 655 657 659 662 663 663 663 664 664 665 665 665 666 666 667 667 668 668 669 673 673 673 675 675 676 676 676 677 677 677 678 681 683 684 685 685 686 688 690 690 693 694 694 695 696 699 700 701 702 703 705 706 707 708 710 710 711 712 714 715 718 718 718 719 719 720 720 720 721 721 721 721 722 722 722 722 723 723 724 724 725 725 728 730 733 734 734 735 740 743 743 743 747 747 748 748 748 749 750 750 750 751 753 755 755 756 757 760 761 761 762 762 768 769 769 770 770 771 771 771 773 773 775 778 780 781 781 781 782 782 783 783 784 784 785 786 786 789 789 789 790 790 792 793 794 795 797 797 798 798 799 799 800 803 803 804 805 805 806 811 812 812 812 812 813 815 816 816 817 818 820 820 822 823 825 826 827 827 829 831 832 833 833 835 836 836 836 836 836 837 837 837 839 840 840 842 843 843 844 845 845 845 845 846 846 848 850 853 854 855 855 855 856 858 860 860 862 864 866 867 867 868 871 871 872 872 873 873 874 875 875 877 877 878 878 878 879 879 880 883 883 883 883 884 885 885 886 888 889 890 892 895 896 896 896 896 897 898 898 899 900 900 901 901 902 903 903 905 907 908 908 910 913 914 914 914 916 917 917 917 917 919 920 920 922 923 925 930 931 934 935 937 937 937 938 938 938 939 940 941 943 944 945 947 948 949 950 950 951 951 952 952 954 956 956 957 959 959 959 962 962 963 963 963 965 965 966 969 969 970 970 970 970 971 972 974 974 974 974 975 975 976 976 976 977 978 979 979 979 979 980 981 982 982 985 985 987 988 989 990 991 991 993 994 994 994 995 997 997 998 998 999 1000 1000
Before Sorting : 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
After Sorting : 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
Before Sorting : 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
After Sorting : 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
BUILD SUCCESSFUL (total time: 0 seconds)