Should process (at least) the following record types: integer-valued keys string
ID: 3603505 • Letter: S
Question
Should process (at least) the following record types:
integer-valued keys
string-valued keys
ordered pairs of string-valued and integer-valued keys
Provide a comparison method for each record type.
When we sort our records we will first perform replacement selection then merge.
The number of entries in the k-way tournament sort (k) will be the number of sorted runs.
Write the following statistics to a log file:
an identification of which file the (input) unsorted records are from,
an identification of which file the (output) sorted records are placed in,
the number of records that can fit in memory,
the number of records,
the number of runs,
the smallest, largest and arithmetic mean number or records in all of the runs,
A sorted file of records will be generated for each of our categories of record.
Write a program that demonstrates that your file sorter works for a sufficiently large count of records in memory.
Implement in C++ a back-to-back, dual heap, replacement selection algorithm.
Initialize: a vector to serve as the replacement selection container.
Once the vector size (defaulting to 8 fixed-size records) has been set, the vector size will be fixed at that value for its lifetime.
The vector's type should be templated.
Files:
a file to receive a sequence of sorted lists.
a file to receive the byte offsets (or RRNs) of the sequence of sorted lists.
a heap direction flag.
If TRUE, the active heap's head is on the left end, and the pending heap's head is on the right end.
Else if FALSE, the active heap's head is on the right end, and the pending heap's head is on the left end.
The default value is TRUE
While the replacement selection vector is not full:
heapify a new element (if there is one)
While there's a new element:
Pop the root of the current heap, adding it to the current sorted list.
If the new element is (for a min-heap) greater than or equal to the last element popped, push it onto the current heap
If the new element is (for a min-heap) less than the last element popped,
push it onto the pending heap
decrement the current heap size counter, and increment the pending heap size counter.
If the current heap size is zero,
terminate the current sorted list
initialize a new sorted list
toggle the heap direction flag
you will have current_heap_push(), current_heap_pop(), and pending_heap_push() methods, as they'll operate differently.
When the input is exhausted, pop the remaining elements of the active heap into the current list and then (if not empty) pop the remaining elements of the pending heap into the final list.
Finishing (consistency checks):
Verify that the count of records in the entry-sequenced file is equivalent to the count of records in the set of sorted lists file.
Verify that each sorted list is monotonically ordered.
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <stdexcept>
#include <algorithm>
int randInt(const int lo, const int hi) {
return (rand() % std::abs(hi-lo+1)) + lo;
}
template<typename T>
void print2DVector(std::vector< std::vector<T> > values, std::string linePretext = "Subvector", int lineWidth = 10, bool verbose = true) {
int runLengthSum = 0
, numElementsSum = 0;
T val
, previousElement;
bool isSorted = true
, sortDirection = (values[0][0] < values[0][1]); //true = ascending
for (int jj = 0; jj < values.size(); jj++) {
//add pretext
if (verbose) {
std::cout << linePretext << jj << ": ";
}
runLengthSum += values[jj].size();
for (int kk = 0; kk < values[jj].size(); kk++) {
val = values[jj][kk];
//count elements
numElementsSum++;
//determine if all vectors are sorted in the same direction
if (kk == 0) {
previousElement = val;
} else if (sortDirection && previousElement > val && isSorted) {
isSorted = false;
}
if (verbose) {
//split lines
if (kk % lineWidth == 0 && kk < values[jj].size() - 1) {
std::cout << " ";
}
//output value
std::cout << val;
//add commas
if (kk != values[jj].size() - 1) {
std::cout << ',';
}
}
}
if (verbose) {
std::cout << " ";
}
}
std::cout << "Total number of elements: " << std::to_string(numElementsSum) << std::endl;
std::cout << "Average run length: " << std::to_string(runLengthSum / values.size()) << std::endl;
std::cout << "All runs are " << (isSorted ? "" : "NOT ") << "sorted!" << std::endl;
}
template <class T>
class DualHeap
{
private:
std::vector<T> _V; //holds both heaps
int current_heap_head
, current_heap_tail
, pending_heap_head
, pending_heap_tail
, capacity;
bool heapDirection //true => active heap = "fwd" heap
, sortDirection; //true => sort ascending
int realLeftHeapIndex(const int virtualIndex) {
return virtualIndex - 1;
}
int realRightHeapIndex(const int virtualIndex) {
return capacity - virtualIndex;
}
int virtualLeftHeapIndex(const int realIndex) {
return realIndex + 1;
}
int virtualRightHeapIndex(const int realIndex) {
return capacity - realIndex;
}
int virtualIndex(const int realIndex) {
if (isInLeftHeap(realIndex)) {
return virtualLeftHeapIndex(realIndex);
} else if (isInRightHeap(realIndex)) {
return virtualRightHeapIndex(realIndex);
} else {
throw std::runtime_error("index out of range (" + std::to_string(realIndex) + ')');
}
}
int realLeftHeapTailIndex() {
return (heapDirection ? realLeftHeapIndex(current_heap_tail) : realLeftHeapIndex(pending_heap_tail));
}
int realLeftHeapHeadIndex() {
return 0;
}
int realRightHeapTailIndex() {
return (heapDirection ? realRightHeapIndex(pending_heap_tail) : realRightHeapIndex(current_heap_tail));
}
int realRightHeapHeadIndex() {
return capacity - 1;
}
bool isInLeftHeap(const int realIndex) {
return (realIndex <= realLeftHeapTailIndex());
}
bool isInRightHeap(const int realIndex) {
return (realIndex >= realRightHeapTailIndex());
}
bool hasChildren(const int realParentIndex) {
if ( isInLeftHeap(realParentIndex) ) {
return ( virtualIndex(realParentIndex) * 2 <= virtualIndex(realLeftHeapTailIndex()) );
}
else if ( isInRightHeap(realParentIndex) ) {
return ( virtualIndex(realParentIndex) * 2 <= virtualIndex(realRightHeapTailIndex()) );
}
else {
return false;
}
}
int realLeftChildIndex(const int realParentIndex) {
int leftChildIndex = -1
, candidateLeftChild;
if ( isInLeftHeap(realParentIndex) ) {
candidateLeftChild = realLeftHeapIndex( virtualLeftHeapIndex(realParentIndex) * 2 );
if ( isInLeftHeap(candidateLeftChild) ) {
leftChildIndex = candidateLeftChild;
}
} else if ( isInRightHeap(realParentIndex) ) {
candidateLeftChild = realRightHeapIndex( virtualRightHeapIndex(realParentIndex) * 2 );
if ( isInRightHeap(candidateLeftChild) ) {
leftChildIndex = candidateLeftChild;
}
}
return leftChildIndex;
}
int realRightChildIndex(const int realParentIndex) {
int rightChildIndex = -1
, candidateRightChild;
if ( isInLeftHeap(realParentIndex) ) {
candidateRightChild = realLeftHeapIndex( virtualLeftHeapIndex(realParentIndex) * 2 + 1 );
if ( isInLeftHeap(candidateRightChild) ) {
rightChildIndex = candidateRightChild;
}
} else if ( isInRightHeap(realParentIndex) ) {
candidateRightChild = realRightHeapIndex( virtualRightHeapIndex(realParentIndex) * 2 + 1 );
if ( isInRightHeap(candidateRightChild) ) {
rightChildIndex = candidateRightChild;
}
}
return rightChildIndex;
}
int realParentIndex(const int realChildIndex) {
int parentIndex = -1;
if (isInLeftHeap(realChildIndex) && virtualLeftHeapIndex(realChildIndex) != 1) {
parentIndex = realLeftHeapIndex(virtualLeftHeapIndex(realChildIndex) / 2);
}
else if (isInRightHeap(realChildIndex) && virtualRightHeapIndex(realChildIndex) != 1) {
parentIndex = realRightHeapIndex(virtualRightHeapIndex(realChildIndex) / 2);
}
return parentIndex;
}
void swapHeaps() {
int temp;
//swap heads
temp = current_heap_head;
current_heap_head = pending_heap_head;
pending_heap_head = temp;
//swap tails
temp = current_heap_tail;
current_heap_tail = pending_heap_tail;
pending_heap_tail = temp;
}
void swapByRealIndex(const int realIndex1, const int realIndex2) {
T temp = _V[realIndex1];
_V[realIndex1] = _V[realIndex2];
_V[realIndex2] = temp;
}
bool shouldSwapByRealIndex(const int realChildIndex, const int realParentIndex) {
if (sortDirection) {
//minheap
return _V[realChildIndex] < _V[realParentIndex];
} else {
//maxheap
return _V[realChildIndex] > _V[realParentIndex];
}
}
void heapifyUpByRealIndex(const int realIndex) {
int childIndex = realIndex
, parentIndex = realParentIndex(childIndex);
if (parentIndex != -1) {
if (shouldSwapByRealIndex(childIndex, parentIndex)) {
swapByRealIndex(childIndex, parentIndex);
heapifyUpByRealIndex(parentIndex);
}
}
}
void heapifyDownByRealIndex(const int realIndex) {
if ( hasChildren(realIndex) ) {
int parentIndex = realIndex
, leftChildRealIndex = realLeftChildIndex(realIndex)
, rightChildRealIndex = realRightChildIndex(realIndex)
, potentialSwapIndex = -1;
if (leftChildRealIndex != -1) {
if (rightChildRealIndex != -1) {
if (sortDirection) {
potentialSwapIndex = (_V[leftChildRealIndex] < _V[rightChildRealIndex] ? leftChildRealIndex : rightChildRealIndex);
} else {
potentialSwapIndex = (_V[leftChildRealIndex] > _V[rightChildRealIndex] ? leftChildRealIndex : rightChildRealIndex);
}
} else {
potentialSwapIndex = leftChildRealIndex;
}
if (shouldSwapByRealIndex(potentialSwapIndex, parentIndex)) {
swapByRealIndex(potentialSwapIndex, parentIndex);
heapifyDownByRealIndex(potentialSwapIndex);
}
} else {
//no children: done
}
} else {
//no children: done
}
}
public:
DualHeap(const int totalcapacity, const bool _sortDirection = true, const bool _heapDirection = true) {
//set the total combined capacity of both heaps
capacity = totalcapacity;
_V.reserve(capacity);
//initialize to zeroes (arbitrary)
// for (int ii = 0; ii < capacity; ii++) {
// _V[ii] = 0;
// }
//set initial virtual head and tail indices
current_heap_head = pending_heap_head = 1;
current_heap_tail = pending_heap_tail = 0;
sortDirection = _sortDirection; //true = right
heapDirection = _heapDirection; //left heap first = right
}
int get_size() {
return current_heap_size() + pending_heap_size();
}
int get_capacity() {
return capacity;
}
int current_heap_size() {
return (current_heap_tail == 0 ? 0 : std::abs(current_heap_head - current_heap_tail) + 1);
}
int pending_heap_size() {
return (pending_heap_tail == 0 ? 0 : std::abs(pending_heap_head - pending_heap_tail) + 1);
}
void current_heap_push(const T element) {
if ( (current_heap_size() + pending_heap_size()) < capacity ) {
int realTailIndex = -1;
//increase current heap size by 1
current_heap_tail += 1;
if (heapDirection) {// active heap = left
realTailIndex = realLeftHeapIndex(current_heap_tail);
} else { //active heap = right
realTailIndex = realRightHeapIndex(current_heap_tail);
}
//store new element at the left heap's tail
_V[realTailIndex] = element;
//heapify the left heap
heapifyUpByRealIndex(realTailIndex);
}
}
void pending_heap_push(const T element) {
reverse_direction();
current_heap_push(element);
reverse_direction();
}
T current_heap_pop() {
if (current_heap_size() > 0){
T returnElement;
if (heapDirection) { //left heap is current
// pop head
returnElement = _V[realLeftHeapIndex(current_heap_head)];
//replace with tail
_V[realLeftHeapIndex(current_heap_head)] = _V[realLeftHeapIndex(current_heap_tail)];
//reduce size by 1
current_heap_tail -= 1;
//heapify down
heapifyDownByRealIndex(realLeftHeapIndex(current_heap_head));
} else {
// pop head
returnElement = _V[realRightHeapIndex(current_heap_head)];
// replace with tail
_V[realRightHeapIndex(current_heap_head)] = _V[realRightHeapIndex(current_heap_tail)];
// reduce size by 1
current_heap_tail -= 1;
//heapify down
heapifyDownByRealIndex(realRightHeapIndex(current_heap_head));
}
//return head
return returnElement;
} else {
throw std::runtime_error("Empty heap!");
}
}
T pending_heap_pop() {
T returnElement;
reverse_direction();
returnElement = current_heap_pop();
reverse_direction();
return (returnElement);
}
std::string stringify() {
int leftHeapSize = (heapDirection ? current_heap_size() : pending_heap_size());
std::string returnString = "";
for (int ii = 0; ii < capacity; ii++) {
if (
ii == realRightHeapIndex(heapDirection ? pending_heap_tail : current_heap_tail) ||
ii == realLeftHeapIndex(heapDirection ? current_heap_tail : pending_heap_tail) + 1
) {
returnString += " | ";
} else {
if (ii > 0) {
returnString += ", ";
}
}
returnString += ' ' + _V[ii];
}
return returnString;
}
void reverse_direction() {
heapDirection = !heapDirection;
swapHeaps();
}
}; //DualHeap
template <class T>
class ReplacementSelectionSort
{
private:
public:
static std::vector< std::vector<T> > sort(
const std::vector<T> vectorToBeSorted,
const int heapSize = 10,
const bool sortDirection = true,
const bool DEBUG = false
)
{
if (heapSize < 1) {
throw std::runtime_error("Heap must be of size 1 or greater");
}
std::vector< std::vector<T> > *returnVector = new std::vector< std::vector<T> >;
DualHeap<T> *myDualHeap = new DualHeap<T>( heapSize, sortDirection );
//While the replecement selection vector is not full, heapify a new element
T el;
int totalCapacity = myDualHeap->get_capacity();
int nextItemToSort;
if(DEBUG){std::cout << "adding: ";}
for (int ii = 0; ii < totalCapacity && ii < vectorToBeSorted.size(); ii++) {
el = vectorToBeSorted[ii];
if(DEBUG){
std::cout << el;
if (ii < totalCapacity - 1) {
std::cout << ",";
}
}
myDualHeap->current_heap_push( el );
nextItemToSort = ii + 1;
}
if (DEBUG) {
std::cout << std::endl;
std::cout << myDualHeap->stringify() << std::endl;
}
int currentList = 0;
T lastElementPopped
, nextElement;
std::vector<T> *row = new std::vector<T>;
while (nextItemToSort < vectorToBeSorted.size() || myDualHeap->get_size() > 0) {
if(DEBUG){std::cout << " heap: " << myDualHeap->stringify() << std::endl;}
lastElementPopped = myDualHeap->current_heap_pop();
if(DEBUG){std::cout << "pop: " << lastElementPopped << std::endl;}
row->push_back( lastElementPopped );
if ( nextItemToSort < vectorToBeSorted.size() ) {
nextElement = vectorToBeSorted[nextItemToSort];
nextItemToSort++;
if(DEBUG){std::cout << "add: " << nextElement << std::endl;}
if (sortDirection) {
if (nextElement < lastElementPopped) {
myDualHeap->pending_heap_push( nextElement );
} else {
myDualHeap->current_heap_push( nextElement );
}
} else {
if (nextElement > lastElementPopped) {
myDualHeap->pending_heap_push( nextElement );
} else {
myDualHeap->current_heap_push( nextElement );
}
}
}
if (myDualHeap->current_heap_size() == 0) {
//std::cout << "Reversing Direction..." << std::endl;
myDualHeap->reverse_direction();
currentList++;
returnVector->push_back( *row );
row = new std::vector<T>;
}
}
delete myDualHeap;
return *returnVector;
}
}; //ReplacementSelectionSort
template <typename T>
void DualHeapTest() {
std::cout << "Beginning DualHeap exercise/test" << std::endl;
std::cout << "Creating DualHeap(6)" << std::endl;
DualHeap<T> *myDualHeap = new DualHeap<T>(6, true);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "pending_heap_push(11): ";
myDualHeap->pending_heap_push(11);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "pending_heap_push(12): ";
myDualHeap->pending_heap_push(12);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "pending_heap_push(10): ";
myDualHeap->pending_heap_push(10);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_push(4): ";
myDualHeap->current_heap_push(4);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_push(5): ";
myDualHeap->current_heap_push(5);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_push(3): ";
myDualHeap->current_heap_push(3);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_push(9): ";
myDualHeap->pending_heap_push(9);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_push(2): ";
myDualHeap->current_heap_push(2);
std::cout << myDualHeap->stringify() << std::endl;
std::cout << "pending_heap_pop() => " << myDualHeap->pending_heap_pop() << ": " << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_pop() => " << myDualHeap->current_heap_pop() << ": " << myDualHeap->stringify() << std::endl;
std::cout << "pending_heap_pop() => " << myDualHeap->pending_heap_pop() << ": " << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_pop() => " << myDualHeap->current_heap_pop() << ": " << myDualHeap->stringify() << std::endl;
std::cout << "pending_heap_pop() => " << myDualHeap->pending_heap_pop() << ": " << myDualHeap->stringify() << std::endl;
std::cout << "current_heap_pop() => " << myDualHeap->current_heap_pop() << ": " << myDualHeap->stringify() << std::endl;
try {
std::cout << "(!) pending_heap_pop(): " << myDualHeap->pending_heap_pop() << std::endl;
}
catch (std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
delete myDualHeap;
myDualHeap = nullptr;
}
template <typename T>
void replacementSelectionSortTest(const std::vector<T> SAMPLE_DATA,
const int HEAP_SIZE,
const bool verbose = false,
const bool ultra_verbose = false) {
std::vector< std::vector<T> > results = ReplacementSelectionSort<T>::sort( SAMPLE_DATA, HEAP_SIZE, true, false );
std::cout << "Least to Greatest: " << std::endl;
print2DVector(results, "Run #", 10, verbose);
results = ReplacementSelectionSort<T>::sort( SAMPLE_DATA, HEAP_SIZE, false, false );
std::cout << "Greatest to Least: " << std::endl;
print2DVector(results, "Run #", 10, verbose);
}
template <typename T>
void replacementSelectionSortTest(const int SAMPLE_SIZE,
const int HEAP_SIZE,
const int SAMPLE_MIN,
const int SAMPLE_MAX,
const int SAMPLE_OFFSET,
const bool verbose = false,
const bool partialSort = false,
const bool fullSort = false,
const bool sortDirection = true,
const bool ultra_verbose = false)
{
std::vector<T> sampleData;
T val;
//generate sample data
for (int ii = 0; ii < SAMPLE_SIZE; ii++) {
val = SAMPLE_OFFSET + randInt(SAMPLE_MIN, SAMPLE_MAX);
sampleData.push_back(val);
}
//sort if flagged
if (fullSort) {
std::sort (sampleData.begin(), sampleData.end());
if (!sortDirection) {
std::reverse(sampleData.begin(), sampleData.end());
}
} else if (partialSort) {
std::partial_sort (sampleData.begin(), (sampleData.begin() + sampleData.size()/2), sampleData.end());
if (!sortDirection) {
std::reverse(sampleData.begin(), sampleData.end());
}
}
//show contents
if (ultra_verbose) {
for (int jj = 0; jj < sampleData.size(); jj++) {
std::cout << sampleData[jj];
if (jj < SAMPLE_SIZE - 1) {
std::cout << ",";
}
}
std::cout << std::endl;
}
replacementSelectionSortTest<T>(sampleData, HEAP_SIZE, verbose, ultra_verbose);
}
char* getArgVal(char* arg) {
return std::strtok(NULL, std::strtok(arg, "="));
}
//sample data item type
enum ItemType
{
INT,
CHAR,
STRING
};
int main(int argc, char* argv[]) {
std::vector<std::string> sampleData;
sampleData.push_back("apples");
sampleData.push_back("oranges");
sampleData.push_back("bananas");
sampleData.push_back("cucumbers");
sampleData.push_back("ducks");
sampleData.push_back("iguanas");
sampleData.push_back("zebras");
sampleData.push_back("porcupines");
sampleData.push_back("quills");
sampleData.push_back("fingers");
sampleData.push_back("toes");
sampleData.push_back("bows");
sampleData.push_back("arrows");
sampleData.push_back("swords");
sampleData.push_back("helmets");
sampleData.push_back("cheese");
int SAMPLE_SIZE = 100
, HEAP_SIZE = 10
, SAMPLE_MIN = 0
, SAMPLE_MAX = 10
, SAMPLE_OFFSET = 0;
ItemType type;
bool verbose = false
, ultra_verbose = false
, PARTIAL_SORT = false
, FULL_SORT = false
, SORT_DIRECTION = true;
//experimenting with command line arguments
for (int ii = 1; ii < argc; ii++) {
//run test with integers
if (!std::strncmp(argv[ii], "-int", 4)) {
type = INT;
}
//run test with chars
if (!std::strncmp(argv[ii], "-char", 5)) {
type = CHAR;
}
if (!std::strncmp(argv[ii], "-string", 7)) {
type = STRING;
}
if (!std::strncmp(argv[ii], "-v", 2)) {
verbose = true;
}
if (!std::strncmp(argv[ii], "-vv", 3)) {
ultra_verbose = true;
verbose = true;
}
if (!std::strncmp(argv[ii], "-sort", 5)) {
FULL_SORT = true;
PARTIAL_SORT = false;
}
if (!std::strncmp(argv[ii], "-sortpartial", 12)) {
FULL_SORT = false;
PARTIAL_SORT = true;
}
if (!std::strncmp(argv[ii], "-fwd", 4) ||
!std::strncmp(argv[ii], "-forward", 8)) {
SORT_DIRECTION = true;
}
if (!std::strncmp(argv[ii], "-rev", 4) ||
!std::strncmp(argv[ii], "-reverse", 8)) {
SORT_DIRECTION = false;
}
if (!std::strncmp(argv[ii], "-samplesize=", 12) || !std::strncmp(argv[ii], "-sample=", 8)) {
SAMPLE_SIZE = std::atoi(getArgVal(argv[ii]));
}
if (!std::strncmp(argv[ii], "-heapsize=", 10) || !std::strncmp(argv[ii], "-heap=", 6)) {
HEAP_SIZE = std::atoi(getArgVal(argv[ii]));
}
if (!std::strncmp(argv[ii], "-samplemin=", 11) || !std::strncmp(argv[ii], "-min=", 5)) {
SAMPLE_MIN = std::atoi(getArgVal(argv[ii]));
}
if (!std::strncmp(argv[ii], "-samplemax=", 11) || !std::strncmp(argv[ii], "-max=", 5)) {
SAMPLE_MAX = std::atoi(getArgVal(argv[ii]));
}
if (!std::strncmp(argv[ii], "-sampleoffset=", 14) || !std::strncmp(argv[ii], "-off=", 5)) {
SAMPLE_OFFSET = std::atoi(getArgVal(argv[ii]));
}
}
if (argc == 1) {
std::cout << " Please specify a type (-int or -char) ";
} else {
if (type == INT) {
std::cout << " Running with sample size:" << SAMPLE_SIZE << ", ";
std::cout << "heap size:" << HEAP_SIZE << ", ";
std::cout << "minimum sample size:" << SAMPLE_MIN << ", ";
std::cout << "maximum sample size:" << SAMPLE_MAX << ", ";
std::cout << "sample offset:" << SAMPLE_OFFSET << " ";
replacementSelectionSortTest<int>(
SAMPLE_SIZE,
HEAP_SIZE,
SAMPLE_MIN,
SAMPLE_MAX,
SAMPLE_OFFSET,
verbose,
PARTIAL_SORT,
FULL_SORT,
SORT_DIRECTION,
ultra_verbose);
}
if (type == CHAR) {
if (SAMPLE_OFFSET == 0 && SAMPLE_MIN == 0) { SAMPLE_OFFSET = 65; SAMPLE_MAX = 25; };
std::cout << " Running with sample size:" << SAMPLE_SIZE << ", ";
std::cout << "heap size:" << HEAP_SIZE << ", ";
std::cout << "minimum sample:" << (char)(SAMPLE_OFFSET + SAMPLE_MIN) << ", ";
std::cout << "maximum sample:" << (char)(SAMPLE_OFFSET + SAMPLE_MAX) << ", ";
std::cout << "(sample offset:" << SAMPLE_OFFSET << ") ";
replacementSelectionSortTest<char>(
SAMPLE_SIZE,
HEAP_SIZE,
SAMPLE_MIN,
SAMPLE_MAX,
SAMPLE_OFFSET,
verbose,
PARTIAL_SORT,
FULL_SORT,
SORT_DIRECTION,
ultra_verbose);
}
if (type == STRING) {
std::cout << " Running with arbitrary string data" << std::endl;
replacementSelectionSortTest<std::string>(sampleData, 10, true, true);
}
}
return 0;
}