Partitioning an Array - kSmall

Last week we created a function that partitions an array into three portions,an array that could be of any size from 0 to 7,428,948 elements or even more! The three portions, S1, the pivot, and S2 are:

1. S1 - index values less than the pivot index contain all values in the array less than or equal to the pivot value.
2. The Pivot - existing at the pivot index, this is the pivot value.
3. S2 - index values greater than the pivot index contain all values in the array greater than the pivot value.

This partition description is outlined:

1. Replace the array in your function with the arrayTracker object.
2. Generalize the partition function to partition a sub-set of the array.

Problem:

Replace any instance of an array with the arrayTracker object

Generalize the partition function to allow it to partition a portion of the array, instead of the whole thing. We do this using the startIndex and endIndex values. In last module's programming problem, we assumed

pivotIndex = 0; 

This week we generalize this with

pivotIndex = startIndex;

This allows the partition function to partition a part of the array (and not the whole array) and create a function that can search for the kth smallest element in the array.

Files and Tools

It includes a main file with testing cases, a solution object (.cpp and .hpp), and an array tracker object (.cpp and .hpp). These objects work together in the main.cpp file to test the success of the solution object's ksmallPartion method.

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; }

arrayTracker.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

#endif /*ARRAY_TRACKER_CPP*/

arrayTracker.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 /*ARRAY_TRACKER_HPP*/

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); /* YOUR CODE GOES HERE */ return pivotIndex; }

#endif /* KSMALL_SOLUTION_CPP */

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 /* KSMALL_SOLUTION_HPP */

main (include a main file)

Problem continued:

Currently, the ksmallPartition method consists of

int kSmallPartition(int startIndex, int endIndex, arrayTracker* anArray) { int pivotIndex = startIndex; int pivotValue = anArray->getItem(pivotIndex); /* YOUR CODE GOES HERE */ return pivotIndex; }

You are to edit this document. Your solution should consist of ONLY edits to this document (although in testing and exploration, you may choose to edit other files - the submission you submit will be the ksmallSolution.cpp file alone and that file must work with the other files without changing the other files).

This method accepts a pointer to an object called an arrayTracker. (The arrayTracker works like an array - but with some extra benefits. You can find information about the area tracker and how it works in the resources video of last module). The arrayTracker contains an array that is unsorted. You must take the first element of that array, at index position 0, (we refer to this as the pivot value) with something like

int pivotIndex = startIndex; int pivotValue = anArray->getItem(pivotIndex);

and 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 position 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.

Solution 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