The C++ question:

The Perplexing Partition

Imagine an array that could be of any size from 0 to 6,226,013 elements or even more! We are going to rearrange this array such that:

• The first element in the array (the pivot value) is placed in its correct position if the array were ordered from smallest to largest.
• All the elements smaller than (or equal to) the pivot value are stored to the left (at lower index positions) of the pivot value
• All the elements larger than the pivot value are stored to the right (at higher index positions) of the pivot value.

This partitioning process is outlined in the Carrano textbook in section 2.4.4. Especially Figure 2-15, a partition about a pivot.

Problem

Imagine that you have an array of 5 elements, in order from index 0 to index 4: 4, 6, 2 ,5 ,8.

We are going to develop a method that:

1. accepts an array
2. identifies the first element of the array object (at index position 0) as the pivot value.
3. rearranges the array such that elements in the array less than or equal to the pivot are at an index positions less than the pivot and all elements larger than the pivot are greater than the pivot.
4. Returns the new pivot index.

In our example of 4, 6 ,2, 5, 8, our method would:

1. Accept this array as an argument.
2. identify the value 4 as our pivot value.
3. rearrange the array into: 2, 4, 6, 5, 8
4. Returns the new pivot index, 1.

The array is now sorted such that the pivot value 4 is now at index 1 (we will refer to this as the pivot value, which is 4, and the pivot Index, which is 1).

There are 3 elements with a value more than the pivot value (5, 6, 8) and these elements now have an index positions more than the pivotIndex (2, 3, and 4).

There is one element with a value less than or equal to the pivot value (2) and this element now has an index position less than the pivot index (0).

Note that the method's solution of 2, 4, 6, 5, 8 is not the only acceptable solution. Other acceptable solutions would be:

• 2, 4, 5, 6, 8
• 2, 4, 5, 8, 6
• 2, 4, 6, 8, 5
• 2, 4, 8, 6, 5
• 2, 4, 8, 5, 6

Any combination is acceptable, as long as all values to the right of the pivot are greater than the pivot and all values left of the pivot are less than or equal to the pivot.

Textbook - check out section 2.31 and the programming example there.

Files and Tools

Found below is the repl.it environment designed to be used with this assignment. It includes a main file, a ksmallSolution object (.cpp and .hpp).

• You are to alter the ksmallSolution.cpp file.
• You are to alter ONLY the function ksmallPartition where it state "//Your Code Here".

The main file performs four tests. When the ksmallPartition function is correctly working, the test should result in the output similar to:

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:-1

Of course - depending on how you sort your array, your array may contain data in a different order - BUT after ksmallPartition has run on the array, it should return a pivotIndex value. The following must be true:

• The element originally at index position 0 (the pivot value) is now at index position pivotIndex.
• All elements at index positions less than the pivotIndex are less than or equal to the pivot value.
• All elements at index positions greater than the pivotIndex are greater than the pivot value.

ksmallSolution.hpp:

#ifndef KSMALL_SOLUTION_HPP

#define KSMALL_SOLUTION_HPP

void displayArray(int arraySize, int anArray[]);

int ksmallPartition(int startIndex, int endIndex, int anArray[]);

#endif

ksmallSolution.cpp:

#include

#include

#include "ksmallSolution.hpp"

using namespace std;

int ksmallPartition(int startIndex, int endIndex, int anArray[]) {

int pivotIndex = 4;

// YOUR CODE HERE

return pivotIndex;

}

void displayArray(int arraySize, int anArray[]) {

cout << setfill('0');

for(int i=0; i

cout << setw(3) << i << " ";

}

cout << endl << setfill(' ');

for(int i=0; i

cout << setw(3) << anArray[i] << " ";

}

cout << endl;

}

Main.cpp:

#include

#include "ksmallSolution.hpp"

using namespace std;

int main() {

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

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

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

cout << "pivotIndex:" << ksmallPartition(0, testSize-1, test01) << endl;

displayArray(testSize, test01);

cout << endl;

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

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

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

displayArray(testSize, test02);

cout << "pivotIndex:" << ksmallPartition(0, testSize-1, test02) << endl;

displayArray(testSize, test02);

cout << endl;

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

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

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

displayArray(testSize, test03);

cout << "pivotIndex:" << ksmallPartition(0, testSize-1, test03) << endl;

displayArray(testSize, test03);

cout << endl;

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

int test04[] = {};

testSize = 0;

displayArray(testSize, test04);

cout << "pivotIndex:" << ksmallPartition(0, testSize-1, test04) << endl;

displayArray(testSize, test04);

int test05[] = {487, 658, 418, 564, 282, 804, 41, 300, 929, 467, 997, 215, 70, 477, 294, 954, 188, 49, 320, 673, 439, 590, 12, 992, 787, 318, 926, 636, 920, 272, 368, 726, 134, 288, 862, 65, 881, 417, 916, 101, 901, 583, 964, 331, 146, 792, 548, 532, 86, 133, 530, 643, 511, 816, 969, 394, 602, 231, 860, 107, 326, 530, 441, 13, 736, 245, 387, 587, 178, 322, 964, 389, 976, 412, 745, 801, 270, 852, 853, 878};

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

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

}