0

このコードは、小さい の場合はうまく機能num_itemsしますが、 の場合はスタックがオーバーフローしますnum_items = 1000。

1000 はかなり小さい数だと思うので、これをもっと大きな数まで機能させる方法があるはずです。より多くの再帰呼び出しに耐えられるようにするにはどうすればよいですか?

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>

void printv(std::vector<int>& v) {
    for (int i=0; i<v.size(); i++) std::cout << v[i] << " ";
    std::cout << std::endl;
}

void quicksort(std::vector<int>& v, int begin, int end) {

    if (((end - begin) <= 1) ||
        (begin < 0) ||
        (end > (v.size() - 1))) return;

    int pivot = v[std::rand() % v.size()];

    int x = 0;
    int y = v.size() -1;

    while(x < y) {
        int changed = 0;
        if(v[x] <= pivot) {
            x++;
            changed = 1;
        }
        if (v[y] > pivot) {
            y--;
            changed = 1;
        }
        if (!changed){
            std::swap(v[x], v[y]);
            x++;
            y--;
        }
    }

    if (x == y) y++;
    if (x > y) std::swap(x, y);

    quicksort(v, begin, x);
    quicksort(v, y, end);
}

int ran() {
    return std::rand() % 100;
}

int main() {
    std::srand(std::time(0));
    int num_items = 1000;
    std::vector<int> v (num_items);
    std::generate_n(v.begin(), num_items, ran);

    printv(v);
    quicksort(v, 0, v.size()-1);
    printv(v);
}

コードに関する一般的なコメントも歓迎します。

で立ち往生[0,4]：

#1  0x0000000000400b4c in quicksort (
    v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
    at quicksort.cpp:14
#2  0x0000000000400cc1 in quicksort (
    v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
    at quicksort.cpp:43
#3  0x0000000000400cc1 in quicksort (
    v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
    at quicksort.cpp:43
#4  0x0000000000400cc1 in quicksort (
    v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
    at quicksort.cpp:43
#5  0x0000000000400cc1 in quicksort (
    v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
    at quicksort.cpp:43
#6  0x0000000000400cc1 in quicksort (
    v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
    at quicksort.cpp:43
#7  0x0000000000400cc1 in quicksort (
    v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
    at quicksort.cpp:43
4

1 に答える 1

3 
int pivot = v[std::rand() % v.size()];

int x = 0;
int y = v.size() -1;

明示的に渡しbeginてend配置しますが、完全なリストからピボット要素を選択します。それは正しく聞こえません。との間のピボット要素を選択する必要がありbeginますend。また、xで開始する必要がbeginあり、 で開始する必要がありyますend。そうしないと、各再帰ステップで常に完全なリストを処理しているため、発生している無限再帰が説明されます。

于 2012-10-07T15:05:24.760 に答える