-
Notifications
You must be signed in to change notification settings - Fork 4
/
QuickSort.java
75 lines (67 loc) · 1.89 KB
/
QuickSort.java
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
package sort.quick;
import sort.AbstractBase;
/**
* @author Suyash
* <p>Complexity in average case is <b>O(nlog(n))</b>.</p>
* <p>Complexity in worst case is <b>O(n^2)</b>.</p>
*/
public class QuickSort extends AbstractBase {
public Integer[] sort(Integer array[], int start, int end){
if(start<end){
int pIndex = partition(array, start, end);
sort(array, start, pIndex-1);
sort(array, pIndex+1, end);
}
return array;
}
public int partition(Integer array[], int start, int end){
/**
All the elements <= pivot will be at the left of pIndex.
*/
int pIndex=start;
int pivot = array[end], temp;
for(int i=start; i<end; i++){
if(array[i]<=pivot){
// Swap array[pIndex] and current element.
temp = array[pIndex];
array[pIndex] = array[i];
array[i] = temp;
pIndex++;
}
}
// Swap pivot(array[end]) and array[pIndex]
temp = array[pIndex];
array[pIndex] = array[end];
array[end] = temp;
return pIndex;
}
/******************************************************
USING GENERICS
******************************************************/
public <E extends Comparable<E>> E[] genericSort(E[] array, int start, int end) {
if(start<end) {
int pIndex = partition(array, start, end);
genericSort(array, start, pIndex-1);
genericSort(array, pIndex+1, end);
}
return array;
}
public <E extends Comparable<E>> int partition(E[] array, int start, int end) {
int pIndex = start;
E pivot = array[end], temp;
for(int i=start; i<end; i++){
if(array[i].compareTo(pivot)<=0){
// Swap array[pIndex] and current element.
temp = array[i];
array[i] = array[pIndex];
array[pIndex] = temp;
pIndex++;
}
}
// Swap pivot(array[end]) and array[pIndex]
temp = array[pIndex];
array[pIndex] = array[end];
array[end] = temp;
return pIndex;
}
}