c++ - 文字列配列を使用した C++ クイックソート

Question

クイックソート コードに問題があります。理由はわかりませんが、並びません。

マイプログラム

#include <iostream>
#include <string>

using namespace std;

class Student
{
    public:
    string studentArray[100][3];
    string getName();
    string getSurname();
    string getID();
    void setName(string stdName);
    void setSurname(string stdSurname);
    void setID(string stdIDs);
    private:
    string name;
    string surname;
    string ID;
};

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

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

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

int main()
{
    Student myStudent;
    string name;
    string surname;
    string id;
    int choice;
    int temp=0;
    char ans1;
    do{
        cout<<"What do you want to search with"<<endl;
        cout<<"1-)For adding a Student:"<<endl;
        cout<<"2-)Search with name:"<<endl;
        cout<<"3-)Search with surname:"<<endl;
        cout<<"4-)Search with ID (binary!):"<<endl;
        cout<<"5-)Show List!"<<endl;
        cin>>choice;

        switch (choice)
        {
            case 1:
            {
                char ans;
                do
                {
                    cout<<"Please enter Student's name: ";
                    cin>>name;
                    cout<<"Please enter Student's surname: ";
                    cin>>surname;
                    cout<<"Please enter Student's ID: ";
                    cin>>id;
                    myStudent.setName(name);
                    myStudent.setSurname(surname);
                    myStudent.setID(id);

                    myStudent.studentArray[temp][0]=myStudent.getID();
                    myStudent.studentArray[temp][1]=myStudent.getName();
                    myStudent.studentArray[temp][2]=myStudent.getSurname();
                    cout<<"Want to add new Student? (y/Y)";
                    cin>>ans;
                    temp++;
                }while(ans=='y'||ans=='Y');
                break;
            }
            case 2:
            {
                cout<<"Enter the student name:";
                cin>>name;
                for(int i=0;i<temp;i++)
                {
                    if(myStudent.studentArray[i][1]==name)
                    {
                       cout<<myStudent.studentArray[i][0] + " " + myStudent.studentArray[i][1] + " " + myStudent.studentArray[i][2]<<endl;
                    }
                }
                break;
            }
            case 3:
            {
                cout<<"Enter the student surname:";
                cin>>surname;
                for(int i=0;i<temp;i++)
                {
                    if(myStudent.studentArray[i][2]==surname)
                    {
                       cout<<myStudent.studentArray[i][0] + " " + myStudent.studentArray[i][1] + " " + myStudent.studentArray[i][2]<<endl;
                    }
                }
                break;
            }
            case 4:
            {
                cout<<"Enter the student ID:";
                cin>>id;
                for(int i=0;i<temp;i++){
                    for(int j=i+1;j<temp;j++){
                        quick_sort(myStudent.studentArray[temp][0],temp);
                    }
                }
                int binary=temp/2;
                for(int i=0;i<temp;i++)
                {
                    if(myStudent.studentArray[binary][0]>id)
                    {
                        binary = binary - binary/2;
                    }
                    if(myStudent.studentArray[binary][0]<id)
                    {
                        binary = binary + binary/2;
                    }
                    if(myStudent.studentArray[binary][0]==id)
                    {
                        cout<<myStudent.studentArray[binary][0]+ " " + myStudent.studentArray[binary][1]+ " " + myStudent.studentArray[binary][2]<<endl;
                        break;
                    }
                }
                break;
            }
            case 5:
            {
                cout<<"id/name/surname"<<endl;
                for(int i=0;i<temp;i++)
                {
                    cout<<myStudent.studentArray[i][0]+ " " + myStudent.studentArray[i][1] + " " + myStudent.studentArray[i][2]<<endl;
                }
                break;
            }    

        }
        cout<<"Want to select action again?(y/Y)";
        cin>>ans1;
    }while(ans1=='y'||ans1=='Y');
    return 0;
}

string Student::getName()
{
    return name;
}

string Student::getSurname()
{
    return surname;
}

string Student::getID()
{
    return ID;
}

void Student::setName(string stdName)
{
    name=stdName;
}

void Student::setSurname(string stdSurname)
{
    surname=stdSurname;
}

void Student::setID(string stdID)
{
    ID=stdID;
}

私の問題はCASE 4にあります。二分検索のみで検索しながらクイックソートしますが、他の検索機能はうまく機能しますが、これをやってのける方法が見つかりませんでした

私のソート機能

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

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

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

私は二次元配列でこのクイックソート機能を使用しています:

ケース 4

case 4:
{
    cout<<"Enter the student ID:";
    cin>>id;
    for(int i=0;i<temp;i++){
        for(int j=i+1;j<temp;j++){
            quick_sort(myStudent.studentArray[temp][0],temp);
        }
    }
    int binary=temp/2;
    for(int i=0;i<temp;i++)
    {
        if(myStudent.studentArray[binary][0]>id)
        {
            binary = binary - binary/2;
        }
        if(myStudent.studentArray[binary][0]<id)
        {
            binary = binary + binary/2;
        }
        if(myStudent.studentArray[binary][0]==id)
        {
            cout<<myStudent.studentArray[binary][0]+ " " + myStudent.studentArray[binary][1]+ " " + myStudent.studentArray[binary][2]<<endl;
            break;
        }
    }
    break;
}

「マイニューソート」

  void quickSort(Student arr[], int left, int right)
  {
     int i = left, j = right;
     Student tmp;
     int pivot = arr[(left + right) / 2].getID();

  /* partition */
     while (i <= j) {
       while (arr[i].getID() < pivot)
              i++;
        while (arr[j].getID() > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
    }
}
/* recursion */
if (left < j)
    quickSort(arr, left, j);
if (i < right)
        quickSort(arr, i, right);
} 

「私の二分探索」

              int binary=temp/2;
        for(int i=0;i<temp;i++)
        {
          if(myStudent[binary].getID()>srcid)
          {
            binary = binary - binary/2;
          }
          if(myStudent[binary].getID()<srcid)
          {
            binary = binary + binary/2;
          }
          if(myStudent[binary].getID()==srcid)
          {
           cout<<myStudent[binary].getID()+ " " + myStudent[binary].getName()+ " " + myStudent[binary].getSurname()<<endl;

         break;
         }

Answer 1

あなたのコードには重大な問題があります。クイックソートは問題ないように見えますが、プログラムはそうではありません。

1. 二分探索を行いたい場合は、リストをソートしたままにするために賢明に挿入することをお勧めします。
2. クイックソート関数を呼び出すためのループは必要ありません
3. クイックソートを呼び出した後、部分的にソートされたリストがあり、クイックソートは実際にはあまり適していないため、挿入ソートを使用することをお勧めします
4. ...

私はあなたのコードを少し変更しましたが、まだ多くのことができます。

    #include <iostream>
    #include <string>

    using namespace std;

    class Student
    {
    public:
        string getName();
        string getSurname();
        string getID();
        void setName(string stdName);
        void setSurname(string stdSurname);
        void setID(string stdIDs);
    private:
        string name;
        string surname;
        string ID;
    };

    int quick_sort_help(Student students[],int left, int right)
    {
        Student val = students[right];
        Student temp;

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

        while (true)
        {
            while (students[++i].getID() < val.getID());

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

            if(i >= j)
                break;

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

        temp=students[i];
        students[i]=students[right];
        students[right]=temp;

        return i;
    }

    void quicksort(Student students[],int left, int right)
    {
        if (left < right)
        {
            int pivot = quick_sort_help(students, left, right);
            quicksort(students, left, pivot - 1);
            quicksort(students, pivot + 1, right);
        }
    }

    void quick_sort(Student students[],int size){
        quicksort(students,0,size-1);
    }

    int main()
    {
        Student myStudent[100];
        string name;
        string surname;
        string id;
        int choice;
        int temp=0;
        char ans1;
        do
        {
            cout<<"Please enter Student's name: ";
            cin>>name;
            cout<<"Please enter Student's surname: ";
            cin>>surname;
            cout<<"Please enter Student's ID: ";
            cin>>id;
            myStudent[temp].setName(name);
            myStudent[temp].setSurname(surname);
            myStudent[temp].setID(id);
            cout<<"Want to add new Student? (y/n)";
            cin>>ans1;
            temp++;
        }while(ans1=='y'||ans1=='Y');

        quick_sort(myStudent, temp);
        do{
            cout<<"What do you want to search with?"<<endl;
            cout<<"1-)Search with name:"<<endl;
            cout<<"2-)Search with surname:"<<endl;
            cout<<"3-)Search with ID (binary!):"<<endl;
            cout<<"4-)Show List!"<<endl;
            cin>>choice;

            switch (choice)
            {
            case 1:
                {
                    cout<<"Enter the student name:";
                    cin>>name;
                    for(int i=0;i<temp;i++)
                    {
                        if(myStudent[i].getName()==name)
                        {
                            cout<<myStudent[i].getID() + " " + myStudent[i].getName() + " " + myStudent[i].getSurname()<<endl;
                        }
                    }
                    break;
                }
            case 2:
                {
                    cout<<"Enter the student surname:";
                    cin>>surname;
                    for(int i=0;i<temp;i++)
                    {
                        if(myStudent[i].getSurname()==surname)
                        {
                            cout<<myStudent[i].getID() + " " + myStudent[i].getName() + " " + myStudent[i].getSurname()<<endl;
                        }
                    }
                    break;
                }
            case 3:
                {
                    cout<<"Enter the student ID:";
                    cin>>id;
                    int left=0;
                    int right = temp;
                    int mid = (right + left)/2;
                    while(left <= right){
                        if(myStudent[mid].getID()>id)
                        {
                            right = mid - 1;
                            mid = (right+left)/2;
                        }
                        if(myStudent[mid].getID()<id)
                        {
                            left = mid + 1;
                            mid = (right+left)/2;
                        }
                        if(myStudent[mid].getID()==id)
                        {
                            cout<<myStudent[mid].getID()+ " " + myStudent[mid].getName()+ " " + myStudent[mid].getSurname()<<endl;
                            break;
                        }
                    }
                    break;
                }
            case 4:
                {
                    cout<<"id/name/surname"<<endl;
                    for(int i=0;i<temp;i++)
                    {
                        cout<<myStudent[i].getID()+ " " + myStudent[i].getName() + " " + myStudent[i].getSurname()<<endl;
                    }
                    break;
                }    
            }
            cout<<"Do you want to continue?(y/n)"<<endl;
            cin>>ans1;
        }while(ans1=='y' || ans1=='Y');

        return 0;
    }

    string Student::getName()
    {
        return name;
    }

    string Student::getSurname()
    {
        return surname;
    }

    string Student::getID()
    {
        return ID;
    }

    void Student::setName(string stdName)
    {
        name=stdName;
    }

    void Student::setSurname(string stdSurname)
    {
        surname=stdSurname;
    }

    void Student::setID(string stdID)
    {
        ID=stdID;
    }