Please help.

[copyright_1978]

I have to hand in a piece of programming work soon, but I can't do it. I have asked other people to help me with it, but nobody seems to be able to sort this program out because it's too difficult, actually I've asked everyone in the computer science department to help me but they say it's too difficult, then I asked some people who were doing their masters degree but they couldn't do it either. God I'm in trouble.

The piece of programming code is this:


#include
#include
int bubble_sort (int array [], int arraySize);
void swap (int &v1, int &v2);
void fill_array (int array [], int arraySize);
void print_array (int array [], int arraySize);

int main()
{
const int SIZE = 4;
int numbers[SIZE];
int count;

fill_array (numbers, SIZE);
cout << "Initially: ";
print_array (numbers, SIZE);
count = bubble_sort (numbers, SIZE);
cout << "Sorted: ";
print_array (numbers, SIZE);
cout << "Number of comparisons was " << count << endl;
getch();
return 0;
}

// Sort an array of integers using (an inefficient) variant of
// bubblesort. It returns the number of comparisons needed to
// do the sort.
int bubble_sort (int array[], int arraySize)
{
int comp = 0;

for (int pass = 0; pass <= arraySize - 2; pass++)
{
for(int counter = 0; counter <= arraySize - 2; counter++)
{
comp = comp + 1; // we are about to do a comparison
if (array[counter] > array[counter+1])
swap (array[counter], array[counter+1]);
}
}

return comp;
}

// Exchange a given pair of values in an array
void swap (int &v1, int &v2) // call by reference
{
int temp;

temp = v1;
v1 = v2;
v2 = temp;
}

// Fill an array from the keyboard
void fill_array (int array[], int arraySize)
{
for(int counter = 0; counter <= arraySize - 1; counter++)
{
cout << "Number " << counter << ": ";
cin >> array[counter];
}
}

// Print the contents of an array to the screen
void print_array (int array [], int arraySize)
{
for(int counter= 0; counter <= arraySize - 1; counter++)
{
cout << array[counter] << "\t";
}
cout << endl;
}




Now what I have to do is modify the program to read in a series of FOUR 3 letter words and then print them out in sorted order. The program should keep a count of the number of string comparisons performed and never take more than 6 comparisons to do the sort. It currently does 9 comparisons, so I need to take it down from 9 to 6. It should not use an index array but a multidimentional array.

So as an example:

If the user typed the following words when requested:

cat
ant
tap
tan

the program should print out:

Initially: cat ant tap tan

Sorted: ant cat tan tap

Number of comparisons was: 6


So far the program only sorts out numbers, so I need to modify it to read in strings using multidimentional arrays.

[mosquito]

The way I see it, you only have to change the int arrays to char* arrays. I'll have a look at it later on today. I'll post the code if I get it working.

[earlboy]

All you got to do is to change your array to type array of char. Then use the string functions in stdlib for comparison.

Heres a modified version of your code to work on strings.



#include
#include

const int len = 5;
typedef char String[ len ];

int bubble_sort (String array[], int arraySize);
void swap (char* v1 , char * v2);
void fill_array (String array[], int arraySize);
void print_array (String array[], int arraySize);

int main()
{
const int SIZE = 4;
String numbers[SIZE];
int count;
char ch;

fill_array (numbers, SIZE);
cout << "Initially: ";
print_array (numbers, SIZE);
count = bubble_sort (numbers, SIZE);
cout << "Sorted: ";
print_array (numbers, SIZE);
cout << "Number of comparisons was " << count << endl;
cin >> ch;
return 0;
}

// Sort an array of integers using (an inefficient) variant of
// bubblesort. It returns the number of comparisons needed to
// do the sort.
int bubble_sort (String array[], int arraySize)
{
int comp = 0;

for (int pass = 0; pass <= arraySize - 2; pass++)
{
for(int counter = 0; counter <= arraySize - 2; counter++)
{
comp = comp + 1; // we are about to do a comparison
if (strcmp ( array[counter], array[counter+1] ) > 0 )
swap (array[counter], array[counter+1]);
}
}

return comp;
}

// Exchange a given pair of values in an array
void swap ( String v1, char* v2) // call by reference
{
char temp[ len ];

strcpy( temp, v1 );
strcpy(v1, v2 );
strcpy( v2, temp );
}

// Fill an array from the keyboard
void fill_array (String array[], int arraySize)
{
for(int counter = 0; counter <= arraySize - 1; counter++)
{
cout << "Number " << counter << ": ";
cin >> array[counter];
}
}

// Print the contents of an array to the screen
void print_array (String array[], int arraySize)
{
for(int counter= 0; counter <= arraySize - 1; counter++)
{
cout << array[counter] << "\t";
}
cout << endl;
}

Note: This code does not check for input length. If you enter more than 4 characters per input then this program will crash. You can increase the lenth of the string though. It's all up to you.

Hope this helps, and cheers.

My output :

Number 0: can
Number 1: ban
Number 2: zen
Number 3: pen
Initially: can ban zen pen
Sorted: ban can pen zen
Number of comparisons was 9

[copyright_1978]

Thanks earlboy and mosquito, how on earth did you guys work it out? It was so complex for me, it just gave me a headache that I thought it was a trick code made to nacker my brains.

I'm so happy Is there anyway to get the comparisons down to 6?

Thanks guys, you lot know more than those who did their masters Degree in computer science. You wanna switch brains? :P

[earlboy]

Glad to help.

It's possible but you need to change your sorting algorithm.
There are a lot of better sorting algorithm out there.
Sorry, but I can't remember any one of them right now. There should be books available regarding sorting or you can try to find one on the net.

cheers.

[Paul Victorey]

Six compares is the worst case scenario for a binary search tree with 4 members added.

In fact, many sorts (like the insertion sort) should not give more than 6 compares for a 4 member series. However, insertion sort has the disadvantage of needing to shift objects in an array.

BST is the best (or better, a red/green tree which is a specialized version of a BST) though sometimes (especially with red/green trees) it's a pain to code. If the input order of the words was purely random, on average a BST and a red/green would perform equally (with red/green taking a bit longer for insertions), but if the input were already sorted, or if local regions of inputs were pseudo-sorted (which is almost guaranteed in real life situations), a red/green tree would do much better.