-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSorting.java
More file actions
119 lines (86 loc) · 2.93 KB
/
Copy pathSorting.java
File metadata and controls
119 lines (86 loc) · 2.93 KB
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.util.Optional;
import java.util.Random;
import java.util.function.Function;
public class Sorting {
//worst case: o(n2) very rare only when pivot lies either on least or highest element. Otherwise, its O(n log n)
public int[] QuickSort(int[] arr, int low, int high) {
if (arr == null || arr.length == 0)
return null;
if (low >= high)
return null;
// pick the pivot
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
//loop through until you find an element less than the pivot.
while (arr[i] < pivot) {
i++;
}
//loop through until you find an element greater than the pivot
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
//swapping
int temp = arr[i];
arr[i] =arr[j];
arr[j]=temp;
//move index to next location
i++;
j--;
}
}
// recursively sort two sub parts
if (low < j)
QuickSort(arr, low, j);
if (high > i)
{
QuickSort(arr, i, high);
}
return arr;
}
//Time Complexity: average = O(n); worse O(n^2)
public int QuickSelect(int[] array, int low, int high, int k ) {
if(array.length == 0) {
return -1;
}
if(low > high) {
return -1;
}
int middle = low + (high - low) / 2;
int i = 0;
int pivot = array[middle];
while( i <= high ) {
int newPivot = Partition( array, low, high, k);
i++;
if(newPivot == k )
return array[newPivot];
}
}
private static void Swap(int[] array, int i, int j) {
int temp = i;
i =array[j];
array[j]=temp;
}
private static int Partition(int[] array, int low, int high, int k) {
int middle = low + (high - low) / 2;
int left = low, right=high;
int pivot = array[middle];
while(left <= high) {
//loop through the array until the values smaller than the pivot.
while(array[left] < pivot) {
left++;
}
//loop through the array until the values greater than the pivot.
while(array[right]> pivot) {
right++;
}
//swap
if(left <= high) {
Swap(array,left,high);
}
}
}
}