読者です 読者をやめる 読者になる 読者になる

感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

【プログラミング 61時間目】オバマとGoogleCEOのやりとりで話題となったバブルソートとは何か?

<スポンサーリンク>

オバマとGoogleCEOのやりとりで話題となったバブルソートとは何か?

2007年11月、当時民主党の大統領候補だったバラク・オバマは演説のため、
カリフォルニア州マウンテンヴューのグーグル本社を訪れていた。
現在、ウェブサイトテスト企業OptimizelyのCEOを務めるシロカーだが、
当時はグーグルブラウザー開発チームのプロダクトマネジャーだった。
彼は裏口から忍び込んで長い行列に紛れ込もうと試みた。
「警備員に『中で会議がある』って言ったんです」とシロカーは回想する。
本当は会議などなかった。だがこのハッタリが功を奏して、中に入ることができた。

質疑応答で、オバマは当時のCEO、エリック・シュミットのジョークに的確な答えを返した。
「100万の32ビット整数を効果的にソートするにはどうすればよいと思われますか?」。
それはただの「つかみ」で、すぐ真面目な質問に移るつもりだったのだが、
オバマは次の言葉をさえぎって、「そうですね、バブルソートを使うのは間違いでしょう」と答えた。
それは正解だった。
シュミットは信じられないといったふうに額に手を当てた。満場の拍手喝采。シロカーはその場に打ちのめされた。
「“バブルソート”には参りましたよ」。2週間後、彼はグーグルを休職してシカゴへ行き、
デジタルアドヴァイザーとしてオバマの選挙キャンペーンに加わることになる。

(引用元)http://wired.jp/2012/12/29/abtest_vol5-2/

さて、このオバマが笑いながら言った「バブルソート」とはなんでしょう?
バブルソート(bubble sort)とは、単純に隣同士を比較していく並べ替え作業のことです。
液体より軽い気体が上に上がっていくように、値が低いもの(あるいは高いもの)が上に上がっていくようなイメージでソートするため、バブルソートと呼びます。


例えば、10人の小学生(A君からJ君)がいたとして、一列に並んではいるものの、順番はバラバラであるとします。
こいつらを身長が高い順に並べ替えたいときはどうするか?

バブルソートでは、隣同士を比較して並べ替えます。
隣同士の比較を(人数 - 1)回繰り返します。
図にするとこんな感じ。

こうすると、「1番先頭は1番大きい人」になります。
一連の比較・交換の作業をパスと呼びます。

次に、2番目に背の高い人を2番目にします。
上の同じ作業を今度は(人数 - 2)回繰り返します。

これを人数分繰り返せば、背の順に並べ替えられるはずです。

これをプログラムで表すとこうなります。

package algorism;

public class BubbleSortTest {
	public static void main(String[] args) {
		
		//A君からJくんの身長を入れる配列
		int[] height = {150,142,165,130,144,158,160,135,121,155};
		
		System.out.println("並べ替える前の値を表示します");
		for(int i=0; i<height.length;i++) {
			if(i < height.length -1 ) {
				System.out.print(height[i] + ",");
			} else {
				System.out.println(height[i]);
			}
		}
		int[] sortedHeight = new int[height.length];
		sortedHeight = bubbleSort(height);
		
		System.out.println("並べ替えた値を表示します");
		for(int i=0; i<sortedHeight.length;i++) {
			if(i < sortedHeight.length -1 ) {
				System.out.print(sortedHeight[i] + ",");
			} else {
				System.out.print(sortedHeight[i]);
			}
		}
	}
	
	private static int[] bubbleSort(int[] sortArray) {
		int n = sortArray.length;
		//iは配列の先頭のイメージ
		for (int i = 0; i < n-1; i++) {
			//jは配列の1番最後の箱のイメージ
			//後ろからどんどん前に向かって比較を繰り返すイメージ
			for (int j = n-1; j > i; j--) {
				//1番最後と最後から2番めの配列の値を比較している
				if(sortArray[j - 1] < sortArray[j])
					sortArray = swap(sortArray, j - 1, j);
			}
		}
		return sortArray;
	}
	
	private static int[] swap(int[] targetArray, int lowerIndex, int BiggerIndex) {
		//低い値のインデックスを一旦保存して
		int exchangeIndex = targetArray[lowerIndex];
		//高い値のインデックスの値を低いやつと入れ替える
		targetArray[lowerIndex] = targetArray[BiggerIndex];
		//保存しておいた低い値を高いインデックスに入れる
		targetArray[BiggerIndex] = exchangeIndex;
		//入れ替えた配列を返す
		return targetArray;
	}
}

表示される結果はこのように、ソートされた(=並べ替えられた)ものとなります。

並べ替える前の値を表示します
150,142,165,130,144,158,160,135,121,155
並べ替えた値を表示します
165,160,158,155,150,144,142,135,130,121

これがバブルソートです。
見てわかるようにとても非効率な並べ替え方なため、オバマは

「そうですね、バブルソートを使うのは間違いでしょう」

と答えたのです。

アルゴリズムをもっと勉強するならこちら。

明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造