QS Algorithm Problem

[coveredinflies]

Hi, I have copied the quicksort algorithm out of my text book, but it isn't working properly and there are no compiler errors so I am struggling to debug. it is partially sorting so I think it must be one of the conditional statements or something not declared how I expect but everything looks okay.

Also I would prefer to use a string rather than a character array in the main program but I can't convert the two since c_str() gives a const so doesn't work and I've tried a few other things.

This is the text book I am using pg 38 <a href "http://download.microsoft.com/download/7/3/7/7374dd3f-be0e-4fc1-ac9b-e3d652194687/C++%20Beginner's%20Guide%20CH05.xps" > link </a>
Sorry I don't like posting chunks of code but I just can't spot the problem.
[spoiler]

char alphabet[]={'s','d','l', 'k','w','o','a','e','x','x','z','y','\0'};
  string name;
  name = "Brian";

  for(int i=0; alphabet[i]; i++)
  {
        cout << alphabet[i] ;
  }
  cout <<endl <<endl;
  quicksort(alphabet,strlen(alphabet));
 // quicksort(name[0],name.length());
   for(int i=0; i<strlen(alphabet); i++)
  {
  
        cout << alphabet[i];
  }
  //cout << name;
  
  cin.ignore();
  cin.get();
  
  return 0;
}

void qs(char *items, int left, int right)
{
    int i,j;
    char x,y;
    
    i=left;
    j=right;
    
    x=items[(left+right)/2];
    
        do
    {
        while(items[i]<x && (i<right)) i++;
        while((x<items[j]) && (j<left)) j--;
        
        if(i<=j)
        {
            y=items[i];
            items[i]=items[j];
            items[j]=y;
            i++; j--;
        }
   }while(i<=j);
   
   if(left < j) qs(items, left, j);
   if(right > i) qs(items, i, right);
   
}

[/spoiler]

EDIT: My attempt to use spoiler tages and hyperlink massively fail lol. I did preview but thought it just musn't work in the preview window

[Salem]

Well you could try reviewing your post before submitting it, to make sure things like code tags and URL links are actually correct.
Rather than just puking into the edit window and pressing submit :(

[Sky Diploma]

Where is the quicksort function mentioned in the code that you have posted?

[coveredinflies]

Where is the quicksort function mentioned in the code that you have posted?

Sorry was trying to cut down on amount I posted which was a bit stupid.

void qs(char *items, int left, int right);

void quicksort(char *items,int len)
{
    qs(items,0,len-1);
};

[Sky Diploma]

Hey.

Assume the following

string s ;
s="Sky";
//Therefore. 

int a = s.size();//Returns 4 
int b = s.length();//Returns 3

Therefore in your code.

i think

void quicksort(char *items,int len)
{
    qs(items,0,len);
};

Should be this using [string var.size () ] instead of length. As you are giving the strings length.

And Secondly the Quick Sort Algorithm wasnt working because over here

void qs(char *items, int left, int right)
{
    int i,j;
    char x,y;
    
    i=left;
    j=right;
    
    x=items[(left+right)/2];
    
        do
    {
        while(items[i]<x && (i<right)) i++;
        while((x<items[j]) && (j<left)) j--;
        
        if(i<=j)
        {
            y=items[i];
            items[i]=items[j];
            items[j]=y;
            i++; j--;
        }
   }while(i<=j);
   
   if(left < j) qs(items, left, j);
   if(right > i) qs(items, i, right);
   
}

On Line 14 it should be (j >left)

[coveredinflies]

Thanks, that was the problem - amazing how many times you can look over something blatantly wrong and not notice the mistake.

Assume the following

string s ;
s="Sky";
//Therefore. 

int a = s.size();//Returns 4 
int b = s.length();//Returns 3

Ah cheers, I knew there was .length() and .size() but had thought they had done the same thing.

Since in the current form I have quicksort taking in a char* type is it possible for it to take in a string? I know you wouldn't normally do it that way but was just wondering if it was possible.

I have changed the function prototype and declaration to accept a string instead i.e

void qs(string items, int left, int right);

void quicksort(string items,int len)
{
    qs(items,0,len-1);
};

but the string just returns unchanged, am I getting C character arrays and C++ strings mixed up again. I thought you didn't need pointers for strings. (I have tried with pointers it crashes).

[Sky Diploma]

Well , There is one thing that you can do.

First make a function that takes in a constant char array as an argument and then you can use

string s

s.c_str(); //I guess we can use this THEN.

I think it will work out, but am not sure.