【Java】マージソート

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

マージソート

package chap06;

import java.util.Scanner;

public class MergeSort {
	
	// 変数の宣言
	static int[] buff;    // 作業用配列
	
	//--- a[left]～a[right]を再帰的にマージソートを行う ---//
	static void __mergeSort(int[] a, int left, int right) {
		
		if (left < right) {
			int i ;
			int center = (left + right) / 2;
			int p      = 0;
			int j      = 0;
			int k      = left;
			
			
			// 半分にしたうちの左側をマージソートする
			__mergeSort(a, left, center);
			
			// 半分にしたうちの右側をマージソートする
			__mergeSort(a, center + 1, right);
			
			
			// 作業用配列に半分にしたうちの左側の配列をコピーする
			for (i = left; i <= center; i++) {
				buff[p++] = a[i];
				
				// for文終了後にi = center + 1になっていることに注意
			}
			
			
			//--- 再帰的にソートされた2つの配列から小さい順に元の配列に要素を格納していく ---//
			// 作業用配列の最後尾jがp未満のとき
			while (i <= right && j < p) {
				
				// 参考書内の記述
				// a[k++] = (buff[j] <= a[i] ? buff[j++] : a[i++]);
				
				// 作業用配列buff[j]がa[i](半分にしたうちの右側の配列)以下なら
				if (buff[j] <= a[i]) {
					
					// a[k]にbuff[j]を格納してkとjをインクリメント
					a[k++] = buff[j++];
				} else {
					
					// a[k]にa[i]を格納してkとiをインクリメント
					// 元の配列aに後半の配列の配列を横入りさせるイメージ
					a[k++] = a[i++];
				}
			}
			
			// 半分にしたうちの左側の配列が残っているとき
			while (j < p) {
				
				// 残りの左側の配列を格納する。
				a[k++] = buff[j++];
			}
		}
	}
	
	//--- マージソート ---//
	static void mergeSort(int[] a, int n) {
		buff = new int[n];           // 作業用配列を生成
		
		__mergeSort(a, 0, n - 1);    // 配列全体をマージソート
		
		buff = null;
	}
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("マージソート");
		System.out.print("要素数：");
		int   nx = stdIn.nextInt();
		int[] x  = new int[nx];
		
		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]：");
			x[i] = stdIn.nextInt();
		}
		
		mergeSort(x, nx);    // 配列xをマージソート
		
		System.out.println("昇順にソートしました。");
		
		for (int i = 0; i < nx; i++)
			System.out.println("x[" + i + "]=" + x[i]);
	}


}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

• staticメソッド

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。