Java Practice 9

Write a program to implement quick sort?

1. public class QuickSort
2.  {
3. private int array[];
4. private int length;
5. 
   
6. public void sort(int[] inputArr) {
7. 
   
8. if (inputArr == null || inputArr.length == 0) {
9. return;
10. }
11. this.array = inputArr;
12. length = inputArr.length;
13. quickSort(0, length - 1);
14. }
15. 
    
16. private void quickSort(int lowerIndex, int higherIndex) {
17. 
    
18. int i = lowerIndex;
19. int j = higherIndex;
20. // calculate pivot number, I am taking pivot as middle index number
21. int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
22. // Divide into two arrays
23. while (i <= j) {
24. /**
25. * In each iteration, we will identify a number from left side which
26. * is greater then the pivot value, and also we will identify a number
27. * from right side which is less then the pivot value. Once the search
28. * is done, then we exchange both numbers.
29. */
30. while (array[i] < pivot) {
31. i++;
32. }
33. while (array[j] > pivot) {
34. j--;
35. }
36. if (i <= j) {
37. exchangeNumbers(i, j);
38. //move index to next position on both sides
39. i++;
40. j--;
41. }
42. }
43. // call quickSort() method recursively
44. if (lowerIndex < j)
45. quickSort(lowerIndex, j);
46. if (i < higherIndex)
47. quickSort(i, higherIndex);
48. }
49. 
    
50. private void exchangeNumbers(int i, int j) {
51. int temp = array[i];
52. array[i] = array[j];
53. array[j] = temp;
54. }
55. 
    
56. public static void main(String a[]){
57. 
    
58. QuickSort sorter = new QuickSort();
59. int[] input = {24,2,45,20,56,75,2,56,99,53,12};
60. sorter.sort(input);
61. for(int i:input){
62. System.out.print(i);
63. System.out.print(" ");
64. }
65. }
66. }