1

私は宿題をしていて、再帰的にクイックソートを完了しましたが、正しい方法でソートされません。うまく入れ替わっていないようです。

これが私のコードです

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

私が得ている出力：

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

3 に答える 3

3

必ず：

1) size ではなく size-1 の値を使用する

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

2) Pivot は (left+right)/2 ではありませんが、quick_sort_help によって返される値であり、pivottwo は必要ありません:

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) 2 番目の while で j 値 (r) をテストし、ピボット (i 値) を返す前に交換を行います。

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;
 }
于 2012-04-16T19:52:34.550 に答える
0

これを見てください：クイックソートの実装

于 2012-04-16T19:19:25.447 に答える
0 
 while (text[right]>val)
      r--;

そうは思えません。を減少させていますが、テストする条件は決して変化しません (おそらくrに依存する必要があります...)r

また

return l;

呼び出し元の関数はピボットの新しい位置であると想定しているように見えるため、疑わしいように見えますが、古い左です。

もう1つは、閉じた間隔を使用します（なぜすべきではないかを参照してください）。これは、範囲外の文字列（UB）にアクセスしていることを意味します。

于 2012-04-16T19:28:56.447 に答える