2次元配列のクイックソートで無限ループになってしまいます。

Question

こちらのページを参考にして2次元配列のクイックソートをやろうとしたのですが、無限ループ？スタックオーバーフロー？となりうまく動作してくれませんでした。
https://dixq.net/forum/viewtopic.php?t=19289

サンプルコードをそのまま使えば動作したのですが、次元数（？）・配列の形を変更したらこのような状態になってしまいました。
2021.04.02 18:55:17.179 Stack overflow in 'C:\Users\AppData\Roaming\MetaQuotes\Terminal\MQL4\Scripts\2Dim_Quick_Sort.ex4'

自分が何か余計なことをしてしまっているみたいなのです。いろいろ試してみたのですが見当がつきませんでした。原因をご教授いただけないでしょうか？
よろしくお願いいたします。

#define MAX  4
#define MAXb 3



int a[MAX][MAXb] = {  // 
    18, 19, 14,
    24, 16, 11,
    17, 22, 20,
    15, 12, 26,
};


//int main(void)
{
    
    quick(a, 0, 0, MAX - 1, MAXb - 1);
    print(a);
}


}

void print(int &a[][])
{
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAXb; j++) printf(" %3d", a[i][j]);
        
    
}

void quick(int &data[][MAXb], int first_x, int first_y, int last_x, int last_y)
{
    int i = first_x, j = first_y, k = last_x, l = last_y;
    int temp = ((i * MAX + j) + (k * MAX + l)) / 2;
    int x = data[temp / MAX][temp % MAXb];     

    Print("Pivot : "+temp);

    for (;;) 
    {
        while (data[i][j] < x)
            if (++j > MAXb - 1){ j = 0; i++; }  
        while (data[k][l] > x)
            if (--l < 0) {l = MAXb - 1; k--; }  
            
        if (i * MAX + j >= k * MAX + l) break;
        
        temp = data[i][j]; data[i][j] = data[k][l]; data[k][l] = temp;
        
        if (++j > MAXb - 1) {j = 0; i++; }      
        if (--l < 0) {l = MAXb - 1; k--; }      
    }
    
    
    
    
    if (--j < 0) {j = MAXb - 1; i--; }          
    if (first_x * MAX + first_y < i * MAX + j)
        quick(data, first_x, first_y, i, j);

        
    if (++l > MAXb - 1) {l = 0; k++;   }        
    if (k * MAX + l < last_x * MAX + last_y)
        quick(data, k, l, last_x, last_y);
}

コード

Comments

[kazuma-s]

コンパイルできないソースでどうやって stack overflow の実行時エラーになるんですか？

Answer 1

サンプルコードから次元を変えたということでそこについていえば、縦4、横3の二次元配列に1次元と同様の順序付けをすると

0, 1, 2
3, 4, 5
6, 7, 8
9,10,11

となります。つまりdata[i][j]は i * 3 + j番目の数じゃないといけません。同様にi番目の数はdata[i / 3][i % 3]を示します。

そこを間違えた結果pivotがまれにfirstとlastの間から出てしまうことがある(例えば(0, 2), (1, 0)の場合(0, 0)がpivotになる)ので、無限ループの原因はそれかもしれません。

Comments

[siusus]

ありきたりなトピックだったので回答もらえないんじゃないかと不安に思ってました。回答もらえて本当にうれしいです！

まさにご指摘いただいた部分が原因となっていました。私が2次元配列から1次元配列に戻す手順をきちんと理解していなかったようです。

再帰から抜ける条件部分を一生懸命調べていました。おそらく自力では気づけなかったと思います。
本当に助かりましたー！ありがとうございます。

Answer 2

指摘していただいた部分を修正したものです。
どなたか私と似た状況の人の助けになったら幸いです。

#define MAX  4
#define MAXb 3


int a[MAX][MAXb] = {  // 列数が大事 : [i][j] = [Row * i +j] 
    18, 19, 14,
    24, 16, 11,
    17, 22, 20,
    15, 12, 26,
};


//int main(void)
{
    
    quick(a, 0, 0, MAX - 1, MAXb - 1);
    print(a);
}


}

void print(int &a[][])
{
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAXb; j++) printf(" %3d", a[i][j]);
        
    
}

void quick(int &data[][MAXb], int first_x, int first_y, int last_x, int last_y)
{
    int i = first_x, j = first_y, k = last_x, l = last_y;
    int temp = ((i * MAXb + j) + (k * MAXb + l)) / 2;
    int x = data[temp / MAXb][temp % MAXb];    // 

    //Print("Pivot : "+temp);
    //Print("PivEle : ["+temp/MAXb+"] "+"["+temp%MAXb+"]");

    for (;;) 
    {
        while (data[i][j] < x)
            if (++j > MAXb - 1){ j = 0; i++; }  //  --- (1)
        while (data[k][l] > x)
            if (--l < 0) {l = MAXb - 1; k--; }  //  --- (2)
            
        if (i * MAXb + j >= k * MAXb + l)
        {
         //Print(" i : j "+i+" : "+j);
         //Print(" l : k "+l+" : "+k);
        
         break;  
        }
        
        temp = data[i][j]; data[i][j] = data[k][l]; data[k][l] = temp;
        
        if (++j > MAXb - 1) {j = 0; i++; }      //  --- (3)
        if (--l < 0) {l = MAXb - 1; k--; }      //  --- (4)
    }
    
    
    
    
    if (--j < 0) {j = MAXb - 1; i--; }            //分割境界を左にずらす 列数jが0を超えたら行i繰り下がり
    if (first_x * MAXb + first_y < i * MAXb + j) //新しい境界がleftからはみ出ていないなら
        quick(data, first_x, first_y, i, j);     //新しい境界で再度ソート

        
    if (++l > MAXb - 1) {l = 0; k++;}         //分割境界を右にずらす 列数LがMAXbを超えたら行k繰り上がり
    if (k * MAXb + l < last_x * MAXb + last_y)
        quick(data, k, l, last_x, last_y);
}
コード