テスト駆動開発の練習(8) -Java&JUnit4でバブルソート＆コムソート-

なんか難易度前回より下がった？アルゴリズムの王道、ソートからこれまたソートの王道の一つ、バブルソートを実装してみる。いわゆるところ、久々に手を動かしてソートのプログラム書いてみようって話。

ちなみにそんなソートプログラムでも収穫はありました。
Javaの配列のコピーのためのメソッドclone()を習得できました(「ああ、こんなものもあった気が…」という記憶が無くもない)。しかしながら、なんか味気ない。

そういうわけで、ソートをするクラスのabstractクラスを作って、ついでにバブルソートの改良版、コムソートも実装してみました。
まあ、ソートなので結局テストすることは一緒です。なのでコムソートの方のテストコードは省略します。

public abstract class AbstractSort {

	int[] sortedArray;

	protected AbstractSort(int[] array){
		sortedArray = array.clone();
		sort();
	}

	protected abstract void sort();
	
	public int[] getSortedArray(){
		return sortedArray;
	}
}

AbstractSort

public class BubbleSort extends AbstractSort {

	public BubbleSort(int[] array){
		super(array);
	}
	
	protected void sort(){
		int t;
		for(int i = 0; i < sortedArray.length-1; i++){
			for(int j = sortedArray.length-1; j > i; j--){
				if(sortedArray[j]<sortedArray[j-1]){
					t = sortedArray[j];
					sortedArray[j] = sortedArray[j-1];
					sortedArray[j-1] = t;
				}
			}
		}
	}
}

BubbleSort

public class ComSort extends AbstractSort{
	
	public ComSort(int[] array){
		super(array);
	}
	
	protected void sort(){
		int h = sortedArray.length * 10 / 13;
		if(h == 9 || h == 10){
			h = 11;
		}
		
		while(true){
			int swaps = 0;
			for(int i = 0; i + h < sortedArray.length; i++){
				if(sortedArray[i] > sortedArray[i+h]){
					int t = sortedArray[i];
					sortedArray[i] = sortedArray[i+h];
					sortedArray[i+h] = t;
					swaps++;
				}
			}
			if(h == 1){
				if(swaps == 0){
					break;
				}
			}
			else{
				h = h *10 / 13;
			}
		}
	}
}

ComSort

import org.junit.*;
import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.assertThat;

public class BubbleSortTest {
	BubbleSort bs;

	@Before
	public void initBubbleSort(){
		int[] a = {5, 4, 3, 2, 1};
		bs = new BubbleSort(a);
	}

	@Test
	public void testGetSortedArray(){
		int[] a = {1, 2, 3, 4, 5};
		assertThat(bs.getSortedArray(), is(a));
	}
}

BubbleSortTest

ちなみにコムソートはWikipediaにコードが…書く前に見つけてしまったので、Wikipediaのコードを参考に書いてみました。(自力で書こうとしましたが参考にしているうちに、ほぼ同じコードに収束してしまいました…残念)


追記:あとで気がついたんですが、今回のテストコードの入力値ってソート時に全て入れ替えを行う場合ですよね。入れ替えを行わないような部分がある配列を渡しておいた方がテストとしては良かったのでは、と思いました。たとえば{4,5,3,2,1}とか。次からは気をつけてみたいところです。

追記:またまた友人からの貴重な助言。

@Beforeのメソッドでしていた処理を、別のメソッドをつくってそのメソッドで生成したAbstractSortのインスタンスを返すようにした方がいいのでは？ということで、リファクタリングしてみます。

public class BubbleSortTest {

	@Test
	public void testGetSortedArray(){
		assertThat(initBubbleSort(new int[]{5, 4, 3, 2, 1}).getSortedArray(),
				is(new int[]{1, 2, 3, 4, 5}));
	}

	private AbstractSort initBubbleSort(int[] input){
		return new BubbleSort(input);
	}
}

たしかにこちらの方がすっきりしている・・・。

C++ではあまりインスタンスを返すというのが(メモリリークの心配とかで)気持ちのいいものではないのであまりやらない癖がついていましたが、Javaはガベージコレクタのおかげでその辺りは気にしなくて済みますね。


追記:pbskさんのコメントでの忠告に従って、ソースコードを書き換えました。

---

旧コメント：
気になったので3点ほど

---

コードを眺めていて気になったことを3つほど。

1. getSortedArrayってスーパークラスに処理書いてよいのでは？
2. サブクラスごとにコンストラクタでsortメソッドを呼び出しているが、スーパークラスのコンストラクタに記述してもよいのでは？

この2つは、今後サブクラスごとに異なる処理を上2つのメソッドに追加するなら話は別かもしれませんが。
（getterの処理がサブクラスごとに異なるのは、個人的にはそれはそれでアレだと思いますが・・・）

3. 配列を宣言する際の括弧の位置を統一したほうが読みやすいかも
sortedArrayのみ名前の後ろに括弧がついていたので、ちょっと気になりました。

2011-02-11 07:43 | pbsk

Re: 気になったので3点ほど

---

> コードを眺めていて気になったことを3つほど。
>
> 1. getSortedArrayってスーパークラスに処理書いてよいのでは？
> 2. サブクラスごとにコンストラクタでsortメソッドを呼び出しているが、スーパークラスのコンストラクタに記述してもよいのでは？
>
> この2つは、今後サブクラスごとに異なる処理を上2つのメソッドに追加するなら話は別かもしれませんが。
> （getterの処理がサブクラスごとに異なるのは、個人的にはそれはそれでアレだと思いますが・・・）
>
> 3. 配列を宣言する際の括弧の位置を統一したほうが読みやすいかも
> sortedArrayのみ名前の後ろに括弧がついていたので、ちょっと気になりました。

すべて確かにその通りですね。記事の方のコードを書き換えておきます。
貴重なご助言、ありがとうございます。

2011-02-11 07:49 | Naoki Rin