There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.
switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.
These functions can be used only N times.
please help me,I tried to reach a proper solution but with
no success.
One crude solution:
Assumptions:
1) Not a trick question ... 'switch' is a reserved word in C, so your
function switch(i, j) is invalid. Let's assume you meant Switch(i, j).
2) _EACH_ function can be used N times ... makes sense, otherwise you
are required to use all N function calls on color to obtain the color of
the N stones and thus have no more calls left for Switch(i,j) ...
Below is the code ... again crude and not very efficient, but it fits
your requirements. Switch(i,j) and Color(i) are each called exactly N
times. A more efficient algorithm would call Switch(i, j) a _maximum_ of N
times. For example, if all the stones are one color, switch is never
needed.
Sincerely,
TJ Walls
Ph.D. Candidate - Stony Brook University
----------------- <snip> -------------------------
#include <stdio.h>
#include <stdlib.h>
#define N 2000
void Switch(char *list, int pos1, int pos2) {
char c;
c = list[pos1];
list[pos1] = list[pos2];
list[pos2] = c;
}
char Color(char *list, int pos) {
return list[pos];
}
int Sort(char *list) {
int i;
int last_r = 0, last_g = N-1;
int calls = 1;
for (i = 0; i < last_g; i++) {
switch (Color(list, i)) {
case 'r':
if (i != last_r++) {
Switch(list, last_r-1, i);
}
break;
case 'b': Switch(list, i, i); break;
case 'g':
if (i != last_g--) {
Switch(list, last_g+1, i--);
}
break;
default: fprintf(stderr, "Invalid Color\n"); exit(7); break;
}
calls++;
}
return calls;
}
int main(void) {
char *list;
int i, tmp;
int calls;
if ((list = malloc(N*sizeof(char))) == NULL) {
fprintf(stderr, "Out of memory\n");
exit(5);
}
srand(1);
fprintf(stdout, "Original List:\n");
for (i = 0; i < N; i++) {
tmp = 1+(int)(3.0*rand()/(RAND_MAX+1.0));
switch (tmp) {
case 1: list
= 'r'; break;
case 2: list = 'b'; break;
case 3: list = 'g'; break;
default: fprintf(stderr, "Invalid Color\n"); exit(6); break;
}
fprintf(stdout, "%c", list);
}
calls = Sort(list);
fprintf(stdout, "\nSorted List:\n");
for (i = 0; i < N; i++) {
fprintf(stdout, "%c", list);
}
fprintf(stdout, "\nCalls: %d\n", calls);
return 0;
}
----------------- <snip> -------------------------