C++

main,cpp:

#include

#include

#include "ksmallSolution.hpp"

using namespace std;

int main() {

arrayTracker* testArray;

cout << "Test 01: odd number elements" << endl;

int test01[] = {4, 6, 2, 5, 8};

int testSize = sizeof(test01)/sizeof(test01[0]);

testArray = new arrayTracker(testSize, test01);

testArray->displayArray();

cout << "pivotIndex:" << kSmallPartition(0, testSize-1, testArray) << endl;

testArray->displayArray();

delete testArray;

cout << endl;

cout << "Test 02: even number elements" << endl;

int test02[] = {8, 7, 56, 78, 4, 6, 2, 5};

testSize = sizeof(test02)/sizeof(test02[0]);

testArray = new arrayTracker(testSize, test02);

testArray->displayArray();

cout << "pivotIndex:" << kSmallPartition(0, testSize-1, testArray) << endl;

testArray->displayArray();

delete testArray;

cout << endl;

cout << "Test 03: pivot already correct" << endl;

int test03[] = {2 , 7 , 56, 78, 4, 6, 8, 5 , 8};

testSize = sizeof(test03)/sizeof(test03[0]);

testArray = new arrayTracker(testSize, test03);

testArray->displayArray();

cout << "pivotIndex:" << kSmallPartition(0, testSize-1, testArray) << endl;

testArray->displayArray();

delete testArray;

cout << endl;

cout << "Test 03: empty array" << endl;

int test04[] = {};

testSize = 0;

testArray = new arrayTracker(testSize, test04);

testArray->displayArray();

cout << "pivotIndex:" << kSmallPartition(0, testSize-1, testArray) << endl;

testArray->displayArray();

delete testArray;

cout << endl;

int test05[] = {900, 40, 297, 388, 57, 965, 419, 43, 535, 513, 939, 410, 435, 214, 73, 122, 674, 335, 983, 91, 725, 32, 65, 377, 962, 677, 699, 262, 503, 286, 539, 231, 784, 345, 140, 642, 702, 824, 58, 939, 850, 55, 547, 970, 210, 364, 378, 202, 797, 363, 399, 996, 314, 379, 833, 765, 937, 161, 223, 868, 972, 467, 301, 226, 84, 400, 502, 290, 142, 618, 750, 91, 129, 974, 877, 857, 861, 570, 599, 926};

testSize = sizeof(test05)/sizeof(test05[0]);

testArray = new arrayTracker(testSize, test05);

cout << "Your Solution Code is: " << kSmallPartition(0, testSize-1, testArray) << endl;

}

anArray.cpp:

#ifndef ARRAY_TRACKER_CPP

#define ARRAY_TRACKER_CPP

#include

#include

#include

#include

#include "arrayTracker.hpp"

using namespace std;

arrayTracker::arrayTracker() {

useCount = 0;

}

arrayTracker::arrayTracker(int newSize) {

useCount = 0;

receipt = (unsigned) time(0);

srand(receipt);

for(int i = 0; i < newSize; i++) {

items[i] = rand()%newSize;

}

arraySize = newSize;

}

arrayTracker::arrayTracker(int newSize, int anArray[]) {

useCount = 0;

receipt = (unsigned) time(0);

srand(receipt);

for(int i = 0; i < newSize; i++) {

items[i] = anArray[i];

}

arraySize = newSize;

}

arrayTracker::arrayTracker(int newSize, int seedValue) {

useCount = 0;

receipt = seedValue;

srand(receipt);

for(int i = 0; i < newSize; i++) {

items[i] = rand()%newSize;

}

arraySize = newSize;

}

int arrayTracker::getUseCount() {

return useCount;

}

int arrayTracker::getItem(int itemIdx) {

if(itemIdx < 0 || itemIdx >= arraySize) {

cout << "ERROR: unrecognized index value: " << itemIdx << endl;

return 0;

}

useCount++;

return items[itemIdx];

}

bool arrayTracker::setItem(int itemIdx, int itemValue) {

if(itemIdx < 0 || itemIdx >= arraySize) {

cout << "ERROR: unrecognized index value: " << itemIdx << endl;

return false;

}

useCount++;

items[itemIdx] = itemValue;

return true;

}

int arrayTracker::getSize() {

return arraySize;

}

void arrayTracker::displayArray()

{

for(int i=0; i

cout << right << setfill('0') << setw(3) << i << " ";

cout << endl;

for(int i=0; i

cout << setfill(' ')<< right << setw(3) << items[i] << " ";

cout << endl;

}

#endif

anArray.hpp:

#ifndef ARRAY_TRACKER_HPP

#define ARRAY_TRACKER_HPP

const int MAX_ARRAY_SIZE = 10000;

class arrayTracker

{

private:

int items[MAX_ARRAY_SIZE];

int useCount;

int arraySize;

unsigned receipt;

public:

arrayTracker();

arrayTracker(int newSize);

arrayTracker(int newSize, int anArray[]);

arrayTracker(int newSize, int seedValue);

int getUseCount();

int getItem(int itemIdx);

bool setItem(int itemIdx, int itemValue);

int getSize();

void displayArray();

};

#endif

ksmallSolution.cpp:

#ifndef KSMALL_SOLUTION_CPP

#define KSMALL_SOLUTION_CPP

#include "ksmallSolution.hpp"

#include "arrayTracker.hpp"

void arraySwap(arrayTracker* swappingArray, int indexA, int indexB)

{

int temp = swappingArray->getItem(indexA);

swappingArray->setItem(indexA, swappingArray->getItem(indexB));

swappingArray->setItem(indexB, temp);

}

int kSmallPartition(int startIndex, int endIndex, arrayTracker* anArray)

{

int pivotIndex = startIndex;

int pivotValue = anArray->getItem(pivotIndex);

if(endIndex==-1)

{

return -1;

}

return pivotIndex;

}

#endif

ksmallSolution.hpp:

#ifndef KSMALL_SOLUTION_HPP

#define KSMALL_SOLUTION_HPP

#include "arrayTracker.hpp"

void arraySwap(arrayTracker* swappingArray, int indexA, int indexB);

int kSmallPartition(int startIndex, int endIndex, arrayTracker* unsortedArray);

#endif

rearrange the array in the arrayTracker, using the getItem and setItem methods of the arrayTracker method.

The newly arranged elements in the array must have all elements smaller than the pivot value stored at index locations less than the index postion of the pivot value and all elements larger than the pivot value stored at index locations greater than the index position of the pivot value.

Output

> ./main Test 01: odd number elements 000 001 002 003 004 4 6 2 5 8 pivotIndex:1 000 001 002 003 004 2 4 6 5 8

Test 02: even number elements 000 001 002 003 004 005 006 007 8 7 56 78 4 6 2 5 pivotIndex:5 000 001 002 003 004 005 006 007 6 7 5 2 4 8 78 56

Test 03: pivot already correct 000 001 002 003 004 005 006 007 008 2 7 56 78 4 6 8 5 8 pivotIndex:0 000 001 002 003 004 005 006 007 008 2 7 56 78 4 6 8 5 8

Test 03: empty array

pivotIndex:ERROR: unrecognized index value: 0 -1