car*_*ost 4 c++ heap mergesort quicksort insertion-sort
我正在开始使用堆的程序，其中必须将Sort，mergeSort和quickSort插入堆中。有人指示我使用课本中的代码作为基础，甚至无法编译示例代码。我不断收到错误：
not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
现在我认为这与在sort.h文件中声明template <>类的顺序有关。但是，我无法想象教科书会发布根本无法编译的代码。你们介意看看吗？
完整错误：
In file included from Driver.cpp:4:0:
Sort.h: In instantiation of 'void heapsort(std::vector<Comparable>&) [with Comparable = int]':
Driver.cpp:47:21: required from here
Sort.h:79:9: error: 'percDown' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
Sort.h:104:6: note: 'template<class Comparable> void percDown(std::vector<Comparable>&, int, int)' declared here, later in the translation unit
Sort.h:83:9: error: 'percDown' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
Sort.h:104:6: note: 'template<class Comparable> void percDown(std::vector<Comparable>&, int, int)' declared here, later in the translation unit
Sort.h: In instantiation of 'void mergeSort(std::vector<Comparable>&, std::vector<Comparable>&, int, int) [with Comparable = int]':
Sort.h:150:5: required from 'void mergeSort(std::vector<Comparable>&) [with Comparable = int]'
Driver.cpp:53:22: required from here
Sort.h:138:9: error: 'merge' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
Sort.h:163:6: note: 'template<class Comparable> void merge(std::vector<Comparable>&, std::vector<Comparable>&, int, int, int)' declared here, later in the translation unit
Sort.h：
#ifndef SORT_H
#define SORT_H
/**
* Several sorting routines.
* Arrays are rearranged with smallest item first.
*/
#include <vector>
#include <functional>
using namespace std;
/**
* Simple insertion sort.
*/
template <typename Comparable>
void insertionSort( vector<Comparable> & a )
{
for( int p = 1; p < a.size( ); ++p )
{
Comparable tmp = std::move( a[ p ] );
int j;
for( j = p; j > 0 && tmp < a[ j - 1 ]; --j )
a[ j ] = std::move( a[ j - 1 ] );
a[ j ] = std::move( tmp );
}
}
/**
* Internal insertion sort routine for subarrays
* that is used by quicksort.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable>
void insertionSort( vector<Comparable> & a, int left, int right )
{
for( int p = left + 1; p <= right; ++p )
{
Comparable tmp = std::move( a[ p ] );
int j;
for( j = p; j > left && tmp < a[ j - 1 ]; --j )
a[ j ] = std::move( a[ j - 1 ] );
a[ j ] = std::move( tmp );
}
}
/**
* Shellsort, using Shell's (poor) increments.
*/
template <typename Comparable>
void shellsort( vector<Comparable> & a )
{
for( int gap = a.size( ) / 2; gap > 0; gap /= 2 )
for( int i = gap; i < a.size( ); ++i )
{
Comparable tmp = std::move( a[ i ] );
int j = i;
for( ; j >= gap && tmp < a[ j - gap ]; j -= gap )
a[ j ] = std::move( a[ j - gap ] );
a[ j ] = std::move( tmp );
}
}
/**
* Standard heapsort.
*/
template <typename Comparable>
void heapsort( vector<Comparable> & a )
{
for( int i = a.size( ) / 2 - 1; i >= 0; --i ) /* buildHeap */
percDown( a, i, a.size( ) );
for( int j = a.size( ) - 1; j > 0; --j )
{
std::swap( a[ 0 ], a[ j ] ); /* deleteMax */
percDown( a, 0, j );
}
}
/**
* Internal method for heapsort.
* i is the index of an item in the heap.
* Returns the index of the left child.
*/
inline int leftChild( int i )
{
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* i is the position from which to percolate down.
* n is the logical size of the binary heap.
*/
template <typename Comparable>
void percDown( vector<Comparable> & a, int i, int n )
{
int child;
Comparable tmp;
for( tmp = std::move( a[ i ] ); leftChild( i ) < n; i = child )
{
child = leftChild( i );
if( child != n - 1 && a[ child ] < a[ child + 1 ] )
++child;
if( tmp < a[ child ] )
a[ i ] = std::move( a[ child ] );
else
break;
}
a[ i ] = std::move( tmp );
}
/**
* Internal method that makes recursive calls.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable>
void mergeSort( vector<Comparable> & a,
vector<Comparable> & tmpArray, int left, int right )
{
if( left < right )
{
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}
/**
* Mergesort algorithm (driver).
*/
template <typename Comparable>
void mergeSort( vector<Comparable> & a )
{
vector<Comparable> tmpArray( a.size( ) );
mergeSort( a, tmpArray, 0, a.size( ) - 1 );
}
/**
* Internal method that merges two sorted halves of a subarray.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* leftPos is the left-most index of the subarray.
* rightPos is the index of the start of the second half.
* rightEnd is the right-most index of the subarray.
*/
template <typename Comparable>
void merge( vector<Comparable> & a, vector<Comparable> & tmpArray,
int leftPos, int rightPos, int rightEnd )
{
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ] <= a[ rightPos ] )
tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );
else
tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );
while( leftPos <= leftEnd ) // Copy rest of first half
tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );
while( rightPos <= rightEnd ) // Copy rest of right half
tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );
// Copy tmpArray back
for( int i = 0; i < numElements; ++i, --rightEnd )
a[ rightEnd ] = std::move( tmpArray[ rightEnd ] );
}
/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
template <typename Comparable>
const Comparable & median3( vector<Comparable> & a, int left, int right )
{
int center = ( left + right ) / 2;
if( a[ center ] < a[ left ] )
std::swap( a[ left ], a[ center ] );
if( a[ right ] < a[ left ] )
std::swap( a[ left ], a[ right ] );
if( a[ right ] < a[ center ] )
std::swap( a[ center ], a[ right ] );
// Place pivot at position right - 1
std::swap( a[ center ], a[ right - 1 ] );
return a[ right - 1 ];
}
/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template <typename Comparable>
void quicksort( vector<Comparable> & a, int left, int right )
{
if( left + 10 <= right )
{
const Comparable & pivot = median3( a, left, right );
// Begin partitioning
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ] < pivot ) { }
while( pivot < a[ --j ] ) { }
if( i < j )
std::swap( a[ i ], a[ j ] );
else
break;
}
std::swap( a[ i ], a[ right - 1 ] ); // Restore pivot
quicksort( a, left, i - 1 ); // Sort small elements
quicksort( a, i + 1, right ); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort( a, left, right );
}
/**
* Quicksort algorithm (driver).
*/
template <typename Comparable>
void quicksort( vector<Comparable> & a )
{
quicksort( a, 0, a.size( ) - 1 );
}
/**
* Internal selection method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* Places the kth smallest item in a[k-1].
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
* k is the desired rank (1 is minimum) in the entire array.
*/
template <typename Comparable>
void quickSelect( vector<Comparable> & a, int left, int right, int k )
{
if( left + 10 <= right )
{
const Comparable & pivot = median3( a, left, right );
// Begin partitioning
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ] < pivot ) { }
while( pivot < a[ --j ] ) { }
if( i < j )
std::swap( a[ i ], a[ j ] );
else
break;
}
std::swap( a[ i ], a[ right - 1 ] ); // Restore pivot
// Recurse; only this part changes
if( k <= i )
quickSelect( a, left, i - 1, k );
else if( k > i + 1 )
quickSelect( a, i + 1, right, k );
}
else // Do an insertion sort on the subarray
insertionSort( a, left, right );
}
/**
* Quick selection algorithm.
* Places the kth smallest item in a[k-1].
* a is an array of Comparable items.
* k is the desired rank (1 is minimum) in the entire array.
*/
template <typename Comparable>
void quickSelect( vector<Comparable> & a, int k )
{
quickSelect( a, 0, a.size( ) - 1, k );
}
template <typename Comparable>
void SORT( vector<Comparable> & items )
{
if( items.size( ) > 1 )
{
vector<Comparable> smaller;
vector<Comparable> same;
vector<Comparable> larger;
auto chosenItem = items[ items.size( ) / 2 ];
for( auto & i : items )
{
if( i < chosenItem )
smaller.push_back( std::move( i ) );
else if( chosenItem < i )
larger.push_back( std::move( i ) );
else
same.push_back( std::move( i ) );
}
SORT( smaller ); // Recursive call!
SORT( larger ); // Recursive call!
std::move( begin( smaller ), end( smaller ), begin( items ) );
std::move( begin( same ), end( same ), begin( items ) + smaller.size( ) );
std::move( begin( larger ), end( larger ), end( items ) - larger.size( ) );
/*
items.clear( );
items.insert( end( items ), begin( smaller ), end( smaller ) );
items.insert( end( items ), begin( same ), end( same ) );
items.insert( end( items ), begin( larger ), end( larger ) );
*/
}
}
/*
* This is the more public version of insertion sort.
* It requires a pair of iterators and a comparison
* function object.
*/
template <typename RandomIterator, typename Comparator>
void insertionSort( const RandomIterator & begin,
const RandomIterator & end,
Comparator lessThan )
{
if( begin == end )
return;
RandomIterator j;
for( RandomIterator p = begin+1; p != end; ++p )
{
auto tmp = std::move( *p );
for( j = p; j != begin && lessThan( tmp, *( j-1 ) ); --j )
*j = std::move( *(j-1) );
*j = std::move( tmp );
}
}
/*
* The two-parameter version calls the three parameter version, using C++11 decltype
*/
template <typename RandomIterator>
void insertionSort( const RandomIterator & begin,
const RandomIterator & end )
{
insertionSort( begin, end, less<decltype(*begin )>{ } );
}
#endif
和Driver.cpp
//Driver.cpp
#include <iostream>
#include "Sort.h"
#include <vector>
#include <string>
#include <time.h>
using namespace std;
void checkSort( const vector<int> & a )
{
for( int i = 0; i < a.size( ); ++i )
if(a.size( ) != i )
cout << "Error at " << i << endl;
cout << "Finished checksort" << endl;
}
int main( )
{
srand(time(NULL));
int vec_length;
cout << "What would you like the length of the vector to be?" << endl;
cin >> vec_length;
vector<int> a(vec_length);
for(int i = 0; i < a.size(); i++)
{
a[i] = rand() % 100 + 1;
}
//vector<string> a( NUM_ITEMS ); // This input adds factor of N to running time
//for( int i = 1; i < a.size( ); ++i ) // but we want to test std::move logic
// a[ i ] = a[ i - 1 ] + 'a';
for( int theSeed = 0; theSeed < 10; ++theSeed )
{
insertionSort( a );
checkSort( a );
insertionSort( begin( a ), end( a ) );
checkSort( a );
heapsort( a );
checkSort( a );
shellsort( a );
checkSort( a );
mergeSort( a );
checkSort( a );
quicksort( a );
checkSort( a );
SORT( a );
checkSort( a );
quickSelect( a, vec_length / 2 );
//cout << a[vec_length / 2 - 1].size( ) << " " << vec_length / 2 << endl;
}
cout << "Checking SORT, Fig 7.13" << endl;
int N = vec_length * vec_length;
vector<int> b( N );
for( int i = 0; i < N; ++i )
b[ i ] = i;
SORT( b );
for( int i = 0; i < N; ++i )
if( b[ i ] != i )
cout << "OOPS!!" << endl;
return 0;
}