1

先生は、使用して実行時間をテストするための簡単な並べ替え機能を教えてくれましたが、10,000 個の要素リストに達すると、スタック オーバーフローがスローされ、その理由がわかりません。いくつかの異なるコンピューターでテストしましたが、解析された 10,000 要素のうち約 9375 で同じ結果が得られました。

クイックソートファイル

#include "swap.h"

/** Chooses a pivot for quicksort's partition algorithm and swaps
 *  it with the first item in an array.
 * @pre theArray[first..last] is an array; first <= last.
 * @post theArray[first] is the pivot.
 * @param theArray  The given array.
 * @param first  The first element to consider in theArray.
 * @param last  The last element to consider in theArray. */
void choosePivot(int theArray[], int first, int last){
    //cerr << "choosePivot(array, " << first << ", " << last << ")\n";
    int mid = (last - first) / 2;
    if( (theArray[first] <= theArray[mid] &&
         theArray[mid] <= theArray[last]) ||
        (theArray[last] <= theArray[mid] &&
         theArray[mid] <= theArray[first]) ){
        // value at mid index is middle of values at first and last indices 
        swap(theArray[first], theArray[mid]);
    }else if( (theArray[first] <= theArray[last] &&
               theArray[last] <= theArray[mid]) ||
              (theArray[mid] <= theArray[last] &&
               theArray[last] <= theArray[first])){
        // value at last index is middle of values
        swap(theArray[first], theArray[last]);
    }
}


/** Partitions an array for quicksort.
 * @pre theArray[first..last] is an array; first <= last.
 * @post Partitions theArray[first..last] such that:
 *    S1 = theArray[first..pivotIndex-1] <  pivot
 *         theArray[pivotIndex]          == pivot
 *    S2 = theArray[pivotIndex+1..last]  >= pivot
 * @param theArray  The given array.
 * @param first  The first element to consider in theArray.
 * @param last  The last element to consider in theArray.
 * @param pivotIndex  The index of the pivot after partitioning. */
void partition(int theArray[],
               int first, int last, int& pivotIndex){
   // place pivot in theArray[first]
   choosePivot(theArray, first, last);
   int pivot = theArray[first];     // copy pivot

   // initially, everything but pivot is in unknown
   int lastS1 = first;           // index of last item in S1
   int firstUnknown = first + 1; // index of first item in
                                 // unknown

   // move one item at a time until unknown region is empty
   for (; firstUnknown <= last; ++firstUnknown)
   {  // Invariant: theArray[first+1..lastS1] < pivot
      //         theArray[lastS1+1..firstUnknown-1] >= pivot

      // move item from unknown to proper region
      if (theArray[firstUnknown] < pivot)
      {  // item from unknown belongs in S1
         ++lastS1;
         swap(theArray[firstUnknown], theArray[lastS1]);
      }  // end if

      // else item from unknown belongs in S2
   }  // end for

   // place pivot in proper position and mark its location
   swap(theArray[first], theArray[lastS1]);
   pivotIndex = lastS1;
}  // end partition

/** sorts the items in an array into ascending order.
 * @pre theArray[first..last] is an array.
 * @post theArray[first..last] is sorted.
 * @param theArray  The given array.
 * @param first  The first element to consider in theArray.
 * @param last  The last element to consider in theArray. */
void quicksort(int theArray[], int first, int last){
    int pivotIndex;

   if (first < last)
   {  // create the partition: S1, pivot, S2
      partition(theArray, first, last, pivotIndex);

      // sort regions S1 and S2
      quicksort(theArray, first, pivotIndex-1);
      quicksort(theArray, pivotIndex+1, last);
   }  // end if
}  // end quicksort

swap.h ファイル

#ifndef _SWAP_H
#define _SWAP_H

/** Swaps two items.
 * @pre x and y are the items to be swapped.
 * @post Contents of actual locations that x and y represent are
 *       swapped.
 * @param x  Given data item.
 * @param y  Given data item. */
void swap(int& x, int& y){
   int temp = x;
   x = y;
   y = temp;
}  // end swap

#endif /* _SWAP_H */

そして実装ファイル

//main.cpp
//Angelo Todaro
//Main driverto clock the timing efficiency of different sort algorithms for different sized lists

#include "quickSort.cpp"
#include <iostream>
#include <time.h>
using namespace std;

double diffclock(clock_t,clock_t);

int main(){
    clock_t begin, end;//clocks to store number of ticks at beginning and end
    srand(time(NULL));//initialize seed
    cout << "# of Elements\tQuick\n";
    for(int n = 10; n < 100000; n*=10){
        int* array = new int[n];
        cout << n << "\t\t";
        for(int i =0; i < n; i++){
            array[i]=rand()%1000;
        }


        //quick sort
        begin=clock();
        quicksort(array,0,n);
        end=clock();
        cout << diffclock(end,begin) << "\t";

    }

    return 0;
}


double diffclock(clock_t clock1, clock_t clock2){
    double diffticks = clock1-clock2;//finds difference between ticks
    double diffmili=diffticks/CLOCKS_PER_SEC;//turns tickes into miliseconds
    return diffmili;
}
4

2 に答える 2

3

これは、あまり良いピボットを選択しない再帰的なクイックソートの実装です。いくつかの入力が与えられると、すべての要素に対して関数呼び出しが行われる場合があります。スタック上の 10,000 の呼び出しを処理するのは非常に困難です。この時点では、ランダム ピボットを使用した反復インプレース クイックソートのみが適切なアルゴリズムになります。

于 2013-03-01T19:51:23.737 に答える
2

あなたのコードをデバッグchoosePivotしたところ、 を呼び出すと要素が 1 つしかなく、完全に消去されていることがわかります。

enter quicksort(array, 2, 3)
1  //content of region
enter partition(array, 2, 3)
1  //content of region 
enter choosePivot(array, 2, 3)
1  //content of region 
0  //content of region - WAIT, WHAT HAPPENED TO THE ONE
end choosePivot
0   //content of region
end partition

そのため、少なくとも問題の場所が見つかりました: choosePivot。その関数を注意深く見てみると、最終的に次のエラーに気付きました。

void choosePivot(int theArray[], int first, int last){
    //cerr << "enter choosePivot(array, " << first << ", " << last << ")\n";
    int mid = (last - first) / 2;
    if( (theArray[first] <= theArray[mid] &&
         theArray[mid] <= theArray[last]) ||
        (theArray[last] <= theArray[mid] &&
         theArray[mid] <= theArray[first]) ){

theArray[last]範囲外であり、配列の終わりを過ぎています。完全にランダムで無効な数値を配列にスワップし、要素の 1 つを配列からスワップしました。これは実際にはかなり頻繁に発生するようです。これが、多数でテストする前に精度をテストする理由です。

私が に変更theArray[last]したときtheArray[last-1]、あなたのコードは私のすべてのテストに合格しました。ノート:

  • C++ ライブラリには既にstd::swap.
  • あなたはすべての記憶を漏らします。と一致deleteするnewか、さらに良いことに、を使用しますstd::vector<int>
于 2013-03-01T20:21:42.777 に答える