Solved

Sorting algorithm (Easy but long)

Posted on 2001-06-03
14
223 Views
Last Modified: 2008-03-03
// I have this class:

class Person
{
protected:
     char *first;
     char *last;
     char *address;
     char *city;
     char *state;
     long int zip;
     long int phone;

public:
     Person();
     Person(char *First,char *Last,char *Address,char *City,char *State, long int zip, long int phone);      
     

// I have array of Person objects that need to be sorted by last,first name.  Assume the array has 50 or less items and should be sorted using a simple Quick sort or Merge sort whichever is more efficient."NO BUBBLE SORT I can do that".  For an A grade I need code that will work and an explanation of how it works.  Please make the code as simple as possible.
0
Comment
Question by:DwarfBaby
  • 7
  • 4
  • 2
  • +1
14 Comments
 
LVL 5

Accepted Solution

by:
djbusychild earned 200 total points
ID: 6150988
you could use qsort or use STL's template classes' own sort functions.. to use qsort do something like this..
pretty self-explanatory... I think.. It's for example purposes only.

#include <stdlib.h>
#include <string.h>
#include <iostream.h>

class Person
{
protected:
    char *first;
    char *last;
    char *address;
    char *city;
    char *state;
    long int zip;
    long int phone;

public:
    Person(){first=last=address=city=state=NULL;zip=0;phone=0;}
    void setMembers(char *First,char *Last)
     {
          /* not checking arr bonds */
          first=new char[strlen(First)];
          last=new char[strlen(Last)];
          strcpy(first,First);
          strcpy(last,Last);
     }
     char* getLastName(){return last;};
     char* getFirstName(){return first;};
};

/*
   <0 elem1<elem2
    0 elem1==elem2
   >0 elem1>elem2
*/
int compareByLastName(const void *elem1, const void *elem2)
{
     Person* person1=(Person*)elem1;
     Person* person2=(Person*)elem2;

     return strcmp(person1->getLastName(),person2->getLastName());
}
int compareByFirstName(const void *elem1, const void *elem2)
{
     Person* person1=(Person*)elem1;
     Person* person2=(Person*)elem2;

     return strcmp(person1->getFirstName(),person2->getFirstName());
}
int main(int argc, char* argv[]) {

     Person people[5];
     people[0].setMembers("a","e");
     people[1].setMembers("b","d");
     people[2].setMembers("c","c");
     people[3].setMembers("d","b");
     people[4].setMembers("e","a");

     cout << endl<< "sort by last name"<<endl;

     qsort(people,5,sizeof(Person),compareByLastName);

     int i;
     for (i=0;i<5;i++) {
          cout << "Last Name:" << people[i].getLastName() << " Firt Name:"<<people[i].getFirstName()<<endl;
     }
     cout << endl<<"sort by first name"<<endl;

     qsort(people,5,sizeof(Person),compareByFirstName);
     for (i=0;i<5;i++) {
          cout << "Last Name:" << people[i].getLastName() << " Firt Name:"<<people[i].getFirstName()<<endl;
     }
     return 0;
}
0
 
LVL 5

Expert Comment

by:djbusychild
ID: 6150992
you should do your own tidying it up, encapsulating, err checking, etc, etc... this is purely a quick hack example. =)
0
 
LVL 5

Expert Comment

by:djbusychild
ID: 6150995
qsort is a builtin function in stdlib that does qsort for you.

the man page entry can be found here

http://www.opengroup.org/onlinepubs/007908799/xsh/qsort.html

you're basically telling it how big the data is, how many of them there are, and what function shold be used to compare the two.
0
 
LVL 5

Expert Comment

by:djbusychild
ID: 6150999
I really should be allocating memory for strlen(last)+1 there.. (for the NULL terminating char), and if you're a C++ person you wouldn't use the C style casting that I used either.
0
 

Author Comment

by:DwarfBaby
ID: 6151025
Ok, I understand your code but I'm trying to learn how the quick sort works.  I need the code for a quick sort not the code for how to use the quick sort.  Sorry, I was not very clear about what I wanted.
0
 
LVL 5

Expert Comment

by:djbusychild
ID: 6151035
oh, well here's an example with full explanation (There are gazilliong qsort implementations on the web)

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort1a.html
0
 
LVL 5

Expert Comment

by:djbusychild
ID: 6151036
if you don't understand the explanation I can help you
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:DwarfBaby
ID: 6151061
I need to get something to eat and then I am going to try to work a quick sort into my code.  I will let you know if I need more explanation in a couple hours.  Thanks
0
 

Expert Comment

by:idyott
ID: 6151075
this question sounds like homework
0
 
LVL 5

Expert Comment

by:djbusychild
ID: 6151098
hmm... come to think of it, it does. idyott... ;)
0
 

Author Comment

by:DwarfBaby
ID: 6151586
Thanks for the help.
0
 
LVL 22

Expert Comment

by:nietod
ID: 6152043
DwarfBaby, if this is homework then the solution above will not be satisfactory.  You would be expected to write your own sort procedure, not use one that is part of the standard library.  (Is like ordering take-out food for a cooking class in home-ec.)

And if that is the case, then we can't _give_ you the answer.  You need to write it yourself.  But we coudl help you.
0
 

Author Comment

by:DwarfBaby
ID: 6165549
The question was not really homework.  I say not really because all the instructions called for either Selection sort or an insertion sort, which I know how to do.  I just thought I'd throw in a quicksort too for some browny points.  Although I did finally get the quick sort to work I barley understand how it works.  If anyone knows of a good website that can explain it better I will set up some extra points for you.  Thanks
0
 

Expert Comment

by:idyott
ID: 6172285
you can use "the c programming language"
in the index look 4 qosrt and u will c how it is written.

very generally, it uses divides the array in2 2 parts and sorts each of them recursively
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now