Expert: Zlatko - 9/29/2010

Question
QUESTION: Hello,

I'm working on an hw assignment, and I'm asked to write a
function template that sorts the given array data (from
main) in ascending order.


The following arrays are already given in the main:

  const int n1 = 5, n2 = 7, n3 = 6;
  int a[n1] = {2, 4, 6, 8, 10};
  float b[n2] = {1.5, 2.5, 3.4, 4.9, 6.7, 7.7};
  char c[n3] = "PROGRAMMING";

And now, my attempt at writing a function template that will
sort the three arrays in ascending order:

template <class T>
void sortarray (T *a, const int n)
{
  T t;
  for (int i = 0; i < n; i++)
     {
         for (int j = 0; j = n-1; j++)
        {
         if (a[i] > a[i+1])
         {
         t = a[i];
         a[i] = a[i+1];
         a[i+1] = t;
         }
        }
     }

I think this sorts numbers ok, but I think you need to use
the strcmp function to sort the char arrays? Did I write
that function template correctly?

Thanks for the help, sorry if the formatting is weird.

Mike

ANSWER: Hello Mike.

You declared your template correctly, but the sort algorithm is not correct. You may think it sorts the data, but that is because your data starts out sorted.

The sort works like this. Every time the inner loop completes, one more item should be in its proper location, at the end of the array. As the sort progresses, the border between the unsorted and sorted parts moves down towards the start of the array.

On every iteration of the outer loop, the inner loop has to go through only the unsorted part of the array, so it goes from 0 to n-i-1. Notice that on every iteration of the outer loop (as i increases), the inner loop gets smaller (n-i), because more of the array is sorted.

In the inner loop, (the comparison and swapping part) the array is indexed with the inner loop variable, j, not i. Think, if accessing with i, the changing of j in the inner loop will not have any affect on the swapping part.

You do not need strcmp, because you are sorting characters in a character array, not C strings in a C string array. If you are sorting C strings, you would need another function, specialized to accept char**, and use strcmp. You could not use the existing template function. However, if you were sorting arrays of C++ strings, you could use the template, because C++ strings can treated like built in primitive types. They can be compared with ">" and they can be assigned with "=".


Finally, here is the corrected program. I would suggest you try to correct your bubble sort before looking at the program. That would increase your skill. I use a little trick to get the array size. You might find it useful.

Remember to test your program on unsorted data. I have not tested it thoroughly.

#include <iostream>
using namespace std;

template <class T>
void sortarray (T *a, const int n)
{
   T t;
   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j < n-i-1; j++)
       {
         if (a[j] > a[j+1])
         {
         t = a[j];
         a[j] = a[j+1];
         a[j+1] = t;
         }
       }
   }
}

template <class T>
void dump(T* a, const int n)
{
   for(int ix = 0; ix < n; ++ix) cout << a[ix] << ' ';
   cout << endl;
}

#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

int main(void)
{
   // you can remove these if using ARRAY_SIZE trick const int n1 = 5, n2 = 6, n3 = 6;
   int a[] = {2, 4, 6, 8, 10};
   float b[] = {1.5, 2.5, 3.4, 4.9, 6.7, 7.7};
   char c[] = "PROGRAMMING";

   dump(a, ARRAY_SIZE(a));
   sortarray(a, ARRAY_SIZE(a));
   dump(a, ARRAY_SIZE(a));
   cout << endl;

   dump(b, ARRAY_SIZE(b));
   sortarray(b, ARRAY_SIZE(b));
   dump(b, ARRAY_SIZE(b));
   cout << endl;
   

/*
For char c[] = "abc" use
ARRAY_SIZE(c)-1 because creating the array with quotes c[] = "abc"
adds a null terminator at the end,
which is counted in the size, but which you
don't really want to move.
*/
   dump(c, ARRAY_SIZE(c)-1);
   sortarray(c, ARRAY_SIZE(c)-1); x
   dump(c, ARRAY_SIZE(c)-1);
}


---------- FOLLOW-UP ----------

QUESTION: Hi,

here is my second attempt. Tried fixing the bubblesort a
bit. So: you compare two successive elements of the array
two at a time in order and if swap is needed to get proper
sorting, we will execute that swap and this cycles on until
we have reached the end of array.


template <class T>
void printarray (T *a, const int n)
{
  for (int i = 0; i < n; i++)
     cout << a[i] << "  ";
  cout << endl;
}

template <class T>
void sortarray (T *a, const int n)
{
  T t;
  for (int i = 0; i < n; i++)
  {
      for (int j = 0; j < n-1; j++)
      {
         if (a[j] > a[j+1])
         {
         t = a[j];
         a[j] = a[j+1];
         a[j+1] = t;
         }
      }
     cout << a[i] << "  ";
  }
}

int main()
{
  const int n1 = 5, n2 = 7, n3 = 8;
  int a[n1] = {4, 8, 10, 6, 1};
  float b[n2] = {1.1, 1.2, 1.4, 1.3, 5.5, 6.6, 7.7};
  char c[n3] = "PROGRAM";

  cout <<"the integer array" << endl;
  printarray(a, n1);
  sortarray(a, n1);
  cout << "\n\n";

  cout <<"the float array" << endl;
  printarray(b,n2);
  sortarray(b, n2);
  cout << "\n\n";

  cout <<"the string is" << endl;
  printarray(c,n3);
  sortarray(c, n3-1);
  cout << endl;
  return 0;
}

Two things:

1. I am little confused why you are using "n-i-1" in the  
loop right before the if statement for the swap. The book I
have just says n-1.

2. The following is the output below. Why is the integer
array not doing what the sorting for the other data type
does? However, if I change the 1 to a 7, we will see the
appropriate sorting. But if I have change the 7 to something
less than 6, the sorting is not doing it right.

the integer array
4  8  10  6  1
4  6  6  8  10

the float array
1.1  1.2  1.4  1.3  5.5  6.6  7.7
1.1  1.2  1.3  1.4  5.5  6.6  7.7

the string is
P  R  O  G  R  A  M
P  G  A  O  P  R  R


ANSWER: Hello Mike.

Your bubble sort works. The reasons you are getting wrong output is because you are trying to print from the sort routine. During the run of the sort, the sorted area is at the end of the array, and the unsorted area is at the beginning. During each iteration of the outer loop the border between the unsorted and sorted areas moves towards the start of the array by one position. In your bubble sort, you are printing a[i], which is still in the unsorted area. For example when i is 0, only the very end of the array is sorted, but you are printing the beginning of the array.

Do the print after the sort is done using your printarray function.

Your book says n-1, and that works, and seems less complicated to the beginner. When you have n-1, your inner loop is always going to the end of the array, so it is going past the border of the unsorted/sorted area. It is redoing all the comparisons in the sorted area. The n-i-1 is a slight improvement to the algorithm, but improvements to bubble sort are pointless since it is a very naive algorithm anyway. It is just to get you thinking about sorting. The next easiest sort to learn is selection sort. It is like bubble sort, but without so much swapping so it is more efficient.

Best regards
Zlatko

---------- FOLLOW-UP ----------

QUESTION: Hi again,

Thank you very much for the help with the bubblesort! Now,
my next thing is that I am going to need to write another
function template to save the (now sorted) array data to a
text file. Here is my attempt below:

template <class T>
void savearray (T *a, const int n)
{
  ofstream myfile("c:\\array.txt", ios::out);
  for(int i = 0; i < n; i++)
  {
     myfile << a[i] << endl;
  }
  myfile.close();
}

Did I write this function template correctly? I'm thinking
now that the sorted arrays should be saved to an array.txt
file, but when if I call the function template three times,
I will only see the text AGMOPRR when I open the text file.

What's a way to have all three arrays saved to the text file
so I see all of them in the same file when I open it? (I
think I probably need to use append to text mode, but that
would require two templates I think and I'm supposed to just
use one)

Thank you once again,
Mike  

Answer
Hi Mike.

If you want to open the file in the template function, and you want to save the previous contents, then you need to open it like this:

ofstream myfile("c:\\array.txt", ios::out | ios::app);

Another suggestion is to pass in the ofstream as a parameter to savearray. That way, the caller of the function can decide when to create a new file and when to append. The template function then becomes like this:

template <class T>
void savearray (T *a, const int n, ofstream& myfile)
{
   for(int i = 0; i < n; i++)
   {
       myfile << a[i] << endl;
   }
}

Notice I removed the file close from the template function. If you are calling from main, just open the file once with
ofstream myfile("c:\\array.txt", ios::out);
and pass it to the savearray function.