我有一个快速排序算法，我正在尝试计算其中的比较次数。它使用随机生成的大小为 10、100、1000 和 10,000 的数组，并具有恒定的种子，因此每次都会在数组中生成相同的值。 （因此可以预先确定结果并进行比较，以检查计数是否正确）。我得到的值是 13、147、1506 和 11014。我期望的是 25、630、10292 和 132882。
/**
* @file quicksort.hpp
*/
#ifndef QUICKSORT_H
#define QUICKSORT_H
#include <algorithm>
static const int MIN_SIZE = 10; // Smallest size of an array that quicksort will sort
/**
* Sorts the items in an array into ascending order.
* @pre None.
* @post theArray is sorted into ascending order; n is unchanged.
* @param theArray The given array.
* @param first The first element to consider in theArray.
* @param last The last element to consider in theArray.
* @return the number of comparisons
*/
template<class ItemType>
int insertionSort(ItemType theArray[], int first, int last) {
int counter = 0;
for (int unsorted = first + 1; unsorted <= last; unsorted++) {
ItemType nextItem = theArray[unsorted];
int loc = unsorted;
while ((loc > first) && (counter++, theArray[loc - 1] > nextItem)) {
theArray[loc] = theArray[loc - 1];
loc--;
}
theArray[loc] = nextItem;
}
return counter;
}
/**
* Arranges two specified array entries into sorted order by
* exchanging them, if necessary.
* @param theArray The given array.
* @param i The index of the first entry to consider in theArray.
* @param j The index of the second entry to consider in theArray.
* */
template<class ItemType>
void order(ItemType theArray[], int i, int j) {
if (theArray[i] > theArray[j]) {
std::swap(theArray[i], theArray[j]);
}
}
/**
* Arranges the first, middle, and last entry in an array in sorted order.
* @pre theArray[first..last] is an array; first <= last.
* @post theArray[first..last] is is arranged so that its
* first, middle, and last entries are in sorted order.
* @param theArray The given array.
* @param first The first entry to consider in theArray.
* @param last The last entry to consider in theArray.
* @return The index of the middle entry.
*/
template<class ItemType>
int sortFirstMiddleLast(ItemType theArray[], int first, int last) {
int mid = first + (last - first) / 2;
order(theArray, first, mid); // Make theArray[first] <= theArray[mid]
order(theArray, mid, last); // Make theArray[mid] <= theArray[last]
order(theArray, first, mid); // Make theArray[first] <= theArray[mid]
return mid;
}
/**
* Partitions the entries in an array about a pivot entry for quicksort.
* @pre theArray[first..last] is an array; first <= last.
* @post theArray[first..last] is partitioned 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 entry to consider in theArray.
* @param last The last entry to consider in theArray.
* @return The index of the pivot.
*/
template<class ItemType>
int partition(ItemType theArray[], int first, int last, int counter) {
// Choose pivot using median-of-three selection
int pivotIndex = sortFirstMiddleLast(theArray, first, last);
// Reposition pivot so it is last in the array
std::swap(theArray[pivotIndex], theArray[last - 1]);
pivotIndex = last - 1;
ItemType pivot = theArray[pivotIndex];
// Determine the regions S1 and S2
int indexFromLeft = first + 1;
int indexFromRight = last - 2;
bool done = false;
while (!done) {
// Locate first entry on left that is >= pivot
while (counter++, theArray[indexFromLeft] < pivot) {
indexFromLeft = indexFromLeft + 1;
}
// Locate first entry on right that is <= pivot
while (counter++, theArray[indexFromRight] > pivot) {
indexFromRight = indexFromRight - 1;
}
if (indexFromLeft < indexFromRight) {
std::swap(theArray[indexFromLeft], theArray[indexFromRight]);
indexFromLeft = indexFromLeft + 1;
indexFromRight = indexFromRight - 1;
}
else {
done = true;
}
}
// Place pivot in proper position between S1 and S2, and mark its new location
std::swap(theArray[pivotIndex], theArray[indexFromLeft]);
pivotIndex = indexFromLeft;
counter++;
return pivotIndex;
}
/**
* Sorts an array into ascending order. Uses the quick sort with
* median-of-three pivot selection for arrays of at least MIN_SIZE
* entries, and uses the insertion sort for other arrays.
* @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.
* @return the number of comparisons
*/
template<class ItemType>
int quicksort(ItemType theArray[], int first, int last, int& counter) {
if (last - first + 1 < MIN_SIZE) {
counter += insertionSort(theArray, first, last);
}
else {
// Create the partition: S1 | Pivot | S2
int pivotIndex = partition(theArray, first, last, counter);
// Sort subarrays S1 and S2
quicksort(theArray, first, pivotIndex - 1, counter);
quicksort(theArray, pivotIndex + 1, last, counter);
}
return counter;
}
#endif
这是快速排序的代码。
std::cout << "Quicksort ";
std::cout << " " << std::left << quicksort(makeRandomArray(10, seed), 0, 10-1, comparisons);
comparisons = 0;
std::cout << " " << quicksort(makeRandomArray(100, seed), 0, 100-1, comparisons);
comparisons = 0;
std::cout << " " << quicksort(makeRandomArray(1000, seed), 0, 1000-1, comparisons);
comparisons = 0;
std::cout << " " << quicksort(makeRandomArray(10000, seed), 0, 10000-1, comparisons) << std::endl;
这是 main.cpp 文件中用于打印快速排序比较的代码。我知道它并不漂亮或高效，但就目前而言，它有效。我只是想让我的快速排序计数准确。 编辑：数组生成器的代码：
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;
}
如果是我，我可能会创建一个小类模板来重载
operator<template <class T>
class comparison_counter {
static unsigned comparisons = 0;
T value;
public:
comparison_counter(T t) : value(t) {}
bool operator<(comparison_counter const &other) {
++comparisons;
return value < other.value;
}
comparison_counter &operator=(T t) { value = t; return *this; }
void reset_counter() { comparisons = 0; }
// ...
};
unsigned comparison_counter::comparisons;
我没有详细检查您的代码——您可能需要支持更多一些操作来访问底层值，但这只是总体思路。
有了这个，你就可以对
std::vector<int>std::vector<comparison_counter<int>>comparison_counter::comparisons一些注意事项：
reset_counter