基本情報技術者過去問題 平成27年春期 午後問8のプログラムをC++に書き換えようとしたが無限ループする

Question

https://www.fe-siken.com/kakomon/27_haru/pm08.html

に載っている疑似プログラムをC++で書き換えてみています。

swap操作はstd::swapを使うようにしたことと、C++では配列が0始まりなのでそうしつつデバッグプリントでは1始まりのときのように出力していることを除けば、忠実に書き換えたつもりですが、どういうわけか無限ループに陥ります。

なにが間違っているのでしょうか・・・？

#include <vector>
#include <utility>
#include <iostream>
using std::size_t;
void print(const std::vector<int>& v)
{
    std::cout << "[";
    bool b = false;
    for(auto&& i : v){
        if (std::exchange(b, true)){
            std::cout << ',';
        }
        std::cout << i;
    }
    std::cout << "]" << std::endl;
}
int select(std::vector<int> x, size_t k)
{
    using std::cout;
    using std::endl;
    size_t top = 0, last = x.size() -1, l = 0;
    cout << "top:" << top + 1 << ",last:" << last + 1  << endl;
    print(x);
    while(top < last){
        cout << l++ << "---------" << endl;
        int pivot = x.at(k - 1);
        size_t i = top;
        size_t j = last;
        cout << "i:" << i + 1 << ",j:" << j + 1 << ",pivot:" << pivot << endl;
        while(true){
            while (x.at(i) < pivot) {
                ++i;
                cout << "i:" << i + 1 << endl;
            }
            while (pivot < x.at(j)) {
                --j;
                cout << "j:" << j + 1 << endl;
            }
            if (j <= i) break;
            cout << "swap:: i:" << i + 1 << ",j:"<< j + 1 << ",x[i]:" << x.at(i) << ",x[j]:" <<  x.at(j) << endl;
            std::swap(x.at(i), x.at(j));
            ++i;
            --j;
            print(x);
        }
        if (i <= k){
            top = j + 1;
            cout << "top:" << top + 1 << endl;
        }
        if (k <= j) {
            last = i - 1;
            cout << "last:" << last + 1  << endl;
        }
        cout << "top:" << top + 1 << ",last:" << last + 1  << endl;
    }
    print(x);
    return x.at(k - 1);
}
int main()
{
    std::cout << select({3, 5, 6, 4, 7, 2, 1}, 3) << std::endl;
}

https://wandbox.org/permlink/ejFa0MDmInfitZos

出力

top:1,last:7
[3,5,6,4,7,2,1]
0---------
i:1,j:7,pivot:6
i:2
i:3
swap:: i:3,j:7,x[i]:6,x[j]:1
[3,5,1,4,7,2,6]
i:5
swap:: i:5,j:6,x[i]:7,x[j]:2
[3,5,1,4,2,7,6]
last:5
top:1,last:5
1---------
i:1,j:5,pivot:1
j:4
j:3
swap:: i:1,j:3,x[i]:3,x[j]:1
[1,5,3,4,2,7,6]
j:1
top:2
top:2,last:5
2---------
i:2,j:5,pivot:3
swap:: i:2,j:5,x[i]:5,x[j]:2
[1,2,3,4,5,7,6]
j:3
top:4
top:4,last:5
3---------
i:4,j:5,pivot:3
j:4
j:3
top:4
top:4,last:5

(以下3---------以下のが無限に表示される)

Answer 1

    if (i <= k){
    if (k <= j) {

このiおよびjはオリジナルよりも1小さくなります。
対して、kはオリジナルと同じ数値です。

Comments

[yumetodo]

ああ、見落としていました。ありがとうございます。