sorting char* arrays

Question

Hi! I have a datastructure

struct record {
    char cont[bufferSize];
    record *next;
};

When I add new records to this structure, I want them to be sorted alphabetically. I made this function, that adds record in the right place (by alphabet) in the linked list:

record *start=NULL, *p, *x;

void recAdd(char*temp) {
        p = new record;
        temp[strlen(temp)] = '\0';
        for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j];
        if (start==NULL) start=p;
        else {
            x=start;
            int c=0;
            while (recComp(x->cont,p->cont) <= 0 && x->next != NULL) {
                    x=x->next;
                    c++;
            }
            if (c == 0) {
                p->next=start;
                start=p;
            }
            else {
                x=start;
                for (int i=0;i<c;i++) x=x->next;
                p->next=x->next;
                x->next=p;
            }
        }
        for (int j=0;j<bufferSize;j++) temp[j] = NULL;
    };

But somehow it doesn't sort things right. What is wrong with my function?

Answer 1

Perhaps I'm not answering your question, but why aren't you using the STL? It will do the sorting for you; you shouldn't have to write sorting routines like this these days.

Answer 2

Some tips:

• use strcmp to compare strings
• prefer using pointers to char inside your struct. This allows you to blindly assign them without copying and it won't waste space inside your struct
• if you really need to copy them use strdup to allocate new strings
• keep track of two current elements instead that just one, this will avoid counting how many you got so far and go through the list twice when you found right position

Answer 3

You can make you life here a lot easier if you implement a simple insert sort using STL vector (vector has a member 'insert').

that code will look much cleaner too :)

lookup cplusplus.com for examples there of, you will find it helpful.

Answer 4

Your code is a mess. There are a number of problems both semantic and logical, but fundamentaly the logic that decides where to insert new nodes is the most flawed. Change it to this (note my new code in the else block):

void recAdd(const char*t) {
        char temp[bufferSize];
        strcpy(temp, t);
        p = new record;
        temp[strlen(temp)] = '\0';
        for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j];
        if (start==NULL) { start=p; start->next = 0; }
        else {
            record* x = start;
            record* prev = 0;
            while( x && recComp(x->cont, p->cont) <= 0 )
            {
                prev = x;
                x = x->next;
            }

            // p is a new node. p, x and prev are arranged thusly:
            // prev -> p -> x
            // if prev is null, p is a new head
            // if x is null, p is a new tail
            // otherwise, p is inserted between prev and x

            if( !prev )
            {
                p->next = start;
                start = p;
            }
            else if( !x )   
            // note this block and the next one could be combined.  
            // done this way for clarity.
            {
                prev->next = p;
                p->next = 0;
            }
            else
            {
                p->next = x;
                prev->next = p;
            }
        }
        for (int j=0;j<bufferSize;j++) temp[j] = NULL;
    };

BUT the fact that you had enough difficulty writing this code that you would ask SO for help in fixing it illustrates an important point: the best code is code that you never have to write. You have written both a linked list type structure (bare bones tho it may be) and a sorting algorithm. Both are flawed, and both have working, tested and efficient versions available as part of the standard C++ libraries. You should be using them. Use strings instead of char*s. Use vectors instead of your linked list. Use sort instead of your hand rolled sorting algorithm. Taken together, all your code can be replaced by this:

vector<string> records;

// this for block just populates the vector with random strings
for( int i = 0; i < 10; ++i )
{
    string s;
    for( int j = 0, jx = 3+(rand()/(RAND_MAX/10)); j < jx; ++j )
        s += 'A'-1+(rand()/(RAND_MAX/26));
    cout << s << endl;
    records.push_back(s);
}

sort(records.begin(), records.end());
copy( records.begin(), records.end(), ostream_iterator<string>(cout, " "));

Why hand-roll a bunch of stuff and expose yourself to countless defects when you can use tools that already work and do what you want?

Answer 5

As others have already suggested, the STL makes life a lot easier. It seems all you need is a sorted container of strings:

#include <iostream>
#include <set>
#include <string>

int main()
{
    std::set<std::string> words;
    words.insert("hello");
    words.insert("beautiful");
    words.insert("world");

    for (std::set<std::string>::const_iterator it = words.begin(); it != words.end(); ++it)
    {
        std::cout << *it << std::endl;
    }
}