1

私が取り組んでいるハフマンコーディングプロジェクトのクイックソートアルゴリズムに取り組んでいます（すべての関数名がハフで始まる理由を説明しています）。デバッガーを使用してウォークスルーすると、最高の項を見つけるときに関数がフリーズするように見えます（ベクトルの右側から、その側に「あるべきではない」項を見つけようとすると）。このコードには他にも問題がある可能性がありますが、今はこれに焦点を当てています。ちなみに、ほとんどの場合（常に）私はcoutと呼んでいますが、これはデバッグを目的としています。

編集：コメントから私のコードに多くの修正が加えられましたが、どれも私の問題を修正していません。そのため、コードを更新しています。

void huff_sort_partition(vector<Node*>* v, int b, int e){
    int tempt = b+((rand()%(e-b))+1);
    int p_idx = (*v)[tempt]->weight;
    cout << tempt << endl;
    int l = b+0;
    int r = e;
    cout << "P:" << p_idx << "  L-R:" << l << "-" << r << endl;
    while(l < r){
        while((*v)[l]->weight < p_idx){
            l++;
        }
        while((*v)[r]->weight > p_idx){
            r--;
        }
        Node* s = (*v)[b+l];
        (*v)[b+l] = (*v)[b+r];
        (*v)[b+r] = s;
    }

    huff_sort_partition(v, b, l-1);
    huff_sort_partition(v, l+1, e);
}
void Huff::huff_sort(vector<Node*>* v){
    srand ( time(NULL) );
    cout << "------sort------" << endl;
    huff_sort_partition(v, 0, v->size());
}

編集：まだ誰もこれに答えていないので、私はこれを追加すると思いました。コードが「機能するはず」の場合は、コメントします（そうすれば、このコード以外の理由で機能しない理由を探すことができます）。

4

2 に答える 2

1

b,l使用と停止の状態 に問題があります。bは、patitionを開始する場所からeのインデックスであり、停止する場所のインデックスです。したがって、初めて関数を呼び出すときは、eサイズではなく最後のインデックスを参照する必要があります。また、停止条件が欠落していますhuff_sort_partition-永久に実行されないようにするにはb、eインデックスが各0therに対して問題がないかどうかを確認する必要があります。

以下のコードの修正バージョンをお試しください 

void huff_sort_partition(vector<Node*>* v, int b, int e){ 
        if (b >= e ) {
            return;
        }
        int p = (*v)[b+(rand() % (e - b + 1))]->weight; 
        int l = 0; 
        int r = e-b; 
        cout << "P:" << p << "  L-R:" << l << "-" << r << endl; 
        while(l < r){ 
            while((*v)[b+l]->weight < p){ 
                l++; 
            } 
            while((*v)[b+r]->weight > p){ 
                r--; 
            } 
            Node* s = (*v)[b+l]; 
            (*v)[b+l] = (*v)[b+r]; 
            (*v)[b+r] = s; 
        } 

        huff_sort_partition(v, b, b+l-1); 
        huff_sort_partition(v, b+r+1, e); 
        cout << "P:" << p << "  L-R:" << l << "-" << r << endl; 
        for_each(v->begin(), v->end(), show_freq); 
    } 
    void Huff::huff_sort(vector<Node*>* v){ 
        srand ( time(NULL) ); 
        cout << "------sort------" << endl; 
        huff_sort_partition(v, 0, v->size() - 1); 
    }
于 2012-07-20T20:27:17.817 に答える
1

ピボットウェイトを持つノードが複数ある場合にコードで何が起こるかを検討します。簡単にするために、ウェイト[1, 9, 5, 2, 7, 5, 6, 8, 3, 7]とパーチャンスを考慮し、ピボットインデックスは5です。

void huff_sort_partition(vector<Node*>* v, int b, int e){
    int p = (*v)[b+(rand() % (e - b + 1))]->weight;

我々は持っていますp = 5

    int l = 0;
    int r = e-b;

l = 0とr = 9

    cout << "P:" << p << "  L-R:" << l << "-" << r << endl;
    while(l < r){
        while((*v)[b+l]->weight < p){
            l++;
        }

1 < 5、次に増分l、、。l = 1v[1] = 9 > 5

        while((*v)[b+r]->weight > p){ // where it freezes up and wont move on
            r--;
        }

7 > 5、デクリメントr、、。交換して、与える。r = 8v[8] = 3 < 5v[1]v[8][1, 3, 5, 2, 7, 5, 6, 8, 9, 7]

次のラウンド、l = 1 < 8 = r。v[1] = 3 < 5、l2になりv[2] = 5、5以上で、ループの終わりです。これで、2番目の内部ループに入りますv[8] = 9 > 5、、、; は5以下で、スワップと、を与えます。v[7] = 8 > 5v[6] = 6 > 5v[5] = 5v[2]v[5][1, 3, 5, 2, 7, 5, 6, 8, 9, 7]

次のラウンドl = 2 < 5 = r、、v[2] = 5は5より小さくなく、5v[5] = 5より大きくない、スワップv[2]およびv[5]。おっと、私たちは立ち往生しています。

これを防ぐ通常の方法は、ピボットを邪魔にならないように交換し、2つの条件のいずれかを弱い不等式にすることです。l < rまた、内側のループでも条件を確認する必要があります。そうでない場合、すべてのエントリが等しい場合は実行されます。配列/ベクトルの終わり。次に、分割した後、ピボットを適切な場所に交換します。

次のコードは、標準的な方法を使用しています（テストされていない、タイプミスの可能性があります）。

void huff_sort_partition(vector<Node*>* v, int b, int e){
    // Nothing to sort if there are fewer than two elements
    if (e <= b) return;
    int tempt = b+((rand()%(e-b))+1);
    int p_idx = (*v)[tempt]->weight;
    // swap pivot out of the way
    Node *tmp_Node = (*v)[tempt];
    (*v)[tempt] = (*v)[e];
    (*v)[e] = tmp_Node;
    cout << tempt << endl;
    int l = b;
    int r = e - 1;
    cout << "P:" << p_idx << "  L-R:" << l << "-" << r << endl;
    while(l < r){
        while((l < r) && (*v)[l]->weight < p_idx){
            l++;
        }
        while((l < r) && (*v)[r]->weight >= p_idx){
            r--;
        }
        if (l < r){
            Node* s = (*v)[l];
            (*v)[l] = (*v)[r];
            (*v)[r] = s;
            // stuff at l and r is okay now, we don't need to test again
            ++l;
            --r;
        }
    }
    // Now l is the first index with weight >= pivot weight,
    // swap pivot into place
    tmp_Node = (*v)[l];
    (*v)[l] = (*v)[e];
    (*v)[e] = tmp_Node;

    huff_sort_partition(v, b, l-1);
    huff_sort_partition(v, l+1, e);
}
于 2012-07-20T20:34:57.453 に答える