java-algorithms/QuickSort.java at main · Mahidhar05/java-algorithms · GitHub

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Java implementation of QuickSort
importjava.io.*;

classGFG {

// A utility function to swap two elements
staticvoidswap(int[] arr, inti, intj)
	{
inttemp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
	}

/* This function takes last element as pivot, places
	the pivot element at its correct position in sorted
	array, and places all smaller (smaller than pivot)
	to left of pivot and all greater elements to right
	of pivot */
staticintpartition(int[] arr, intlow, inthigh)
	{

// pivot
intpivot = arr[high];

// Index of smaller element and
// indicates the right position
// of pivot found so far
inti = (low - 1);

for (intj = low; j <= high - 1; j++) {

// If current element is smaller
// than the pivot
if (arr[j] < pivot) {

// Increment index of
// smaller element
i++;
swap(arr, i, j);
 }
 }
swap(arr, i + 1, high);
return (i + 1);
	}

/* The main function that implements QuickSort
 arr[] --> Array to be sorted,
 low --> Starting index,
 high --> Ending index
	*/
staticvoidquickSort(int[] arr, intlow, inthigh)
	{
if (low < high) {

// pi is partitioning index, arr[p]
// is now at right place
intpi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
 }
	}

// Function to print an array
staticvoidprintArray(int[] arr, intsize)
	{
for (inti = 0; i < size; i++)
System.out.print(arr[i] + " ");

System.out.println();
	}

// Driver Code
publicstaticvoidmain(String[] args)
	{
int[] arr = { 10, 7, 8, 9, 1, 5 };
intn = arr.length;

quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
	}
}