1

Pythonクイックソートの実装をC++に変換しようとして、いくつかのコードを記述しました。コードが壊れているようです。私は開発にXcodeを使用していますが、コードをコンパイルして実行する(lldb)と、プログラムが無限ループに陥っているように見えます。

バグを見つけて、C++実装のどこが間違っているのかを指摘するのを手伝ってください。

Pythonクイックソートコード：

from random import randint

def quickSort(lst):
    if not lst:
        return []
    else:
        pivot_index = randint(0, len(lst) - 1)
        pivot = lst[pivot_index]
        lesser = quickSort([l for i, l in enumerate(lst)
                            if l <= pivot and i != pivot_index])
        greater = quickSort([l for l in lst if l > pivot])
        #print lesser, pivot, greater
        return lesser + [pivot] + greater

print quickSort([3, 2, 5, 6, 1, 7, 2, 4, 234, 234, 23, 1234, 24, 132])

C ++クイックソートコード：

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// simple print function 
void print(int* lesser, int len_lesser, int pivot, int* greater, int len_greater) {
    for (int i=0; i < len_lesser-1; i++) {
        cout << lesser[i] << " ";
    }
    cout << pivot << " ";
    for (int i=0; i < len_greater-1; i++) {
        cout << greater[i] << " ";
    }
    cout << endl;
}

unsigned long long rdtsc(){
    unsigned int lo,hi;
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return ((unsigned long long)hi << 32) | lo;
}

int randint(int len) {
    // srand(time(0));
    srand((unsigned)rdtsc());
    return (rand() % (len) + 0);
}
void quickSort(int* lst, int len) {
    if (lst == NULL) {
        cout << "List Empty" << endl;
        return;
    }
    else {
        int lesser[] = {};
        int greater[] ={};
        int j = 0;
        int k = 0;
        int pivot_index = randint(len);
        int pivot = lst[pivot_index];
        //cout << pivot << endl;
        for (int i=0; i < len-1; i++) {
            if (lst[i] <= pivot && i != pivot_index) {
                lesser[j] = lst[i];
                j = j+1;
            }
        }
        int len_lesser = sizeof(lesser)/sizeof(int);
        quickSort(lesser, len_lesser);

        for (int i=0; i < len-1; i++) {
            if (lst[i] > pivot) {
                greater[j] = lst[i];
                k = k+1;
            }
        }
        int len_greater = sizeof(greater)/sizeof(int);
        quickSort(greater, len_greater);
        print(lesser, len_lesser, pivot, greater, len_greater);
    }

}


int main() {
    int lst[] = {3, 2, 5, 6, 1, 7, 2, 4, 234, 234, 23, 1234, 24, 132};
    int len = sizeof(lst)/sizeof(int);
    quickSort(lst, len);
    return 0;
}
4

2 に答える 2

4

C++宣言する配列は動的ではありません。データを動的に使用std::vectorまたは割り当てる必要があります。それ以外の場合、これらの呼び出し (関数 quickSort 内):

lesser[j] = lst[i];

範囲外のインデックスにアクセスしています。

于 2013-03-21T14:43:20.870 に答える
2

lesser宣言していない、またはgreaterサイズを持たない、少なくとも1つの大きな問題があります。

int lesser[]  = {};
int greater[]  ={};

したがって、後でそれらにアクセスしようとすると、範囲外になります。

lesser[j] = lst[i];

その後、サイズを取得すると、次のようになります0。

int len_lesser = sizeof(lesser)/sizeof(int);

クリーンな解決策は、std :: vectorを使用することです。そうすれば、割り当てやサイズについて心配する必要はありません。警告を有効にして、常に警告を使用してコンパイルする必要があります。でgcc実行する-Wall -W -pedanticと、コンパイルできず、次のように表示されます。

 36:26: error: zero-size array 'lesser'
 37:26: error: zero-size array 'greater'

何が悪いのかすぐにわかります。

于 2013-03-21T14:46:55.367 に答える