Sorting by city and then by name

[AdamLad3]

Hi,
I'm writing a program in C++ to ask the user for a list of ten names and cities of residence in the format <firstname> <Surname> <city>.
The amount of spaces between each doesn't matter as I will be using isspace.
then i have to sort the list by city and then in each city group alphabetically by name.
I'm able to extract each of the three components from the strings, but now I'm not sure on how to incorporate sorting into this, we have to use bubble sort.
This is what I have so far

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

int main()
{
 char name[10][80];
 char buffer1 [80];
 char buffer2 [80];
 char buffer3 [80];
 int i,j,k,q,word_size,start_pos,end_pos,name_size,city_start,city_end,city_length;


 cout<<"Enter 10 names and cities of residence: "<<"\n";
 gets( name[0]);
 gets( name[1]);
 gets( name[2]);
 gets( name[3]);
 gets( name[4]);
 gets( name[5]);
 gets( name[6]);
 gets( name[7]);
 gets( name[8]);
 gets( name[9]);

 cout<<"***Initialise check***"<<"\n";


cout<<"\n";
cout<<"\n";
cout<< name[0]<< "\n";
cout<< name[1]<< "\n";
cout<< name[2]<< "\n";
cout<< name[3]<< "\n";
cout<< name[4]<< "\n";
cout<< name[5]<< "\n";
cout<< name[6]<< "\n";
cout<< name[7]<< "\n";
cout<< name[8]<< "\n";
cout<< name[9]<< "\n"<<"\n";

cout<< "***Check Complete***"<<"\n";

  for (i=0; i<=9; i++)
  { j=0;

   while (isspace  (name[i][j]) )

     {j=j+1;

     }


         k=j;
         while(!isspace(name[i][k])) k=k+1; //advances through the first name
         name_size = k-j;

         for (q=0; q<=name_size; q++)
          {
            // this generates the name
            buffer1[q] = name[i][j];
            j++;

          }

     buffer1[j]='\0';//this is the null char to terminate first name name
     cout<<"Name "<<i+1<<": "<<buffer1<<"\n";

   if (j<80){
         while(isspace(name[i][k])) k=k+1;   // advances through the next block of spaces
         start_pos=k;
         while(!isspace(name[i][k])) k=k+1;// advances through the surname
         end_pos=k;

         word_size = end_pos - start_pos;
   }

     // check word size of first char


     for (q=0; q<=word_size; q++)
          {
            // this generates the surname
            buffer2[q] = name[i][start_pos];
            start_pos++;

          }
           //this is the null char to terminate surname name
    buffer2[start_pos]='\0';
    cout << "Surname "<<i+1<<": "<<buffer2 << "\n";


    while(isspace(name[i][k])) k++;

    city_start=k;
    while(!isspace(name[i][k])) k++;

    city_end=k;
    city_length=city_end-city_start;


    for (q=0; q<=city_length; q++)
          {
            // this generates the city
            buffer3[q] = name[i][city_start];
            city_start++;

          }

          //this is the null char to terminate surname name
    buffer3[city_start]='\0';
    cout<< "City " << i+1 <<": "<< buffer3 <<"\n";
    cout<< "\n" << "\n";

  }

    return 0;
}

[Labdabeta]

Modularization will be key here. If you have not yet learnt functions, look them up. Then you can make your main look like this:

const int numNames=10;//this helps make the code more flexible
int main()
{
    char name[numNames][80];
    for (int i=0; i<numNames; ++i)//use a loop
        gets(name[i]);
    char firstNames[numNames][80];
    char lastNames[numNames][80];
    char city[numNames][80];
    breakApart(name,firstNames,lastNames,city);//this function will deal with the spaces
    sortNames(city,firstNames,lastNames);
    cout<<"Sorted names:"<<endl;
    for (int i=0; i<numNames; ++i)
    {
        cout<<city[i]<<' '<<firstNames[i]<<' '<<lastNames[i]<<endl;
    }
    return 0;
}

The sorting algorithm can just sort the arry three times (by the different values) since bubble sort is stable. Here is some pseudo-code for that function:

void sortNames(char array1[numNames][80],char array2[numNames][80],char array3[numNames][80])
{
    //bubble sort array3 remembering that any swaps you do you must do to all the arrays
    //bubble sort array2 remembering that any swaps you do you must do to all the arrays
    //bubble sort array1 remembering that any swaps you do you must do to all the arrays
}

[mike_2000_17]

Have you learned about struct ? If you did, you should define a struct to hold all the data in once record, as in:

struct Individual {
  char first_name[80];
  char last_name[80];
  char city_name[80];
};

The kind of multi-level sorting that you are describing (sort by city, sort by last-name within a city, then sort by first-name within one city and one last-name) can be easily achieved with a proper comparison function. This is just like sorting things in alphabetical order (first sort by the first letter, then by second letter within each first letter group, etc..). There is no need for the type of triple sorting that Labdabeta (or is it Lambdabeta!) is suggesting, it would be very wasteful to do this.

Basically, you should define your own comparison function. I suggest:

bool compare_individuals(const Individual& a, const Individual& b) {
  int result = strcmp(a.city_name, b.city_name);
  if( result != 0 )
    return (result > 0);
  result = strcmp(a.last_name, b.last_name);
  if( result != 0 )
    return (result > 0);
  result = strcmp(a.first_name, b.first_name);
  return (result > 0);
};

The above uses the function strcmp which will return 0 if the strings are equal, -1 if the first string comes before the other in alphabetical order, and 1 if the first string comes after the other in alphabetical order. If you look at the above function, you will see that it is going to return "true" if individual "a" should go after individual "b" in the sorted array, and false if "a" should come before "b".

Once you have the above two things, implementing the sorting algorithm boils down to just any normal sorting. Say, you have a sorting algorithm to sort integers from lowest to highest value (by using the "greater-than" comparison). Then, you can apply the exact same algorithm except that the integers are replaced by "Individuals" and the greater-than comparison is replaced by the function "compare_individuals".

[AdamLad3]

Have you learned about struct ? If you did, you should define a struct to hold all the data in once record, as in:

struct Individual {
  char first_name[80];
  char last_name[80];
  char city_name[80];
};

The kind of multi-level sorting that you are describing (sort by city, sort by last-name within a city, then sort by first-name within one city and one last-name) can be easily achieved with a proper comparison function. This is just like sorting things in alphabetical order (first sort by the first letter, then by second letter within each first letter group, etc..). There is no need for the type of triple sorting that Labdabeta (or is it Lambdabeta!) is suggesting, it would be very wasteful to do this.

Basically, you should define your own comparison function. I suggest:

bool compare_individuals(const Individual& a, const Individual& b) {
  int result = strcmp(a.city_name, b.city_name);
  if( result != 0 )
    return (result > 0);
  result = strcmp(a.last_name, b.last_name);
  if( result != 0 )
    return (result > 0);
  result = strcmp(a.first_name, b.first_name);
  return (result > 0);
};

The above uses the function strcmp which will return 0 if the strings are equal, -1 if the first string comes before the other in alphabetical order, and 1 if the first string comes after the other in alphabetical order. If you look at the above function, you will see that it is going to return "true" if individual "a" should go after individual "b" in the sorted array, and false if "a" should come before "b".

Once you have the above two things, implementing the sorting algorithm boils down to just any normal sorting. Say, you have a sorting algorithm to sort integers from lowest to highest value (by using the "greater-than" comparison). Then, you can apply the exact same algorithm except that the integers are replaced by "Individuals" and the greater-than comparison is replaced by the function "compare_individuals".

Is there any way of sorting this using bubble sort only ie. no strcmp etc. It's just that I'm pretty new to C++ and when our lecturer gave us this assignment he only gave us examples of simple bubblesort code to help us with it.
Also thank you for your replies

[Labdabeta]

You could make your own version of strcmp. Here is what it could look like:

int strcmp(char *str1, char *str2)
{
    for (int i=0; str1[i]&&str2[i]; ++i)//compare each character
    {
        if (str1[i]>str2[i])
            return 1;
        if (str2[i]>str1[i])
            return -1;
    }
    //so far they are the same.... compare lengths
    int str1len,str2len;
    for (str1len=0; str1[str1len]; ++str1len){}//get str1len
    for (str2len=0; str2[str2len]; ++str2len){}//get str2len
    if (str1len==str2len)
        return 0;//they are the same string
    else if (str1len>str2len)
        return 1;//str1 is bigger
    else
        return -1;//str2 is bigger

[AdamLad3]

You could make your own version of strcmp. Here is what it could look like:

int strcmp(char *str1, char *str2)
{
    for (int i=0; str1[i]&&str2[i]; ++i)//compare each character
    {
        if (str1[i]>str2[i])
            return 1;
        if (str2[i]>str1[i])
            return -1;
    }
    //so far they are the same.... compare lengths
    int str1len,str2len;
    for (str1len=0; str1[str1len]; ++str1len){}//get str1len
    for (str2len=0; str2[str2len]; ++str2len){}//get str2len
    if (str1len==str2len)
        return 0;//they are the same string
    else if (str1len>str2len)
        return 1;//str1 is bigger
    else
        return -1;//str2 is bigger

I could, if I understood it. We have only covered basic bubblesort in lectures and I have never seen strcmp in any of these lectures. What I am trying to achieve is to use the main code at the beginning of this thread and usin basic bubblesort, sort first by city (buffer3) and then by first name (buffer1)

[Labdabeta]

Okay... lets see if we can explain this. Here is a pseudoC++code bubblesort algorithm which I expect you are familiar with:

void bubbleSort(Array X)
{
    bool swapped=true;
    int length=lengthOf(X);
    while (swapped)
    {
        swapped=false;
        for (int i=1; i<length-1; ++i)
        {
            if (X[i-1]>X[i])
            {
                swap(X[i-1],X[i]);
                swapped=true;
            }
        }
        --length;//this is an optimization that can be done
    }
}

Thi issue is that lengthOf(X) is undefined and X[i-1]>X is undefined for strings. The problem then becomes defining these things. To get the length you will likely pass in a parameter called length. For the X[i-1]>X issue you can use strcmp(X[i-1],X). Basically strcmp(A,B) can be thought of as A>B. The thing is that you want to compare more than one string so you need to define an even more complicated comparison algorithm. This is easiest to do if you group all of your strings (city, first, last) into a struct. As such your final code would look something like this:

const int STRING_BUFFER_SIZE=80;//increase this to allow for really long names
struct Individual//this will store 1 person
{
    char firstName[STRING_BUFFER_SIZE];
    char lastName[STRING_BUFFER_SIZE];
    char cityName[STRING_BUFFER_SIZE];
};
//this function will be equivalent to a>b
bool isGreater(Individual a, Individual b)
{
    int result = strcmp(a.cityName, b.cityName);//determine if the cities are different
    if( result != 0 )//if they are then...
        return (result > 0);//return true if city A comes first
    result = strcmp(a.lastName, b.lastName);//cities are the same... check last names
    if( result != 0 )//if they are different
        return (result > 0);//return true if last name A comes first
    result = strcmp(a.first_name, b.first_name);//moving on to first names
    return (result > 0);//return true if A comes first.
}
void bubbleSort(Individual a[], int aLength)
{
    bool swapped=true;
    int length=aLength;
    while (swapped)
    {
        swapped=false;
        for (int i=1; i<length-1; ++i)
        {
            if (isGreater(a[i-1],a[i]))//this is the same as if (a[i-1]>a[i])
            {
                //this is how to implement a swap:
                Individual temp=a[i-1];
                a[i-1]=a[i];
                a[i]=temp;
                swapped=true;
            }
        }
        --length;
    }
}

Later, when you learn OOP, you can implement a > operator to allow the code to be neater, but until then this code should work. The key now is to understand it.

[Programmer!!!]

Hey!!! :)

This code looks good ie the final code submitted by user Lamdabeta. I've added the cstring header to it to implement strcmp, after that I get one error: "Undefined reference to 'WinMain@16'". If I include int main (), this error is removed but replaced by about 20 others!!! Any ideas on how I can get this program to actually run??

[mike_2000_17]

>> Any ideas on how I can get this program to actually run??

Reading the error messages and going to the line that they point to and take a look at them. Maybe it's just me, but I think this might be a good start to getting the program to run.

Generally, when code is posted on a forum like this, it gets posted to explain it as an example. The hope is that it will help people understand how to do it on their own.

If working code is all you care about, try this:

#include <cstring>
#include <algorithm>

const int STRING_BUFFER_SIZE=80;//increase this to allow for really long names
struct Individual {
    char firstName[STRING_BUFFER_SIZE];
    char lastName[STRING_BUFFER_SIZE];
    char cityName[STRING_BUFFER_SIZE];
};
bool isGreater(const Individual& a, const Individual& b) { 
  int result; 
  return ((result=std::strcmp(a.cityName, b.cityName))?(result>0):((result=std::strcmp(a.lastName,b.lastName))?(result>0):(std::strcmp(a.firstName, b.firstName)>0))); 
};
void bubbleSort(Individual* a, int aLength) { 
  for(bool swapped=true; (swapped && (!(swapped=false))); --aLength) 
    for(int i=1;i<aLength;++i) 
      if((isGreater(a[i-1],a[i])) && (swapped=true)) std::swap(a[i-1],a[i]); 
};

Try submitting this and watch your grade shrink! (or sky-rocket, if your teacher is a moron)

There's a big difference between exemplary (pseudo-)code, working code, and production code.

[Damian Dalton]

Students are NOT allowed to use forums to aid homework assignments,
Damian Dalton.

[Lerner]

Learning how to manipulate data in arrays is a useful skill to have. Therefore I suspect that this is whay your instructor has provided you with this project. Clearly, there are several approaches that could be used, some more sophisticated than others, and you will get a wide variety of recommendations about what you could do. You will need to decide what you do. At the base level you could sort by city, then sort the elements for a given city by name. If you know about structs/classes and operator overloading, then that approach would simplify the process. There might even be another way. For example, you could try generating a fourth array of strings that contains strings formatted as city name followed by last name followed by first namewith each field separated by a single space. Assuming case insensitive input, you shoulde be able to use a single loop to sort by city, then last name, then first name. However, no matter what you approach you take, if you are going to try to compare C style strings so they can be sorted alphabetically, then you are going to have to use strcmp(), or a related function, whether your instructor told you how to use that function or not, unless you write your own version of strcmp() (which may be part of the learning process, too, of course). It isn't all that difficult to use strcmp(). The syntax and how to interpret the return value is available in any decent resource you look up on line.

[Labdabeta]

Not to stick my head in where it doesnt belong, but if a student is having trouble understanding a concept and their teacher is unable to get them to explain it are they not allowed to do research? And when that research comes up fruitless are they not allowed to ask for guidance from others? It is clear that the student made an effort to solve the homework on their own, but needed some help. Homework should be assigned to help students learn, if they learn then it should matter very little how they got their solutions. I understand discouraging the using of forums to get answers, but to help understand answers I think that they can be helpful. It seems as though there was a student who did not understand bubblesorting of strings who now understands bubblesorting of strings. Furthermore by definition a student must study, if something is preventing them from being able to study then any good student should seek to rectify it. If a student has made a legitimate effort to solve a problem and has been unable to come up with a solution due to lack of understanding then they should be allowed to use almost any means by which to understand, assuming they are not being assessed. Of course if this was not 'homework' per se, but rather an assignment I take back what I have said and completely understand your concerns. Finally I also hope that the student will/did not plagiarize from the solutions given here and merely uses our examples to help better their understanding of the concept. Maybe if the particular rules of the particular student explicitly deny use of forums for homework further inquiry may be necessary. Gone are the days when a student got all their knowledge from teachers and textbooks. This is the 21st century and whether you like it or not all students are going to be getting information from the internet.

[mike_2000_17]

It's all a matter of balance and common sense. If you look at most threads on this forum and others, and the rules of this forum, clearly we don't condone giving away complete ready-for-submission code. But if after several posts back and forth between the OP and a few users, working its way towards a solution to the problem, and explaining the issues the OP has difficulty with along the way, it often happens at the end that you could pick the code posted on thread and copy-paste it into a homework submission of your own.

First, as far as the OP is concerned, the important thing is the learning process that led to this final working code, and whether a portion of the code provided by users (even a significant portion of it) ends up on his homework / assignment submission or not, isn't really a big issue.

Second, for those who go out on the internet looking for ready-made code that they can copy-paste for their particular homework assignment, well, I doubt that they will have any trouble finding it, whether or not we post working final code on this forum. In fact, many of the basic assignments you would get in an introductory course on C++ are the kind of simple problems whose solution can often be found as easily as looking up the examples on www.cplusplus.com, so it's not like they have to look very far. The main thing is, you are personally responsible for your own success and failure. A student might cheat his way through the first half or even a complete introductory course on C++. If he doesn't go further along the C++ learning curve, then who cares, his competence in C++ is negligible (cheated or not). If he does go further in learning or courses, he will have to stop cheating very soon because you just can't fake it forever (especially in the real world, you can smell fake competence from a mile away... I've seen people give me source code that "they wrote" which had somebody else's name as author in the comment section at the top of source files, but I had figured out that it wasn't their work long before I noticed the original author's name in the comment sections.. if someone thinks he can plagiarize real world code and go unnoticed, he's an idiot).

If some people are too stupid to realize that when you cheat your way through a course, you are not cheating the system, but really cheating yourself (not to use another word like f...ing), then nobody can stop them from doing so, we can only try to convince them otherwise.

[Damian Dalton]

Students are NOT allowed to use forums to aid homework assignments,
Damian Dalton.

sorry but that was my friend messing...this is NOT damian dalton so don't worry , good luck with the assignment