Hi all,

Sorry if its a newbie post, but I'm currently trying to finish a program that sorts a binary search tree using the quicksort method. It seems like it should work, but whenever I run it, the program stops at a certain part in the program and encounters a bug or some sort of error. I've located where I think this bug is coming from, but haven't found a way to fix it.

Any help would be greatly appreciated!


Here is the code for the current state of the program, w/ some comments:

/* File: treeQSort.c
 * This program uses the quicksort procedure to sort a given 
 * binary search tree with the help of arrays.
 */
  
#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "strlib.h"
#define size 8

typedef struct nodeT{
    string key;
    struct nodeT *left, *right;
} nodeT,*treeT;

string grtr[size];
string arr[size];

void InsertNode(treeT *tptr,string key)  // Inserts nodes into the tree
{
    treeT t;
    int sign;
    t=*tptr;
    
    if(t==NULL){
        t=New(treeT);
        t->key = CopyString(key);
        t->left = t->right = NULL;
        *tptr = t;
        return;
    }
    
    sign = StringCompare(key,t->key);
    if(sign==0)return;
    if(sign<0){
        InsertNode(&t->left,key);
    }
    else {
        InsertNode(&t->right,key);
    }
}

void addnodes(treeT t, int i)   // adds the nodes within the tree to arr
{
    if(t!=NULL){
        addnodes(t->left, i);
        arr[i]=t->key;
        i=i+1;
        addnodes(t->right, i);
    }
}

treeT putnodes(treeT t, int i)  // transfers the sorted list of nodes to the tree
{
    if(t!=NULL){
        putnodes(t->left, i);
        t->key=arr[i];
        i++;
        putnodes(t->right, i);
    }
}

void DisplayTree(treeT t)   // Displays the tree
{
    if(t!=NULL){
        DisplayTree(t->left);
        printf("%s\n",t->key);
        DisplayTree(t->right);
    }
}

void quicksort(int l, int r)   // Sorts the nodes using the quicksort procedure
{
       int pos, i, n=0;
       string pivot;
       pos=l;
       pivot=arr[pos];
       arr[pos]=arr[l];
       for(i=l+1;i<=r;i++)
       {
               if(StringLength(arr[i])>StringLength(pivot))
               {
                       grtr[n]=arr[i];
                       n++;
               }
               if(StringLength(arr[i])<=StringLength(pivot))
               {
                       arr[pos]=arr[i];
                       pos++;
               }
               // PROGRAM SEEMS TO BE ENCOUNTERING A BUG DURING THIS LOOP - TRIED TO FIND A WAY TO FIX IT,
               // BUT I COULDN'T STOP THE BUG/ERROR FROM OCCURING
               
       }
       for(i=0;grtr[i]!=0;i++)
       {
               arr[(r+1)-n+i]=grtr[i];
       }
       for(i=0;i<size;i++)
       {
               grtr[i]=NULL;
       }
       arr[pos]=pivot;
       if(pos-1>=0)
       {
               quicksort(0, pos-1);
       }
       if(r-pos>1)
       {
               quicksort(pos+1, r);
       }
}


main()
{
      int i, l=0, r=size-1;
      treeT T=NULL;
      for(i=0;i<size;i++)
      {
               grtr[i]=NULL;
      }
      printf("This program uses the quicksort procedure to sort a binary search tree\n");
      printf("of strings, sorting by the length of each string node.\n");
      InsertNode(&T,"ads");
      InsertNode(&T->left,"agwrehse");
      InsertNode(&T->left->right, "a");
      InsertNode(&T->left->left, "aassadf");
      InsertNode(&T->left->right->left, "dddeeeeeeeeee");
      InsertNode(&T->right,"ffffffffffds");
      InsertNode(&T->right->left, "sa");
      InsertNode(&T->right->right,"gasdse");
      printf("Here is the tree with unsorted nodes:\n\n");
      DisplayTree(T);
      i=0;
      addnodes(T, i);
      quicksort(l, r);
      i=0;
      T=putnodes(T, i);
      printf("\n\nHere is the tree with its nodes sorted:\n\n");
      DisplayTree(T);
      getchar();
}

oh and btw: the program uses strings, and is supposed to be sorted by the length of the strings.

Sorry about the long code, and thanks in advance!

>Can you explain what is it: binary search tree sorted with quicksort method???
It's a poorly worded question. Clearly a binary search tree is already sorted by nature, so quicksorting the tree itself is nonsensical. By the looks of the code, the OP wants to copy the contents of the tree to an array, then quicksort the array using different comparison criteria.

The question boils down to: "What's wrong with my quicksort algorithm?"

genlib.h ... simpio.h ... strlib.h ... WTF is this???

whoever told you to use this crap is setting you up for FAIL. this is so non-standard, i dont even know what the hell it is. all i know is that it's caused your code to be so far beyond broken there is no way to ever get it to work on any standard C compiler.

throw these libraries out of your program and any function calls that rely on it, then rewrite your program to work with standard C libraries.

and if someone tells you to use this garbage again, kick them in both shins really hard.

Comments
this made me laugh, respect.
Whatever they are, they make it impossible for us to replicate the problem.
you fail.
don't worry, I for one, appreciate your dumbassery
You fail. Go smoke a dooby or something and chill out.

jephthah> genlib.h ... simpio.h ... strlib.h ... WTF is this???

User defined header files. Just because there are not part of the standard C library doesn't mean they are not C standard compliant

Therefore,
jephthah> whoever told you to use this crap is setting you up for FAIL. this is so non-standard, i dont even know what the hell it is. all i know is that it's caused your code to be so far beyond broken there is no way to ever get it to work on any standard C compiler.

...it is out of place and erroneous.

okay, so im a jackass... yes that's been pretty well-established, and i've not made any efforts to dissuade anyone of such an opinion.

but these library headers aren't user defined. i mean that they're not unique. because apparently they're out there, somewhere, as optional features with some compiler. lets see one of you compile his code and debug it.

which is what i was going to do until i realized it was going to be an entire project in and of itself. i mean, i could do it if i had some motivation to do so, but i have other things to do besides hunt down obscure libraries, or rewrite someone elses code to use standard libraries, and I just dont have the inclination to debug 150 lines of code for someone by eyesight.

perhaps one of you fans of non-standard libraries can cipher it out.

.

jephthah> okay, so im a jackass... yes that's been pretty well-established, and i've not made any efforts to dissuade anyone of such an opinion.

Don't let it get you! We all put our foot in our mouth from time to time;
the important part to remember is not to chew while is inside. :)

>because apparently they're out there, somewhere, as optional features with some compiler.
I seriously doubt that. More likely they're teacher-written libraries to protect beginners from the nuances of C during a programming course. simpio.h is suggestive of this, as it indicates a "simplified" I/O library.

>lets see one of you compile his code and debug it.
Done. It took less than five minutes to write a dummy library such that the code can be debugged without any changes to the driver code.

>which is what i was going to do until i realized it
>was going to be an entire project in and of itself.
Really? The more you talk, the more I doubt your programming abilities. Are you honestly saying that replacing the includes with the following stub code is too much for you?

/*
  Begin "non-standard" header implementation
*/
#include <stdlib.h>
#include <string.h>

typedef char *string;

#define New(T) malloc ( sizeof ( T ) )

string CopyString ( string src )
{
    string dst = malloc ( strlen ( src ) + 1 );
    return strcpy ( dst, src );
}

int StringCompare ( string a, string b )
{
    return strcmp ( a, b );
}

size_t StringLength ( string s )
{
    return strlen ( s );
}
/*
  End "non-standard" header implementation
*/

If you flame people and you're right, you'll get a lot more respect than if your flame is so off the mark that it's embarrassing to your peers.

For the OP: addnodes is incorrect in that your value of i is erratic whereas what you want is a value that steadily increases. The result is that after addnodes finishes, arr isn't properly populated. If string is a typedef as in my example, that means you're trying to work with null pointers (ie. access violations will ensue). Note that putnodes suffers the same problem, which means you're totally shredding the contents of the tree. The following code compiles cleanly on one of my compilers and runs correctly:

/* File: treeQSort.c
 * This program uses the quicksort procedure to sort a given 
 * binary search tree with the help of arrays.
 */
  
#include <stdio.h>
/*
  Begin "non-standard" header implementation
*/
#include <stdlib.h>
#include <string.h>

typedef char *string;

#define New(T) malloc ( sizeof ( T ) )

string CopyString ( string src )
{
    string dst = malloc ( strlen ( src ) + 1 );
    return strcpy ( dst, src );
}

int StringCompare ( string a, string b )
{
    return strcmp ( a, b );
}

size_t StringLength ( string s )
{
    return strlen ( s );
}
/*
  End "non-standard" header implementation
*/
#define size 8

typedef struct nodeT{
    string key;
    struct nodeT *left, *right;
} nodeT,*treeT;

string grtr[size];
string arr[size];

void InsertNode(treeT *tptr,string key)  // Inserts nodes into the tree
{
    treeT t;
    int sign;
    t=*tptr;
    
    if(t==NULL){
        t=New(treeT);
        t->key = CopyString(key);
        t->left = t->right = NULL;
        *tptr = t;
        return;
    }
    
    sign = StringCompare(key,t->key);
    if(sign==0)return;
    if(sign<0){
        InsertNode(&t->left,key);
    }
    else {
        InsertNode(&t->right,key);
    }
}

static int n = 0;

void addnodes(treeT t)   // adds the nodes within the tree to arr
{
    if(t!=NULL){
        addnodes(t->left);
        arr[n++]=t->key;
        addnodes(t->right);
    }
}

void putnodes(treeT t)  // transfers the sorted list of nodes to the tree
{
    if(t!=NULL){
        putnodes(t->left);
        t->key=arr[n++];
        putnodes(t->right);
    }
}

void DisplayTree(treeT t)   // Displays the tree
{
    if(t!=NULL){
        DisplayTree(t->left);
        printf("%s\n",t->key);
        DisplayTree(t->right);
    }
}

void quicksort(int l, int r)   // Sorts the nodes using the quicksort procedure
{
       int pos, i, n=0;
       string pivot;
       pos=l;
       pivot=arr[pos];
       arr[pos]=arr[l];
       for(i=l+1;i<=r;i++)
       {
               if(StringLength(arr[i])>StringLength(pivot))
               {
                       grtr[n]=arr[i];
                       n++;
               }
               if(StringLength(arr[i])<=StringLength(pivot))
               {
                       arr[pos]=arr[i];
                       pos++;
               }
               // PROGRAM SEEMS TO BE ENCOUNTERING A BUG DURING THIS LOOP - TRIED TO FIND A WAY TO FIX IT,
               // BUT I COULDN'T STOP THE BUG/ERROR FROM OCCURING
               
       }
       for(i=0;grtr[i]!=0;i++)
       {
               arr[(r+1)-n+i]=grtr[i];
       }
       for(i=0;i<size;i++)
       {
               grtr[i]=NULL;
       }
       arr[pos]=pivot;
       if(pos-1>=0)
       {
               quicksort(0, pos-1);
       }
       if(r-pos>1)
       {
               quicksort(pos+1, r);
       }
}


int main()
{
      int i, l=0, r=size-1;
      treeT T=NULL;
      for(i=0;i<size;i++)
      {
               grtr[i]=NULL;
      }
      printf("This program uses the quicksort procedure to sort a binary search tree\n");
      printf("of strings, sorting by the length of each string node.\n");
      InsertNode(&T,"ads");
      InsertNode(&T->left,"agwrehse");
      InsertNode(&T->left->right, "a");
      InsertNode(&T->left->left, "aassadf");
      InsertNode(&T->left->right->left, "dddeeeeeeeeee");
      InsertNode(&T->right,"ffffffffffds");
      InsertNode(&T->right->left, "sa");
      InsertNode(&T->right->right,"gasdse");
      printf("Here is the tree with unsorted nodes:\n\n");
      DisplayTree(T);
      i=0;
      n = 0;
      addnodes(T);
      quicksort(l, r);
      i=0;
      n = 0;
      putnodes(T);
      printf("\n\nHere is the tree with its nodes sorted:\n\n");
      DisplayTree(T);
      return 0;
}

The fix for addnodes and putnodes is awkward and ugly, but I'm somewhat pressed for time at the moment.

Really? The more you talk, the more I doubt your programming abilities

well, i've got to say that it's easier to talk than to do.

admittedly, i didn't really look at the code. i got to the unknown libraries, and just stopped right there. i'm so tired of all the conio.h and whatnot, i saw three unknown libraries, i just snapped.

but good work though. I have no problem admitting you're a better -- and far more patient -- programmer and teacher than i am.

I'll also admit that this incident has taught me to slow down and take a breath before flying off about 'non-standard' libraries. i can see that they are quite trivial functions.

.

This article has been dead for over six months. Start a new discussion instead.