マージソートのアルゴリズムを実装してみた

ソート(並び替え)のアルゴリズムの勉強編。

今回は「マージソート」を実装してみました。

マージソートがどんなものか知りたい方は、
動画で見た方が分かりやすいので、こちらでご確認ください。
https://www.youtube.com/watch?v=RrQO9qse3h8

これをプログラムで実装すると、こうなります。

package sort;

/**
 * マージソート
 */
public class MergeSort {

	public static void main(String[] args) {
		
		int array[] = {7, 4, 9, 2, 3, 8, 6, 1, 5};
		
		arrayPrint(array);
		sort(array);
		
	}
	
	/**
	 * ソート処理
	 * @param array 配列
	 */
	static public void sort(int[] array) {
		
		int length = array.length;
		
		if (1 < length) {
			int leftSize = length / 2;
			int rightSize = length - leftSize;
			
			int[] leftArray = new int[leftSize];
			int[] rightArray = new int[rightSize];
			
			for (int i = 0; i < leftSize; i++) {
				leftArray[i] = array[i];
			}
			for (int i = 0; i < rightSize; i++) {
				rightArray[i] = array[i + leftSize];
			}
			
			sort(leftArray);
			sort(rightArray);
			
			merge(leftArray, rightArray, array);
		}
	}
	
	/**
	 * マージ処理
	 * @param leftArray
	 * @param rightArray
	 * @param array
	 */
	static public void merge(int[] leftArray,int[] rightArray,int[] array) {
		
		int leftCount = 0;
		int rightCount = 0;
		
		int leftLength = leftArray.length;
		int rightLength = rightArray.length;
		
		// 本物の配列に挿入していく
		while (leftCount < leftLength || rightCount < rightLength) {
			
			int totalCount = leftCount + rightCount;
			
			if (rightLength <= rightCount) {
				// 右の配列が終了していたら、無条件で左の配列を挿入
				array[totalCount] = leftArray[leftCount];
				leftCount++;
				arrayPrint(array);
			} else if (leftCount < leftLength && leftArray[leftCount] < rightArray[rightCount]) {
				// 左の配列が小さい場合、左の配列を挿入
				array[totalCount] = leftArray[leftCount];
				leftCount++;
				arrayPrint(array);
			} else {
				// 右の配列が小さい場合、右の配列を挿入
				array[totalCount] = rightArray[rightCount];
				rightCount++;
				arrayPrint(array);
			}
		}
	}
	/**
	 * 配列入れ替え用
	 * @param array 配列
	 * @param num1
	 * @param num2
	 */
	static public void swap(int array[], int num1, int num2) {
		
		int tmp = array[num1];
		array[num1] = array[num2];
		array[num2] = tmp;
		
		arrayPrint(array);
	}
	
	/**
	 * 配列出力用
	 * @param array
	 */
	static public void arrayPrint(int array[]) {
		int count = 0;
		for (int a : array) {
			System.out.print(a);
			count++;
			if (count != array.length) {
				System.out.print(", ");
			}
		}
		System.out.println();
	}
}

実行結果のソートの過程を載せておきます。

7, 4, 9, 2, 3, 8, 6, 1, 5
4, 4
4, 7
2, 2
2, 9
2, 4, 9, 2
2, 4, 9, 2
2, 4, 7, 2
2, 4, 7, 9
3, 8
3, 8
1, 5
1, 5
1, 1, 5
1, 5, 5
1, 5, 6
1, 8, 6, 1, 5
1, 3, 6, 1, 5
1, 3, 5, 1, 5
1, 3, 5, 6, 5
1, 3, 5, 6, 8
1, 4, 9, 2, 3, 8, 6, 1, 5
1, 2, 9, 2, 3, 8, 6, 1, 5
1, 2, 3, 2, 3, 8, 6, 1, 5
1, 2, 3, 4, 3, 8, 6, 1, 5
1, 2, 3, 4, 5, 8, 6, 1, 5
1, 2, 3, 4, 5, 6, 6, 1, 5
1, 2, 3, 4, 5, 6, 7, 1, 5
1, 2, 3, 4, 5, 6, 7, 8, 5
1, 2, 3, 4, 5, 6, 7, 8, 9

ソートのアルゴリズム勉強編。
マージソートのプログラムの紹介でした。

参考になれば幸いです。