Sorting a 2d array of strings in C++??
 

Hi y'all!

I found this forum through google and I was hoping that I could get some help!!
I've been assigneda rather odd assignment by my C++ teacher. I have a 2d array of names (names[17][20]) which has to be sorted alphabetically via selection sort, we can not use pointers. We then have to do a Binary Search and find a name input by the user, if the name is found we have to display it and its position in the array, if the name is not found we have to return the name and the fact that it's not found.
My 3 friends and I have spent all weekend on this assignment, and searching for possible help, but we have only been able to come up with following (I'm sorry for the way this is formatted I don't know how to do the cool formatting I've seen on here) :

#include <iostream>

#include <cstring>

using namespace std;



void initArray();

void selectionSort(char names[20][17]);

void searchName(char names[20][17]);

int binarySearch(char name[][17], char names[20][17]);

void DoOperationAgain();



int main()

{ 

initArray();

}

void initArray()

{

        char names[20][17]= {"Collins, Bill", 

                                                 "Smith, Bart", 

                                                 "Allen, Jim",

                                                 "Griffin, Jim", 

                                                 "Stamey, Marty", 

                                                 "Rose, Geri",

                                                 "Taylor, Terri", 

                                                 "Johnson, Jill", 

                                                 "Allison, Jeff",

                                                 "Looney, Joe", 

                                                 "Wolfe, Bill", 

                                                 "James, Jean", 

                                                 "Weaver, Jim",

                                                 "Pore, Bob", 

                                                 "Rutherford, Greg", 

                                                 "Javens, Renee",

                                                 "Harrison, Rose", 

                                                 "Setzer, Cathy", 

                                                 "Pike, Gordon",

                                                 "Holland, Beth"};

selectionSort(names);

}

void selectionSort(char names[][17])

{ int NumEles = 20;

        int number, minIndex, elems;

        elems = 20;

        char minValue[1][17];

        cout << "The unsorted names are \n";

        for (int count = 0; count < NumEles; count++)

                cout << names[count] << endl;

        cout << "Press [Enter] to continue!";

        cin.get();

        system ("cls");

        for (number = 0; number < (elems - 1); number++)

        {

                minIndex = number;

                strcpy(minValue[17], names[number]);

                for (int index = number + 1; index < elems; index++)

                {

                        if (strcmp(names[index], minValue[17]) < 0)

                        {

                                strcpy(minValue[17], names[index]);

                                minIndex = index;

                        }

                }

                strcpy(names[minIndex], names[number]);

                strcpy(names[number], minValue[17]);

        }

        

cout << "The sorted names are\n";

        for (int count = 0; count < NumEles; count++)

                cout << names[count] << endl;

        cout << "Press [Enter] to continue!";

        cin.get();        

        searchName(names);

}





void searchName(char names[][17])

{char name[1][17];

int position = -1;

cout << "Please enter a name in [Last, First] format.\n";

cin.getline(name[17], 17);

binarySearch(name, names);

if (position < 0)

{

        cout << "Sorry, name was not found.\n";

        cout << "Press [Enter] to continue.\n";

        cin.get();

        system("cls");

}

else 

{

cout << name << " was found in position: " << position << "!\n";

}

DoOperationAgain();

}

int binarySearch (char name [1][17], char names [][17])

{

        int numElems = 17;

        int first = 0, last = numElems - 1, middle, position = -1;

        bool found = false;



        while (!found && first <= last)

        {

                middle = (first + last)/2;

                if (strcmp(names[middle], name[17]) < 0)

                {

                        found = true;

                        position = middle;

                }

                else if (strcmp(names[middle], name[17]) <= 1)

                        last = middle - 1;

                else

                        first = middle + 1;

        }

        return position;

}



void DoOperationAgain()

{

char choice;

int safe;

safe = 0;

        do

        {



cout << "Would you like to repeat the operation?\n";

cout << "[Y]es or [N]o\n";

cin >> choice;

                system("cls");

switch (choice)

{

case 'y':

case 'Y': {

        cin.ignore();

        system("cls");

        initArray();

                  }

        break;

case 'n':

case 'N': exit(0);

        break;

default:{ 

                cout << "Please enter a valid value!\n";

            safe = 1;

                DoOperationAgain();

                }

}        

        }

while (safe != 0);  

}

Code tags added. -Narue

When it sorts, it only does about 1/2 of them and then leaves the rest (it also cuts up some of the names :mad: ). Also we can't get the search function to work!
Could y'all please help us?! :cry: :cry:

Re: Sorting a 2d array of strings in C++??
 

When I have code that gives me trouble, I break it down into parts. For example, to make sure your sort works, perfect the algorithm using integers instead of strings. Then modify it to use strings. Perfect your binary search algorithm on integers, then modify it to work with strings. At that point you only need to build a framework around those two functions. It looks a lot like you were trying to chew up the whole problem at once, and you got bogged down in the slew of problems that popped up.

Re: Sorting a 2d array of strings in C++??
 

I don't know how to change the code to work with strings :(
I've tried to get it to work with ints we're trying it with ints now but translating to strings is something that we do not know how to do.

Re: Sorting a 2d array of strings in C++??
 

>I don't know how to change the code to work with strings
Clearly.

>we're trying it with ints now
No, you're trying it with arrays of char from the looks of your code.

>translating to strings is something that we do not know how to do.
Now you're lying. If you and your buddies didn't know how to do it then you wouldn't have gotten so far. You're on the right track.

Re: Sorting a 2d array of strings in C++??
 

Please, help us! We have literally been working on this since 9am this morning! We spent 48 hours on this (over Friday, Saturday, and Sunday) and it was due today at noon! Our teacher has been no help and we've had to basically shoot in the dark! We are not allowed to use pointers, and everyone on the internet says to use them (we would use them in a heart beat if we were allowed, as we know how).
This is the second assignment that there are no examples out of the book and our teacher's response is: "Well its in there." When pressured to point to a page his response changes to "It is." (without referencing a page or any chapter) When asked how do you do it, he responds "You do."

So please if you could help us by fixing what ever little problems or at least explicitly point them out so that we can get a better feel for how to fix it.

Thanks greatly!
Matt LeGare, Charles Lee, John Christensen

Re: Sorting a 2d array of strings in C++??
 

This assumes you're sorting by last name:

#include <cstring>

#include <iostream>



using namespace std;



void selectionSort ( char names[][17], int n );

int binarySearch ( char name[], char names[][17], int n );



char names[20][17]= {

  "Collins, Bill", 

  "Smith, Bart", 

  "Allen, Jim",

  "Griffin, Jim", 

  "Stamey, Marty", 

  "Rose, Geri",

  "Taylor, Terri", 

  "Johnson, Jill", 

  "Allison, Jeff",

  "Looney, Joe", 

  "Wolfe, Bill", 

  "James, Jean", 

  "Weaver, Jim",

  "Pore, Bob", 

  "Rutherford, Greg", 

  "Javens, Renee",

  "Harrison, Rose", 

  "Setzer, Cathy", 

  "Pike, Gordon",

  "Holland, Beth"

};



int main()

{

  cout<<"Unsorted:"<<endl;

  for ( int i = 0; i < 20; i++ )

    cout<< names[i] <<'\n';

  cout<<endl;



  selectionSort ( names, 20 );



  cout<<"Sorted:"<<endl;

  for ( int i = 0; i < 20; i++ )

    cout<< names[i] <<'\n';

  cout<<endl;



  cout<<"Find Allen, Jim: ";

  cout<< binarySearch ( "Allen, Jim", names, 20 ) <<endl;



  cout<<"Find Wolfe, Bill: ";

  cout<< binarySearch ( "Wolfe, Bill", names, 20 ) <<endl;



  cout<<"Find James, Jean: ";

  cout<< binarySearch ( "James, Jean", names, 20 ) <<endl;



  cin.get();

}



void selectionSort ( char names[][17], int n )

{

  // Fix for last name sort

  for ( int i = 0; i < n; i++ )

    names[i][strcspn ( names[i], "," )] = '\0';



  // Sort

  for ( int i = 0; i < n - 1; i++ ) {

    char save[17];

    int min = i;



    for (int j = i + 1; j < n; j++) {

      if ( strcmp ( names[j], names[min] ) < 0 )

        min = j;

    }



    memcpy ( save, names[i], 17 );

    memcpy ( names[i], names[min], 17 );

    memcpy ( names[min], save, 17 );

  }



  // Recover first names

  for ( int i = 0; i < n; i++ )

    names[i][strlen ( names[i] )] = ',';

}



int binarySearch ( char name[], char names[][17], int n )

{

  int low = 0, high = n - 1;



  while ( low <= high ) {

    int mid = ( low + high ) / 2;



    if ( strcmp ( name, names[mid] ) < 0 )

      high = mid - 1;

    else if ( strcmp ( name, names[mid] ) > 0 )

      low = mid + 1;

    else

      return mid;

  }



  return -1;

}

Re: Sorting a 2d array of strings in C++??
 

Narue, you're code is full of bugs. :cool:

Lol, I tried running it and it displayed a lot of funny stuff.

Anyway, Fodo_bett, this is the exact same problem I'm working on, whenever I'm having trouble I go to the index. I think page 221 will will help you, the major goal of the problem has a focus of bringing in past information.

I haven't worked out the problem myself yet, but I think I'll figure it out by the end of the day, and I have no prior C++ experience except this class and I also have no clue what pointers are.

I can also use help when it comes to sorting alphabetically.

What I understand from the problem is that it wants us to first sort out the data, and then search it using a binary search method. Sorting out the string has to be sort of like sorting the names alphabetically only within the char array.

After sorting them out, it's a matter of searching and comparing elements. It's a freaking pain.

Also page 443 talks about arrays in the strings.

Re: Sorting a 2d array of strings in C++??
 

I think both of us read the problem wrongly... we're not trying to sort it "alphabetically" per say. It just needs to sort out the strings in such a way that we can search the array for the name.

Binary search.

Re: Sorting a 2d array of strings in C++??
 

I found the solution.

Use strcpy to convert string values as an assignment operatoer over the '=' sign.

Re: Sorting a 2d array of strings in C++??
 

Don't bump year old threads, it's rude.

>Narue, you're code is full of bugs.
...

Words fail me. Don't *EVER* say this unless you can prove it. If you can't, you've stumbled upon the worst possible insult to a programmer.

>Lol, I tried running it and it displayed a lot of funny stuff.
Just because you run it and it doesn't work doesn't mean the code is buggy. It's more likely that you simply don't know what you're doing, and this "bug report" proves it. Don't ever comment on my code again.