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

Did you try running it through a debugger? That can help a lot. Another good technique you can use is to test the partition function (quick_sort_help) in isolation first to see if it is correct. — R. Martinho Fernandes
– R. Martinho Fernandes, Commented Apr 16, 2012 at 19:24

gliderkite · Accepted Answer · 2012-04-16 19:52:34Z

3

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;
 }

answered Apr 16, 2012 at 19:52

gliderkite

8,9287 gold badges49 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

mydreamadsl Over a year ago

sorry, you are right, it wasn't rebuilt. Thank you very much for the clear explanation and code support

Erwald · Accepted Answer · 2012-04-16 19:19:25Z

0

Take a look at this : Quicksort implementation

answered Apr 16, 2012 at 19:19

Erwald

2,2162 gold badges15 silver badges20 bronze badges

2 Comments

Daniel Over a year ago

If hes doing homework, just giving a solution is not the way to help.

Erwald Over a year ago

Since he was pretty close to the solution, I though i'd be helpful for him to simply search for the solution to his problem and also look at tdifferent type of implementation. This is a great way to learn as well.

Community · Accepted Answer · 2017-05-23 12:04:31Z

0

 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).

edited May 23, 2017 at 12:04

CommunityBot

11 silver badge

answered Apr 16, 2012 at 19:28

jpalecek

47.9k7 gold badges105 silver badges147 bronze badges

2 Comments

mydreamadsl Over a year ago

I am comparing to pivot, right? so val is my pivot, if right>pivot, I am dec right?

jpalecek Over a year ago

@mydreamadsl: Maybe (you used the word "right" three times in your post, and I'm not quite sure what you meant). Anyway, think about what the posted code does, what you think it should do, what I've written in the parentheses. BTW your code does something different on ideone: ideone.com/CMqJw

Collectives™ on Stack Overflow

c++ quicksort sort string text

3 Answers 3

1 Comment

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related