c++ quicksort sort string text

Question

I am doing my homework, and completed quicksort recursive, however it doesn't sort in a correct way. Seems to be it doesn't swap correctly.

Here is my code

#include<iostream>
#include<ctime>
#include<string>
using namespace std;


int quick_sort_help(string &text,int left, int right, int pivot){


  char val = text[pivot];
  char temp;

  //swap
 // temp =text[pivot];
  //text[pivot]= text[right];
  //text[right]=temp;

  //swap(&text[left],&text[right]);

  int l = left;
  int r = right;

  int i=left;
  while (i<=r)
  {
      while (text[i]<val)
          i++;
      while (text[right]>val)
          r--;
      if (i<=r)
      {
          temp=text[i];
          text[i]=text[r];
          text[r]=temp;
          i++;
          r--;
      }
  }


  return l;
     }


void quicksort(string &text,int left, int right){

      if (left < right){

          int pivot=(left+right)/2;
          int pivottwo = quick_sort_help(text, left, right, pivot);
          quicksort(text, left, pivottwo - 1);
          quicksort(text, pivottwo + 1, right);
          }
 }  
void quick_sort(string &text,int size){
              quicksort(text,0,size);}


int main()
{

    string text="this is a test string text,.,!";
    int size = text.length();
    float t1, t2;
    t1 = clock();
    quick_sort(text,size);

    t2=clock();
    cout<<"quicksort Sort: "<<(t2-t1)/CLK_TCK*1000<<" msec\n"; 
    cout<<text<<endl;


    system("pause");
    return 0;
}

the output I am getting:

hi  a e  e,g.nii,r!tssssxttttt

Answer 1

 while (text[right]>val)
      r--;

That doesn't seem likely. You're decrementing r, but the condition you test never changes (should depend on r, probably...)

Also

return l;

looks suspicious, since the calling function seem to expect it to be the new position of the pivot, whereas it is the old left.

Another one, you use closed intervals (see why you shouldn't), which means you're accessing the string out-of bounds (which is UB).

Answer 2

You have to:

1) Don't use size but size-1 value

void quick_sort(string &text,int size){
          quicksort(text,0,size-1);}

2) Pivot is not (left+right)/2 but it's the value returned by quick_sort_help, and pivottwo is not necessary:

void quicksort(string &text,int left, int right)
{
  if (left < right)
  {
      int pivot = quick_sort_help(text, left, right);
      quicksort(text, left, pivot - 1);
      quicksort(text, pivot + 1, right);
  }
}

3) Test my j value (your r) in the second while and make the exchange before returning the pivot (the i value):

int quick_sort_help(string &text,int left, int right)
{
  char val = text[right];
  char temp;

  int j = right;
  int i = left - 1;

  while (true)
  {
  while (text[++i] < val);

  while (text[--j] > val) {
      if(j == left)
          break;
  }

  if(i >= j)
      break;

  temp=text[i];
  text[i]=text[j];
  text[j]=temp;
 }

 temp=text[i];
 text[i]=text[right];
 text[right]=temp;

 return i;
 }

Answer 3

Take a look at this : Quicksort implementation