# 練習問題の解答例　3日目

## マージソートの例

<code java>
	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++;
			}
		}
	}
</code>

## クイックソートの例

<code java>
	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);
        }
</code>