forked from srinathr91/TestJava
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSort1.java
More file actions
129 lines (118 loc) · 2.51 KB
/
Sort1.java
File metadata and controls
129 lines (118 loc) · 2.51 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
120
121
122
123
124
125
126
127
128
129
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
public class Sort1 {
public static long count=0;
public static int[] quickSort(int[] ar,int l, int r){
if(ar.length==1){
return ar;
}
if(l<r){
int p= Sort1.partition(ar, l, r);
count=count+r-l+1-1;
quickSort(ar, l,p-1);
quickSort(ar, p+1,r);
}
return ar;
}
public static int leftpivot(int[] ar,int l, int r){
return l;
}
public static int rightpivot(int[] ar,int l, int r){
//exchange
int temp11=ar[l];
ar[l]=ar[r];
ar[r]=temp11;
//end
return l;
}
public static int medianpivot(int[] ar,int l, int r){
// median-of-three rule
int a= r-l+1;
int mid;
if(a%2==0){
mid=l+(a/2)-1;
}else{
mid=l+(a/2);
}
int[] comp=new int[3];
comp[0]=ar[l];
comp[1]=ar[mid];
comp[2]=ar[r];
int index=l;
Arrays.sort(comp);
if(comp[1]==ar[l]){
index=l;
}else if(comp[1]==ar[mid]){
index=mid;
}else if(comp[1]==ar[r]){
index=r;
}
int temp11=ar[l];
ar[l]=ar[index];
ar[index]=temp11;
//end of 3-median
return l;
}
public static int partition(int[] ar,int l, int r){
int pivot= ar[rightpivot(ar,l,r)];
int i=l+1;
for(int j=l+1; j<=r;j++){
if(ar[j]<pivot){
int temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
i++;
}
}
int temp1=ar[i-1];
ar[i-1]=pivot;
ar[l]=temp1;
return i-1;
}
//second method- According to corman
public static int partition1(int[] ar,int l, int r){
int pivot= ar[r];
int i=l-1;//l;
for(int j=l; j<r;j++){
if(ar[j]<pivot){
i++;
int temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
//i++;
}
}
int temp1=ar[i+1];
ar[i+1]=pivot;
ar[r]=temp1;
return i+1;
}
public static void main(String[] args){
try {
BufferedReader br=new BufferedReader(
new FileReader("C:/Users/srinath/Desktop/Amazon/Design_analysis/week_2/QuickSort.txt"));
int[] arr=new int[10000];
int[] arr1={3,8,2,5,1,4,7,6};
String line=null;
int i=0;
//loading the array
while((line=br.readLine())!=null){
arr[i]=Integer.parseInt(line);
i++;
}
for(int it: Sort1.quickSort(arr, 0, arr.length-1)){
System.out.println(it);
}
System.out.println(Sort1.count);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}