0

私は QuickSort アルゴリズムを理解しようとしていました。しかし、配列を Partition と QuickSort 関数に渡すことができないようです。配列の最初の要素のみを処理します。

どうすれば修正できますか？

template < class T > int getArrayLen(T & array) {
    return (sizeof(array) / sizeof(array[0]));
}

int Partition(int a[], int first, int last) {
    int pivot = a[last];
    int i = first - 1;
    for (int j = first; j < last; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[last]);
    return i + 1;
}

void QuickSort(int a[], int first, int last) {
    int pivot;

    if (first < last) {
        pivot = Partition(a, first, last);
        QuickSort(a, first, pivot);
        QuickSort(a, pivot + 1, last);
    }
 }

 int main() {
    int a[] = {
         4, 32, 3, 13, 48, 45, 12, 54, 7, 42, 3, 12, 5, 24, 20
    };
    int length = getArrayLen(a);
    QuickSort(a, 0, length - 1);
}
4

1 に答える 1

1

Just decrease one from pivot before calling QuickSort again:

void QuickSort(int a[], int first, int last)
{
    int pivot;

    if (first < last)
    {
        pivot = Partition(a, first, last);
        QuickSort(a, first, pivot - 1);  // <--  HERE
        QuickSort(a, pivot + 1, last);
    }
}

And every thing is OK. Also test for various sizes of a: 1, 2, 3, 4, 5, ...

于 2013-03-12T08:09:52.270 に答える