Re: [Dev-C++] Help with functions

[Jason H. <jas...@bt...>]

I went ahead and created a faster algorithm anyway, it's the sortv2()
function a the bottom.
Note that the e-mail line length is cropped, so some of the comments will
need to be straightened out before it will compile again.

Jason.


#include <cstdio>   // all around useful header
#include <cstdlib>  // the rand() fuction is in this header
#include <ctime>    // for time()
#include <iostream> // for cout and cin
#include <cstring>  // for strcpy()

void sortv2(char str[]);

int main(int argc, char *argv[])
{
    using namespace std; // allow implicit use of std namespace

    // Random number generation
    int num;
    srand((unsigned) time(NULL)); // give the rand() function a seed
        // I use the time because it's not likely to be the same each time
        // the program is run. There may be a better way of doing this?

    for(int i = 0; i < 10; ++i)
    {
        num = (rand() % 99) + 1; // A random number between 1 and 100.
        cout << "A random number " << i + 1 << ": " << num << endl;
    }

    cout << endl;

    // Getting a character out of a string
    char a_string[] = "This is a string of text. Hello World!";
    cout << a_string << endl << "Enter a number between 1 and "
         << sizeof(a_string) - 1 << ": ";
            // the string is null terminated, so sizeof reports one bigger
            // than text
    cin >> num;
    cout << "The character at that number is: " << a_string[num-1] << endl;
        // You don't need a function to get a single character out of a
string
        // just use array access. This applies to std::string too.
        // don't forget... arrays are indexed from 0

    cout << endl;

    // Sorting a string in sequence
    char str[80], str2[80]; // up to 80 chars
    cout << "Enter a string to be sorted in sequence (80 char MAX!)"
         << endl << ": ";
    gets(str); // get a string from user (part of <cstdio>)
    strcpy(str2, str); // make a copy

    // Begin sort (brute force)
    int i = 0, j = 0, k = 0; // index's
    char sorted[80], c;
    while(str[i])
    {
        while(str[i] == ' ') ++i; // skip spaces
        if(!str[i]) break; // avoid end of line
        j = i;
        c = str[i];
        while(str[j])
        {
            if(str[j] == c)
            {
                sorted[k] = c;
                str[j] = ' '; // don't get the same char twice
                ++k; // increment sorted index
            }
            ++j; // increment search index
        }
        ++i; // increment input index
    }
    sorted[k] = 0; // don't forget to null terminate string!
    cout << "Sorted string is: " << sorted << endl;
        // NB: there may be a better way to do it, but this works and you
        // don't really need anything faster for just 80 chars.
        // I leave it to you to perform size and type checking anywhere

    sortv2(str2); // I made a faster one anyway :)
    cout << "Sorted by V2 is : " << str2 << endl;

    system("PAUSE");
    return 0;
}


// another sort that should be faster (in theory)
// for one it uses pointer arithmatic mainly which is faster
// than array access, secondly it employs two single passes
// of the string, rather than the multiple in the other version
// one thing you could note is that if you give this function
// an already sorted string it will take longer than the v1 sort
// method.
void sortv2(char str[]) // pass it the string to be sorted
{
    char ts[80], *pstr, *pts;
    int count[128], *pc;
    pc = count;
    for(int i = 0; i < 128; ++i) *pc++ = 0; // clear all of count to zero
    pstr = str;
    while(*pstr) ++count[*pstr++]; // count instances of each character
    pstr = str;
    pts = ts;
    while(*pstr)
    {
        while(*pstr == ' ') ++pstr; // ignore spaces
        if(!*pstr) break;         // stop at EOL
        for(; count[*pstr]; --count[*pstr])
            *pts++ = *pstr;
        ++pstr;
    }
    *pts = 0; // NULL terminate
    strcpy(str, ts); // copy it over original string

}