- ベストアンサー
クイックソートの考え方？
KG_の回答
ちょっと長いですが、こういうことでは。 (位置の値は、検索範囲の左から数えて何番目かです。) 13が基準値 [ 10 20 11 19 13 17 14 16 15 ] 左から比べていって13以上なのは20(位置2) 右から比べていって13以下なのは11(位置3) 双方を入れ換える。 [ 10 11 20 19 13 17 14 16 15 ] 最後の位置を開始位置とし、さらに比べます 左から比較している位置2と、右から比較している位置3が すれ違うので（又は同じ位置）、そこで、エリアをわける [ 10 11 ][ 20 19 13 17 14 16 15 ] ＜左のエリアからさらに同じように繰り返す＞ 11が基準値 左から比べていって11以上なのは11(位置2) 右から比べていって11以下なのは11(位置2) すれ違うので（又は同じ位置）、そこでエリアをわける [ 10 ][ 11 ][ 20 19 13 17 14 16 15 ] 要素が１になったエリアはさわらない。 ＜右のエリアからさらに同じように繰り返す＞ 17が基準値 左から比べていって17以上なのは20(位置1) 右から比べていって17以下なのは15(位置7) 双方を入れ換える。 [ 10 ][ 11 ][ 15 19 13 17 14 16 20 ] 最後の位置を開始位置とし、さらに比べます 位置1から左へ比べていって17以上なのは19(位置2) 位置7から右へ比べていって17以下なのは16(位置6) 双方を入れ換える。 [ 10 ][ 11 ][ 15 16 13 17 14 19 20 ] 最後の位置を開始位置とし、さらに比べます 位置2から左へ比べていって17以上なのは17(位置4) 位置6から右へ比べていって17以下なのは14(位置5) 双方を入れ換える。 [ 10 ][ 11 ][ 15 16 13 14 17 19 20 ] 最後の位置を開始位置とし、さらに比べます 左から比較している位置4と、右から比較している位置5が すれ違うので（又は同じ位置）、そこで、エリアをわける [ 10 ][ 11 ][ 15 16 13 14 ][ 17 19 20 ] ＜[15～14]のエリアを同じように処理する＞ ここからは要素の入換えだけ書き込みます。 基準値13 [ 10 ][ 11 ][ 15 16 13 14 ][ 17 19 20 ] [ 10 ][ 11 ][ 13 16 15 14 ][ 17 19 20 ] [ 10 ][ 11 ][ 13 ][ 16 15 14 ][ 17 19 20 ] ＜[ 16 15 14 ]のエリアを同じように処理する＞ 基準値15 [ 10 ][ 11 ][ 13 ][ 16 15 14 ][ 17 19 20 ] [ 10 ][ 11 ][ 13 ][ 14 15 16 ][ 17 19 20 ] [ 10 ][ 11 ][ 13 ][ 14 ][ 15 16 ][ 17 19 20 ] ＜[ 15 16 ]のエリアを同じように処理する＞ 基準値16 [ 10 ][ 11 ][ 13 ][ 14 ][ 15 16 ][ 17 19 20 ] [ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 19 20 ] ＜[ 17 19 20 ]のエリアを同じように処理する＞ 基準値19 [ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 19 20 ] [ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 ][ 19 20 ] ＜[ 17 19 20 ]のエリアを同じように処理する＞ 基準値20 [ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 ][ 19 20 ] [ 10 ][ 11 ][ 13 ][ 14 ][ 15 ][ 16 ][ 17 ][ 19 ][ 20 ] すべての要素が１になったので終了。 #長年この考え方でやっているのだが、人に教えるとなると自信がない(~_~;
関連するQ&A
- クイックソートのソート
2 8 7 1 3 5 6 4 という数字が並んでいて ４を基準に左から昇順にクイックソートするとしたら 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4 2 1 7 8 3 5 6 4 (1) 2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4 2 1 3 4 8 7 5 6 8 というふうになりますが (1)の状態は８と７が交換されていますが これは間違いなのでしょうか 教科書に載っていたのですが
- ベストアンサー
- その他([技術者向] コンピューター)
- クイックソートがうまくいかない
クイックソートの仕様はこうです。 (1)バラバラにランダムで入力した配列から基準値を設定する。 (2)前から順番に辿って行って基準値よりも大きいならば、基準値よりも後に移動、小さいならば、基準値よりも前に移動させる。（私のプログラムの場合は基準値を配列の一番目の数に設定しています。） (3)小さいほうと大きいほうの二つのグループに分かれたらまたそれらのグループごとにクイックソートにかける。 (4)二つのグループを分けることができなくなればソート完了。 動作させてみたところ関数QuickSortの中の「基準値より大きいか小さいかの仕分けの処理」の後で、再帰処理があるのですが、再帰ではなく無限ループになってしまっているようです。 自分では、この処理で無限ループをとめているつもりです。 if(youso==1) { return; } なぜこのようになってしまうのでしょうか お手数ですが、よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #define N 10 int k,q; void QuickSort(char mi,char hai[10],int youso) { char shoubox[10]; char bigbox[10]; int i,len,len2; k=0,q=0; /*もし配列haiの大きさが1ならば終了*/ if(youso==1) { return; } /*配列の２番目から最後まで基準値からの大小により仕分けしていく。大きいならば、配列bigboxに小さい*/ /*ならば配列shouboxにそれぞれ入れる。*/ for(i=1;i<youso;i++) { if(hai[i]>mi) { bigbox[k++]=hai[i]; } else { shoubox[q++]=hai[i]; } } /*仕分け処理はここまで*/ /*小さいほうの配列と大きいほうの配列をそれぞれクイックソートにかける再帰処理。*/ QuickSort(shoubox[0],shoubox,q); QuickSort(bigbox[0],bigbox,k); /*それぞれのソートが完了したら、配列haiに「小さいほうの配列」→「基準値」→「大きいほうの配列」 の順に値を代入していく。*/ len=strlen(shoubox); for(i=0;i<len;i++) { hai[i]=shoubox[i]; } hai[len]=mi; len2=strlen(bigbox); for(i=(len+1);i<len+len2;i++) { hai[i]=bigbox[i]; } /*代入処理ここまで。*/ } int main(void) { char array[N]; char m; int i,val,j; srand(time(NULL)); /*(1～10)までの数字をランダムに入力する処理*/ for(i=0;i<N;i++) { do{ val=rand()%10; for(j=0;j<i;j++) { if(val+'0'==array[j]) { break; } } }while(j<i); array[i]=val+'0'; } /*ランダムに値を入力する処理ここまで*/ m=array[0]; /*値配列の最初を基準値mに設定*/ QuickSort(m,array,N); /*基準値、配列、要素数を実引数として、クイックソートを呼び出す。*/ /*昇順に並べ替えた配列arrayを出力する。*/ for(i=0;i<N;i++) { printf("array[%d]=%c\n",i,array[i]); } return 0; }
- 締切済み
- C・C++・C#
- クイックソートがうまくいかない
クイックソートとはこういう仕様のソートのことです。 (1)バラバラの配列から基準値を設定する。 (2)前から順番に辿って行って基準値よりも大きいならば、基準値よりも後に移動、小さいならば、基準値よりも前に移動させる。（私のプログラムの場合は基準値を配列の一番目の数に設定しています。） (3)小さいほうと大きいほうの二つのグループに分かれたらまたそれらのグループごとにクイックソートにかける。 (4)二つのグループを分けることができなくなればソート完了。 自分で確かめてみたのですが、どうやら関数QuickSortの中でさらに再帰的にQuickSortにかけるときにバグが発生しているようです。ですが、なぜバグが起きるのかわかりません。 お手数ですが、よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #define N 10 void QuickSort(char mi,char *hai,int youso) { char *shoubox; char *bigbox; int k=0; int q=0; int i,len,len2; /*もし配列haiの大きさが1ならば終了*/ if(strlen(hai)==1) { return; } /*配列の２番目から最後まで基準値からの大小により仕分けしていく。大きいならば、配列bigboxに小さい*/ /*ならば配列shouboxにそれぞれ入れる。*/ for(i=1;i<youso-1;i++) { if(hai[i]>mi) { bigbox[k++]=hai[i]; } else { shoubox[q++]=hai[i]; } } /*仕分け処理はここまで*/ /*小さいほうの配列と大きいほうの配列をそれぞれクイックソートにかける再帰処理。*/ QuickSort(shoubox[0],shoubox,q); QuickSort(bigbox[0],bigbox,k); /*それぞれのソートが完了したら、配列haiに「小さいほうの配列」→「基準値」→「大きいほうの配列」 の順に値を代入していく。*/ len=strlen(shoubox); for(i=0;i<len;i++) { hai[i]=shoubox[i]; } hai[len]=mi; len2=strlen(bigbox); for(i=(len+1);i<len+len2;i++) { hai[i]=bigbox[i]; } /*代入処理ここまで。*/ } int main(void) { char array[N]; char m; int i,val,j; srand(time(NULL)); /*(1～10)までの数字をランダムに入力する処理*/ for(i=0;i<N;i++) { do{ val=rand()%10; for(j=0;j<i;j++) { if(val+'0'==array[j]) { break; } } }while(j<i); array[i]=val+'0'; } /*ランダムに値を入力する処理ここまで*/ m=array[0]; /*値配列の最初を基準値mに設定*/ QuickSort(m,array,N); /*基準値、配列、要素数を実引数として、クイックソートを呼び出す。*/ /*昇順に並べ替えた配列arrayを出力する。*/ for(i=0;i<N;i++) { printf("array[%d]=%c\n",i,array[i]); } return 0; }
- 締切済み
- C・C++・C#
- クイックソートの解説頂けないでしょうか。
C言語を始めたばかりのプログラマ見習いです。 クイックソートのトレースでつまっています。 下記プログラムにあたっているのですが、 どなたか解説頂けないでしょうか。 void q_sort(int d[],int left,int right) { int i=left; int j=right; int t; t=d[(i+j)/2]; while(i<j){ for(;t>d[i];i++) ; for(;t<d[j];j--) ; if(i<=j){ /*Swap*/ int t; t=d[i]; d[i]=d[j]; d[j]=t; i++; j--; } } if(left<j){ q_sort(d,left,j); } if(){ q_sort(d,i,right); } } 長い引用で申し訳ありません。 クイックソートの理論的な部分は理解しているつもりです (最初に基準値を置き、それより大きいもしくは小さい 値を左右に振り分ける→分割統治法で繰り返し、最終的に 値がソートされた状態になる)。 よく判らないのがwhile文の中、特に最初のfor文の 役割です。初期値が空文で、中身もなし・・・この文は なにをしているのでしょうか？ ネット上で解説されているソースをのぞいてみましたが 少し形が違っていたので、できればこのプログラムを もとにアドバイス頂けないでしょうか。 それ以外の回答(参考URL等)でも嬉しいです。 どうぞ宜しくお願いします
- ベストアンサー
- C・C++・C#
- クイックソートをC++で作りたいのですが・・・
題の通り、C++でクイックソートを作りたいのですが、以下のコードではセグメンテーションエラーで動きませんでした。partition関数があやしいと思い、色々と試してみたのですが、やはりできなかったので、質問させていただくことにしました。 結果としては、print関数で昇順に表示出来ればいいのですが・・・。 以下のコードのどこをどう変えれば良いのか、ご指摘の方、何卒よろしくお願い致します。 #include <iostream> #include <vector> using namespace std; class Array { private: vector<int> array; public: void insert( int value ){ array.push_back( value ); } int getSize( ){ return (int)array.size( ); } void quick_sort( ){ quick_sort( 0, (int)array.size( ) - 1 ); } void quick_sort( int left, int right ); int partition( int left, int right ); void swap(int *a,int *b){int tmp=*a;*a=*b;*b=tmp;} void print( ); }; // クイックソートにより配列の添字 left ～ right の部分を整列する関数 void Array::quick_sort( int left, int right ) { if ( left >= right ) { return; } int v = partition( left, right ); quick_sort( left, v - 1 ); quick_sort( v + 1, right ); } //この関数を考える // 配列の添字 left ～ right の部分を，pivot の値より小さい要素と，大きい要素に分割し pivot の位置を返す関数 int Array::partition( int left, int right ) { int i=left; //左からの処理位置 int j=right; //右からの処理位置 int pivot=array[(int)(left+right)/2]; //基準 int tmp=0; while(true){ while(array[i]<pivot){i++;} while(array[j]>pivot){j--;} if(i>=j){return i;} tmp=array[i]; array[i]=array[j]; array[j]=tmp; i++; j++; } } // 配列の内容を表示する関数 void Array::print( ) { for ( int i = 0; i < (int)array.size( ); i++ ) { cout << array[i] << " "; } cout << endl; } int main( ) { Array a1; a1.insert( 56 ); a1.insert( 34 ); a1.insert( 57 ); a1.insert( 64 ); a1.insert( 3 ); a1.insert( 87 ); a1.insert( 85 ); a1.insert( 37 ); a1.insert( 21 ); a1.insert( 4 ); a1.insert( 68 ); a1.insert( 62 ); a1.insert( 42 ); a1.insert( 55 ); a1.insert( 63 ); a1.insert( 95 ); a1.insert( 7 ); a1.insert( 32 ); a1.insert( 78 ); a1.insert( 11 ); cout << "要素数: " << a1.getSize( ) << endl; cout << "ソート前: "; a1.print( ); a1.quick_sort( ); // ここで，ソートを行う関数を呼び出す cout << "ソート後: "; a1.print( ); return 0; }
- ベストアンサー
- C・C++・C#
- クイックソートの可視化プログラムを考えています
いつもお世話になっております。 当方、理系の学部に在籍中の学生です。 OpenGLを用いてクイックソートを可視化するためのプログラムを考えております。 まず、ソーティングしたい整数配列の要素ひとつひとつを単色の四角形で表現し、数が大きいほど明るく、小さいほど暗くなるよう設定しました。 イメージとしては、Rキーを押す度にソーティングがワンステップずつ進み、徐々に綺麗なグラデーションが出来上がっていく様子を表示させたいのですが、ここが上手くいかず困っております。問題点をご指摘いただけるとありがたいです。 以下、ソースコードの一部となります。 /* ソートする配列 */ int nums[] = {94, 43, 59, 57, 23, 27, 25, 22, 55, 21, 44, 28, 65, 30, 75, 13, 23, 89, 84, 71, 45, 68, 28, 31, 75, 62, 70, 34, 87, 20, 96, 47, 80, 74, 81, 30, 22, 55, 11, 34, 85, 16, 71, 41, 28, 26, 25, 47, 14, 55}; int n = 50; int flag = 0; /* 表示コールバック関数の一部 */ void display(void) { glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glLineWidth(5.0); for(int i = 0; i < n; i++) { glColor3f(0.0, 0.0, nums[i] * 0.01); glBegin(GL_POLYGON); glVertex2f(0.0, 0.0 + 0.5 * i); glVertex2f(2.0, 0.0 + 0.5 * i); glVertex2f(2.0, 0.5 + 0.5 * i); glVertex2f(0.0, 0.5 + 0.5 * i); glEnd(); } /* キーボードコールバック関数の一部 */ case 'r': flag = 1; break; case 'q': /* クイックソートする */ QSort(nums, 0, n - 1); break; /* クイックソートを行う */ void QSort(int x[], int left, int right) { int i, j; int pivot; i = left; /* ソートする配列の一番小さい要素の添字 */ j = right; /* ソートする配列の一番大きい要素の添字 */ pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */ while (1) { /* 無限ループ */ while (x[i] < pivot) /* pivot より大きい値が */ i++; /* 出るまで i を増加させる */ while (pivot < x[j]) /* pivot より小さい値が */ j--; /* 出るまで j を減少させる */ if (i >= j) /* i >= j なら */ break; /* 無限ループから抜ける */ Swap(x, i, j); /* x[i] と x[j]を交換 */ while (flag == 0) glutPostRedisplay(); i++; /* 次のデータ */ j--; flag = 0; /* flag更新 */ } if (left < i - 1) /* 基準値の左に 2 以上要素があれば */ QSort(x, left, i - 1); /* 左の配列を Q ソートする */ if (j + 1 < right) /* 基準値の右に 2 以上要素があれば */ QSort(x, j + 1, right); /* 右の配列を Q ソートする */ } /* 配列の要素を交換する */ void Swap(int x[ ], int i, int j) { int temp; temp = x[i]; x[i] = x[j]; x[j] = temp; }
- ベストアンサー
- C・C++・C#
- C言語 クイックソートについて
クイックソートでわからない点があるため、 質問させていただきます。 ----------------------------------------------------- ～省略～ data = [5, 3, 4, 2, 6, 1]; no = 6; //データの個数 ～省略～ dqsort(data, 0, no-1); ～省略～ void dqsort(double data[], int lower, int upper) { int i, boundary; //boundaryは配列の前半と後半の境界を示す if(lower >= upper) { return; } //基準値となる値（データの中央に位置する値）とデータの先頭の値を入れ替える swapdata(&data[lower], &data[(lower + upper)/2]); boundary = lower; //boundaryを先頭に移動させる for(i=lower+1; i<=upper; i++) { if(data[i] < data[lower]) { //配列の前半部分に移動し、境界を移動する swapdata(&data[++boundary], &data[i]); } } //最後に基準値を境界位置にコピー swapdata(&data[lower], &data[boundary]); //配列の前半部分をクイックソート dqsort(data, lower, boundary-1); //配列の後半部分をクイックソート dqsort(data, boundary+1, upper); } void swapdata(double *i, double *j) { int temp; temp = *i; *i = *j; *j = temp; } --------------------------------------------------------- 基準値と配列の先頭のデータを入れ替えた後、 データは、[4, 3, 5, 2, 6, 1]となり、lower = 0であるため、 data[boundary]はdata[0]となります。 for文の最初のループでdata[0]<data[1]なら、 swapdata(&data[++boundary], &data[i]); となっているのですが、 [++boundary]の部分はboundary=0に1を足してから処理するため、 swapdata(&data[1], &data[1]); となると思うのですが、そうすると同じデータを入れ替えることになってしまいます。 何が間違っているのか、教えていただけますでしょうか。
- ベストアンサー
- C・C++・C#
- クイックソート
今クイックソートのプログラム作成をしていますが、分からない箇所が幾つかあります。下は、作成した時のプログラムリストです。 class QuickSort{ static int compare = 0; static int copy = 0; static int swap = 0; static void swap(int a[], int i, int j){ int tmp; tmp = a[i];copy++; a[i] = a[j];copy++; a[j] = tmp;copy++; swap++;} static void showArray(int a[], int l, int r){//配列の内容を表示するメソッドで、動作:部分配列a[l]～a[r]の要素を表示。これが分かりません。 int a[l] = {1,2,3,4,5,6,7,8,9,10}; int a[r] = {11,12,13,14,15,16,17,18,19,20};} static void initArray(int a[], int N){ int i; a[0]=0; for(i=1;i<N;i++) a[i] = i; for(i=1;i<N;i++){ int j,k; j = (int)(java.lang.Math.random()*(N-1)) + 1; k = (int)(java.lang.Math.random()*(N-1)) + 1; swap(a,j,k);}} public static void (int a[],int l, int r) { if (r+1-l <= 1) return; int e = (l+r+1)/2; int c = 0; return a[c]; } static int partition(int a[], int l, int r, int pivot){// 配列の分割を行うメソッドです。そのあと分割に要した比較回数(=iの増加分+jの減少分)を変数compareに加算し、iの値を戻り値として返さないといけませんが、そこんとこが分かりません。 while (true) { while (a[l] < pivot) l = l + 1; while (a[r] >= pivot) r = r - 1; if (l > r) return l; swap(a, l, r); } } static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } int i=0; int j=0; return i; } static void quicksort(int[] a, int l, int r){//(カットオフなしで)再帰的にクイックソートを行うメソッドです。paritionメソッドを用い、a[l]～a[r]を分割値a[r]で分割するのが条件ですが、ここも全然分かりません。 if(l < r){ int i = l; int j = r; int x = a[(i+j)/2]; do{ while(a[i]<x) i++; while(a[j]>x) j--; if(i<=j) { swap(a,i,j); i++; j--; } }while(i<=j); quickort(a,l,j); quicksort(a,i,r); } } static void swap(int[] a, int s, int t){ int temp = a[s]; a[s] = a[t]; a[t] = temp; return; int i,pivot; } public static void main(String args[]){ //上で作ったメソッドを用いて、ソート過程を表示しながらクイックソートを実行 //手順は次のようになる。 1.要素を(20個もつ)整数型配列aを宣言 2.整数型変数Nに配列aの要素数を保存 3.initArrayメソッドを用いて配列aを初期化 4.showArrayメソッドを用いてソート前の配列aの内容を表示 5.変数compare,copyの値を0に初期化 6.quickSortメソッドを用いて配列aを選択ソート 7.showArrayメソッドを用いてソート後の配列aの内容を表示 8.ソートにかかった比較・コピーの回数を表示 //これも分かりません。 } 分かる人がいましたら教えて下さい。お願いします。
- 締切済み
- Java
- バブルソート、あなたはどちら派？
昇順にソートする場合ですが、 配列の先頭とその次の値を比較し、大きい数字の方を後ろへ持っていくパターンと 配列の最後とその手前を比較し、小さい数字を前へ持っていくパターンがあると思います。 前者のほうが、湖底から水面へ泡がだんだん大きくなっていくバブルのイメージで 長年これがスタンダードだと思っていたのですが、 後者についてを「小さい泡がだんだん移動していくイメージなのでバブルソートと言う」と 断言しているサイトや書籍もあります。 どちらも間違いではないと思います。 ですが、他人に教えることを想像したとき、 どちらかというと先に前者を教えてから、後者のやり方もあるよと伝えた方が 直感的に理解しやすいかなと思いました。 皆さんはどちら派ですか？ また、前者と後者を使い分けるメリットがもしもあればご教示頂けませんか？
- 締切済み
- その他（プログラミング・開発）
- クイックソートの比較交換回数について
クイックソートの比較交換回数を変数countで計算し、表示させようとしているのですがうまくいきません。 改善策を教えていただけないでしょうか。 /* クイックソート */ void quickSort(randomlist_t data[],int n){ /* 実質的な処理は何もせず、クイックソートを実際に行う関数を呼び出すのみ */ int count = 0; quickSort_1(data,0,n-1,count); printf("count:%d\n",count); } /* 実際にクイックソートを行う関数 */ void quickSort_1(randomlist_t data[],int l,int r,int count){ int v; if(l >= r) /* 整列する要素が1つなら、何もしないでリターンする */ return; v = partition(data,l,r,count); /* 枢軸vを基準に分割する */ quickSort_1(data,l,v-1,count); /* 左の部分の配列a[l]～a[v-1]を整列する */ quickSort_1(data,v+1,r,count); /* 右の部分の配列a[v+1]～a[r]を整列する */ } /* 配列a[l]～a[r]を分割する。枢軸の添え字を返す */ int partition(randomlist_t data[],int l,int r,int count){ int i,j,pivot; randomlist_t t; i = l - 1; j = r; /* ポインタiとjを初期化する */ pivot = data[r].no; /* 一番右端の要素を枢軸にする */ for(;;){ /* ポインタiとjとがぶつかるまで繰り返す */ while(data[++i].no < pivot) count++; /* ポインタiを右へ進める */ while(i < --j && pivot < data[j].no) count++; /* ポインタjを左へ進める */ if(i >= j) break; /* ポインタiとjがぶつかったらループを抜ける */ t = data[i]; data[i] = data[j], data[j] = t; /* iの指す要素とjの指す要素を交換する */ count++; } t = data[i]; data[i] = data[r]; data[r] = t; /* a[i]と枢軸を交換する */ count++; return i; }
- ベストアンサー
- C・C++・C#
お礼
シ、シマッタ！ と、とんどもない考え違いをしていたようです。 正に、回答の通りです。 面目ない次第です。 ともかく、もう一度よーく考えてみます。
補足
補足でお礼を！ やっと理解できました。 要は、基準値の右に大きいのを集めて左に小さいのを集める。 そのために基準値を移動させている。 隣同志になるまで。 そういうことでした。