C++ quicksort with string array

Question

I have a problem with my quicksort code. I don't know why but it doesn't sort.

My Program

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

my problem is at CASE 4 ,i will quicksort while only searching with binary search,the other search functions work well,i couldn't find a way to pull this off

my sort function

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

I am using this quicksort function with two-dimensional array:

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

"My New Sort"

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

"My Binary Search"

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

You really need to eliminate the unrelated code, and show the smallest amount of code you can that still demonstrates the problem (though I should add that by including the code at all, you've done better than most first-time poster). — Jerry Coffin
– Jerry Coffin, Commented Apr 23, 2012 at 16:30
it was indented but it becomes hardly readable after copy paste sorry — Emircan ayvaz
– Emircan ayvaz, Commented Apr 23, 2012 at 17:48
Why is the first parameter of your quicksort a reference to a single string? What is the purpose of the two nested for loops in the beginning of case 4? — Blastfurnace
– Blastfurnace, Commented Apr 23, 2012 at 18:15
Looking over your code, I think the first thing you should do is to review your Student class. Does the studentArray really belong in there? — Kevin
– Kevin, Commented Apr 23, 2012 at 18:25
@Blastfurnace yeah i realized that two nested loops doesn't do anything there. — Emircan ayvaz
– Emircan ayvaz, Commented Apr 23, 2012 at 19:23

Ehsan Shoja · Accepted Answer · 2012-04-24 09:52:40Z

Dude your code has serious problems, your quicksort seems OK but your program is not.

if you want to do binary search it is better to insert wisely to keep the list sorted.
you do not need a loop for calling quicksort function
after once you have called quicksort, you have a partially sorted list where quicksort is not actually so good, so it is better to use insertion sort
...

I modified your code a little, still you can do more.

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

1 && 3 ) this is a quicksort homework so i can only use quicksort algorithm 2) i deleted the loop after but i forgot to edit here
My homework is to make a student class,add some students with random ids then quicksort them and search a student from an id.
1) remove "string studentArray[100][3];" from student class 2) in main declare "Student myStudent[100];"
thanks a lot buddy,i managed to do it,there is a little bug but it doesn't important much.

Collectives™ on Stack Overflow

C++ quicksort with string array

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related