11章の問題11

配列を基準値との大小関係で分割する.

とりあえず普通の分割.
xs[0]未満の要素を左に集める.

// 基準要素(配列の先頭)未満の要素を先頭に移動する
void split2(int * xs, int l, int u){
	if(l>u){
		return ;
	}

	int t = xs[l]; // 基準
	int m = l;   // t< 要素の左端
	cout << "basis :" << t << endl;

	for(int i=l+1; i<u; i++){

		if(xs[i] < t){
			int temp(xs[++m]);
			xs[m] = xs[i];
			xs[i] = temp;
		}
		print_array(xs, u-l);
	}

	int temp(xs[l]);
	xs[l] = xs[m];
	xs[m] = temp;
	print_array(xs, u-l);
	
	return ;
}

次が本題.
基準値t(xs[0])と比較して, {未満,tと等しい,tより大きい}のように配列を分割する.

void split3(int * xs, int l, int u){
	if(l>u){
		return ;
	}
	int t = xs[l]; // 基準
	int m = l;   // t未満の要素の左端
	int n = l;   // tと等しい要素の左端

	for(int i=l+1; i<u; i++){
		// 配列のソート済みの部分の構造
		// [基準(t)] ++ [x\\x<-xs|x<t] ++ [x\\x<-xs|x==t] ++ [x\\x<-xs|t<x]
		assert(m<=n && n<=i);

		if(xs[i] < t){
			int temp(xs[++m]);
			xs[m] = xs[i];
			xs[i] = xs[++n];
			xs[n] = temp;
		}else if(xs[i]==t){
			int temp(xs[++n]);
			xs[n] = xs[i];
			xs[i] = temp;
		}
		print_array(xs, u-l);
	}

	// 基準に使用した要素を中央に移動
	int temp(xs[l]);
	xs[l] = xs[m];
	xs[m] = temp;
	print_array(xs, u-l);
	
	return ;
}

始めうまくいかなくて,本文に倣ってassert入れてみたw
(結局それとは関係なかったけど)