Thread: sorting an array of structs

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    2

    sorting an array of structs

    I am trying to sort a file of 500 structs. I have read them all into an array, but am unable to sort them using a bubble sort. Is there a better way? Here is the function I am using....

    void searchArray::sortfile(studarray student, fstream& tempfile,
    int length)
    {
    studarray temp;
    int temp1;
    int temp2;
    int pos;
    int placecount;
    length = 500;

    for(int pos =0; pos < length - 1; pos++)
    {
    temp1 = pos;

    for(placecount = pos + 1; placecount < length; placecount++)

    if(student[placecount] < student[temp1])
    temp1 = placecount;

    temp = student[temp1].Id;
    student[temp1] = student[pos];
    student[pos] = temp;
    }

    }

    Any help would be appreciated.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Is there a better way?
    Yes - use qsort in stdlib.h

    All you need to do is write the comparison function which compares two student records.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    2

    Thanks

    Thanks, I have never used qsort, but I will definetely give it a try.

    stm

  4. #4
    Registered User matheo917's Avatar
    Join Date
    Sep 2001
    Posts
    279
    there's also a <vector> and <deque>, that is if you're familiar with templates....????

    ps. just an advice.... you want to sort an array of 500 sturctures... first you have to find out what should this sorting be based on.... for instance: every student maybe has an ID number you should use perhaps something of this kind to base your sorting algorithms on....it is possible to make a "home made" function to sort this array, u r not forced to use templates....

    good luck..

    Regards,
    matheo917

  5. #5
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    >temp = student[temp1].Id;

    is that legal?

    temp is of type studarray. so is student.
    but student[temp1].Id is NOT of type studarray. when you index the array, you are getting just one student, and then you are going further in by getting a specific variable of that student (Id). There for that statements is not legal.

    >Yes - use qsort in stdlib.h


    No offense, Salem, but...eww..
    Have you ever tried to use the standard libraries version of the quick sort? That thing is confusing. It is much easier to make your own quick sort - especially if you do a templated one.
    My Website

    "Circular logic is good because it is."

  6. #6
    Registered User matheo917's Avatar
    Join Date
    Sep 2001
    Posts
    279
    there's a little problem with you assigning...

    temp = student[temp1].Id;

    you are assigning an (i assume ID is) integer to a stucture....
    this is not going to work b/c the compiler doesn't know how to assign integers to structures, or structures to another structures....you have to teach it how.....you have to overload the
    (operator=).... the question is....do you know how to do operator overloading....????

    hmmm

    Regards,
    matheo917

  7. #7
    Registered User matheo917's Avatar
    Join Date
    Sep 2001
    Posts
    279
    here's a program i wrote a while back.... it uses templates....
    take a look at it....maybe it will be helpful to you.....




    /////////////////////////////////////////////////////////////////////////////
    //
    // Author: Matt
    // File: PR_1_page46.cpp

    //
    // Task: Consider a program that will read employee information into an array
    // of structures (or classes), sort the array by employee identification
    // number, write out the sorted array, and compute various satistics
    // on the data, such as the average age of and employee. Write complete
    // specificatons for this problem and design a modular solution.
    // What functions did you identify during the design of your solution?
    // Write specifications, including prconditoins and postconditions,
    // for each function. Implement your solution by using stubs.
    //
    // Result: Have an array of 5 employees, each employee must have and ID
    // number, first and last name, address, and the age.
    // The client will be prompted to input customer's data and his
    // ID number. This program will have a modular solution. And at
    // the end will print to the screen each employee and it's data
    // in a sorted (ascending) order based on ID number.
    //
    /////////////////////////////////////////////////////////////////////////////

    //--------------------------------------------------------------------------
    // Preprocessor directives...

    #include <iostream>
    #include <string>
    #include <cstdlib>
    #include <vector> // For this program I am using a vector
    #include <algorithm>
    using namespace std;

    //--------------------------------------------------------------------------
    // Constant global unchangeable variables...

    const int MaxEmployees = 5;

    //--------------------------------------------------------------------------
    // class (Employee) declaration...

    class Employee
    {

    public:

    int ID; // public access data member...
    // Automatic inline functions, less typing
    void SetAge(int ItsAge){Age = ItsAge;}
    int GetAge() const {return Age;}
    void SetName(string ItsName) {Name = ItsName;}
    string GetName() const{return Name;}
    void SetAddress(string ItsAddress) {Address = ItsAddress;}
    string GetAddress() const {return Address;}
    // Outline function. This function will be passed as an argument to the
    // for_each() to calculate the sum. I calculated the average externally
    // to the classes; I only used the average age in the main function and
    // for display purposes only.
    friend bool compare_id(const Employee &emp1, const Employee &emp2);
    private:
    int Age;
    string Name;
    string Address;

    };

    bool compare_id(const Employee &emp1, const Employee &emp2)
    {
    if(emp1.ID < emp2.ID)
    return true;
    else
    return false;

    }

    template<class _T> class Sum
    {
    public:
    Sum(): Total(0){}
    void operator()(const _T &x){Total += x.GetAge();}
    int total() const {return Total;}
    private:
    int Total;
    };

    //---------------------------------------------------------------------------
    // (Display) function...
    //
    // Precondition: This function sort an array of employee objects...
    //
    // Postcondition: This function will sort an array of employee objects based
    // on the ID numbers in the ascending order, after that it will
    // print to the screen each employee's data in appriopriate
    // order...
    //
    // Arguments: It will receive an array of employees as a prameter...
    //

    void Display(const Employee &Waiter)
    {

    cout << "Employee ID # : " << Waiter.ID << endl;
    cout << "Employee name : " << Waiter.GetName() << endl;
    cout << "Employee age : " << Waiter.GetAge() << endl;
    cout << "Employee address : " << Waiter.GetAddress() << endl;

    cout << endl;


    }


    //---------------------------------------------------------------------------
    // First function to be executed...
    // Creates 5 employees and initializes their values...

    int main()
    {

    // Since you are creating an array of the Employee class, it does not make
    // sense for each class to have an average age because it is a value that
    // represents the statistics of a group of individuals.
    vector<Employee>Waiter(MaxEmployees);
    Sum<Employee>totalAge;
    string str[MaxEmployees]; // Array of name strings...

    str[0] = "dsafsd";
    str[1] = "weesds";
    str[2] = "bffgawww";
    str[3] = "wwwwaaaa";
    str[4] = "Kriswwww";

    Waiter[0].ID = 202;
    Waiter[0].SetAge(21);
    Waiter[0].SetName(str[0]);
    Waiter[0].SetAddress("21 Stein Ave.");


    Waiter[1].ID = 404;
    Waiter[1].SetAge(40);
    Waiter[1].SetName(str[1]);
    Waiter[1].SetAddress("100 Main St.");


    Waiter[2].ID = 303;
    Waiter[2].SetAge(21);
    Waiter[2].SetName(str[2]);
    Waiter[2].SetAddress("56 Mt.Pleasant Ave.");

    Waiter[3].ID = 505;
    Waiter[3].SetAge(27);
    Waiter[3].SetName(str[3]);
    Waiter[3].SetAddress("5820 N. Nagle St.");

    Waiter[4].ID = 101;
    Waiter[4].SetAge(18);
    Waiter[4].SetName(str[4]);
    Waiter[4].SetAddress("21 Stein Ave.");


    // Here is where all the action takes place. Pay
    // particular attention to sort() and for_each().
    sort(Waiter.begin(),Waiter.end(),compare_id);
    for_each(Waiter.begin(),Waiter.end(),Display);
    totalAge = for_each(Waiter.begin(),Waiter.end(),totalAge);
    cout << "\nThe average age is "
    << static_cast<int>(totalAge.total() / MaxEmployees) << endl;
    system("pause"); // pauses the system and asks
    // a client to press <Enter>
    // in order to continue the
    // the program which in fact
    // will terminate the program..
    return 0;
    }




    good luck

    Regards,
    matheo917

    ps. be careful, don't use someone else's code unless you fully understand it and can explain how it works.....

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Have you ever tried to use the standard libraries version of the quick sort?
    Yes - dead easy - after a few attempts

    Or
    #include <algorithm>
    It has several sorts IIRC
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Aug 2001
    Posts
    101
    Or
    #include <algorithm>
    It has several sorts IIRC
    Yes, in essence:
    Code:
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    struct myStruct {
        int key;
        double data;
        bool operator<(const myStruct& r) const { return key < r.key; }
    };
    
    template <typename T> int arrayElements(const T& r) {
        return sizeof r / sizeof *r;
    }
    
    int main() {
        int i;
        myStruct myStructArray[] = {
            {  5,  5.1 },
            {  1,  6.2 },
            {  6,  2.2 },
            { -1, 50.0 }
        };
    
        for(i = 0; i < arrayElements(myStructArray); ++i) {
            cout << myStructArray[i].key << ' ' << myStructArray[i].data << endl;
        }
    
        sort(myStructArray, myStructArray + arrayElements(myStructArray));
        cout << endl;
    
        for(i = 0; i < arrayElements(myStructArray); ++i) {
            cout << myStructArray[i].key << ' ' << myStructArray[i].data << endl;
        }
    }
    Which is more C++ than qsort, in my humble opinion. It's also more flexible, since sort works on any object that behaves like an array.
    - lmov

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Array Sorting problem
    By ___________ in forum C++ Programming
    Replies: 4
    Last Post: 07-22-2008, 12:17 AM
  2. better way to scanf of a array of structs member?
    By stabu in forum C Programming
    Replies: 3
    Last Post: 07-17-2008, 04:51 PM
  3. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  4. Replies: 12
    Last Post: 12-06-2005, 08:30 PM
  5. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM