c++插入排序计数比较

Question

我正在做一个项目，要求我们实现不同的排序并添加计数器变量来测量具有不同数组大小的运行时。我的问题是，我当前的输出与插入排序的预期输出不匹配。

有什么建议是错的吗？

输出：

  Array Size:            10         100         1000         10000
--------------------------------------------------------------------
Insertion sort           41         2605       242934     25053573

预期输出：

Array Size       10    100    1000      10000
Insertion Sort | 38 | 2600 | 242928 | 25053566 

对于数组大小为10的数组，数组内容中包含什么内容

Insertion sort

[ 935, 942, 697, 299, 382, 579, 408, 181, 366, 505 ] //unsorted
[ 181, 299, 366, 382, 408, 505, 579, 697, 935, 942 ] //sorted

template<class ItemType>
int insertionsort(ItemType theArray[], int n) {
  int counter = 0; //keeps track of number of comparisons

    for (int unsorted = 1; unsorted < n; unsorted++) {
        ItemType nextItem = theArray[unsorted];
        int loc = unsorted;
        counter++;//increment here
        
        while ((loc > 0) && (theArray[loc - 1] > nextItem)) {
          //removed this after comment suggested it
          //if(theArray[loc - 1] > loc){
            counter++; //increment here
          //}
            theArray[loc] = theArray[loc - 1];
            loc--;
        }
        theArray[loc] = nextItem;
    }

    return counter;//returns the number of comaparisons
}


int* makeRandomArray(int n, int seed) {
    srand(seed);
    int * a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 1000;
    }
    return a;
}

int main(){
    const int seed = 9000;
    /******************************/
    /* Start of Insertion Sort    */
    /******************************/

    std::cout << "Insertion sort";

    n = 10;
    int* a;

    a = makeRandomArray(10, seed);
    std::cout <<std::setw(13)<< insertionsort(a, n);
    delete[] a;

    n = 100;
    a = makeRandomArray(100, seed);
    std::cout <<std::setw(13)<< insertionsort(a, n);
    delete[] a;

    n = 1000;
    a = makeRandomArray(1000, seed);
    std::cout <<std::setw(13)<< insertionsort(a, n);
    delete[] a;

    n = 10000;
    a = makeRandomArray(10000, seed);
    std::cout <<std::setw(13)<< insertionsort(a, n)<<std::endl;
    delete[] a;
}
#endif

Answer 1

您的计数(counter++;与比较不同步。

我把计数移到了比较和got the desired result之前。

template<class ItemType>
int insertionsort(ItemType theArray[], int n) {
  int counter = 0; //keeps track of number of comparisons

    for (int unsorted = 1; unsorted < n; unsorted++) {
        ItemType nextItem = theArray[unsorted];
        int loc = unsorted;
        // remove this
        //counter++;//increment here
        
        // add counter++ just before the comparision
        while ((loc > 0) && (counter++, theArray[loc - 1] > nextItem)) {
          if(theArray[loc - 1] > loc){
            // remove this
            //counter++; //increment here
          }
            theArray[loc] = theArray[loc - 1];
            loc--;
        }
        theArray[loc] = nextItem;
    }

    return counter;//returns the number of comaparisons
}

请注意，rand()返回的内容取决于环境，因此在不同的环境下，结果可能会有所不同。