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
(結局それとは関係なかったけど)