A robot has the task of sorting a number of colored pebbles contained in a row o

Question

A robot has the task of sorting a number of colored pebbles contained in a row of buckets. The buckets are arranged in front of the robot and each contains exactly one pebble colored either red. white or blue. The robot is equipped with two arms, on the end of each of which is an eye. Using its eye, the robot can determine color(i), the color of the pebble in the ith bucket, and using its arms the robot can perform the action swap(i, j) to swap the pebbles in buckets i and j. The robot is required to sort the pebbles into three segments - the first containing all red pebbles, the second containing all white pebbles, and the third containing all blue pebbles. Using a char array to simulate the buckets, and chars r, w, and b for the three colors of marbles, write a program to control the robot's sorting of the pebbles. Additional Requirements: (1) note that the robot does not have extra buckets -- accordingly, your program may not use any extra arrays, and it may not use extra space in the array you set up to model the buckets (because there is none!); (2) you may not change the color of any marble: all your program can do to the marbles is to swap them between buckets. Suggestion: first, write down pseudo-code for main in terms of functions; second, set up your input and output functions; third, write a function MoveRedToLeft which moves all r's to the left of the array (without changing the numbers of r's, w's or b's) -auxiliary functions, such as Swap, will be needed; fourth, adapt MoveRedToLeft to write another function, MoveWhiteToLeft which moves all w's to the left of any b in the s/b section created by MoveRedToLeft. Be sure to make good use of reference parameters - perhaps the only global needed is DisplayMax (the maximum number of characters to be displayed on one line), and this should be const.

Explanation / Answer

#include <iostream>
#include <cstdlib>

const int BUCKET_COUNT = 20;

void MoveRedToLeft(char buckets[])
{
int left_index = 0;
//first traverse all the reds in the start, left_index will always point to non-red bucket
while(left_index < BUCKET_COUNT && buckets[left_index] == 'r')
left_index++;
//start picking pebbles from end of array until index crosses the red color index
for(int i = BUCKET_COUNT - 1; i > left_index; i--)
{
if(buckets[i] == 'r')
{
//if red color is found then swap two colors
std::swap(buckets[i], buckets[left_index]);
//increment left_index since it is red now after swap
left_index++;
//now consume any other reds
while(left_index < BUCKET_COUNT && buckets[left_index] == 'r')
left_index++;
}
}
}

void MoveWhiteToLeft(char buckets[])
{
int left_index = 0;
//first traverse all the reds in the start, left_index will always point to non-red bucket
while(left_index < BUCKET_COUNT && buckets[left_index] == 'r')
left_index++;
//now traverse all the whites appearing after reds, left_index will always point to blue bucket
while(left_index < BUCKET_COUNT && buckets[left_index] == 'w')
left_index++;
for(int i = BUCKET_COUNT - 1; i > left_index; i--)
{
if(buckets[i] == 'w')
{
//if white color is found then swap two colors
std::swap(buckets[i], buckets[left_index]);
//increment left_index since it is white now after swap
left_index++;
//now consume any other whites
while(left_index < BUCKET_COUNT && buckets[left_index] == 'w')
left_index++;
}
}
}

void ThreeWaySort(char buckets[])
{
MoveRedToLeft(buckets);
MoveWhiteToLeft(buckets);
}

void PrintBuckets(char buckets[])
{
//prints the buckets
for(int i = 0; i < BUCKET_COUNT; i++)
std::cout << buckets[i] << " ";
std::cout << std::endl;
}

int main()
{
char buckets[BUCKET_COUNT];
//call srand to initialize randomizer so that it generates different patterns in each call
srand(time(NULL));
//fill the buckets with colors (r,b,w) based on random values
for(int i = 0; i < BUCKET_COUNT; i++)
{
int color = rand() % 3;
if(color == 0) buckets[i] = 'r';
else if(color == 1) buckets[i] = 'w';
else buckets[i] = 'b';
  
}
PrintBuckets(buckets);
ThreeWaySort(buckets);
PrintBuckets(buckets);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.