public static void main(String[] args) {
int n[] = {23, 5, 69, 87, 4, 2, 62, 1};
for(int i=0;i<n.length;i=i+1){
System.out.println(n[i]);
}
// 単純ソート(O(N^2)の計算量が必要)のソースコードはこのコメントアウトの部分
// for(int i=0;i<n.length;i++){
// int min=n[i];
// for(int j=i+1;j<n.length;j++){
// if(n[j]<min){
// int tempmin=min;
// min=n[j];
// n[j]=tempmin;
// }
// }
// n[i]=min;
// }
mergeSort(n);
System.out.println("Sorted");
for(int i=0;i<n.length;i++){
System.out.println(n[i]);
}
}
public static void mergeSort(int[] a){
if(a.length>1){
int n1 = a.length/2;
int n2 = a.length - n1;
int[] a1 = new int[n1];
int[] a2 = new int[n2];
for(int i=0; i<n1; i++){
a1[i]=a[i];
}
for(int i=0; i<n2; i++){
a2[i]=a[n1+i];
}
mergeSort(a1);
mergeSort(a2);
merge(a1,a2,a);
}
}
public static void merge(int[] a1, int[] a2, int[] a){
int n1 = 0;
int n2 = 0;
while( n1 < a1.length || n2 < a2.length){
if(n2 == a2.length || (n1 < a1.length && a1[n1]<a2[n2])){
a[n1+n2]=a1[n1];
n1++;
}else{
a[n1+n2]=a2[n2];
n2++;
}
}
}
public static void quickSort(int[] a, int l, int r){
if(l>=r){
return;
}
int base = a[l];
int left=l;
int right=r;
while(true){
if(left>right){
break;
}
while(true){
if(a[left]>=base){
break;
}
left++;
}
while(true){
if(a[right]<=base){
break;
}
right--;
}
int temp=a[left];
a[left]=a[right];
a[right]=temp;
left++;
right--;
}
quickSort(a, l, right);
quickSort(a, left, r);
}
public static void main(String[] args) {
int n[] = {23, 5, 69, 87, 4, 2, 62, 1};
quickSort(n, 0, n.length - 1);
}