Sort a list in Ascending Order

This is a discussion on Sort a list in Ascending Order within the C++ Programming forums, part of the General Programming Boards category; I have a .txtfile that has these values(4 rows). Now I want to sort this. This list will be sorted ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    383

    Sort a list in Ascending Order

    I have a .txtfile that has these values(4 rows).
    Now I want to sort this.

    This list will be sorted in ascending order First by value 1 and Then by value 2:
    2,3,0
    1,2,0
    2,2,0
    1,3,0

    The output will then look like this:
    (Notice that it first was sorted for the first value and Then by the second value.)

    1,2,0
    1,3,0
    2,2,0
    2,3,0

    How could this be possible to do... I beleive I have to use Arrays in a way to do this but dont really know how.
    Last edited by Coding; 01-21-2008 at 09:18 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    Well, at the very least you could store the values in a POD struct, e.g.,
    Code:
    struct ValueList
    {
        int values[3];
    };
    Then you define a predicate to make the comparison by the first value and then by the second value:
    Code:
    class ValueListComparator
    {
    public:
        bool operator()(const ValueList& x, ValueList& y) const
        {
            return x.values[0] < y.values[0]
                || (x.values[0] == y.values[0] && x.values[1] < y.values[1]);
        }
    };
    With these in place, you can just use the sort generic algorithm from <algorithm> with say, a std::vector<ValueList> named values:
    Code:
    std::sort(values.begin(), values.end(), ValueListComparator());
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    383
    This was very difficult for me to understand. Almost only new functions to me :-)
    I beleive I understand the last line:
    Code:
    std::sort(values.begin(), values.end(), ValueListComparator());
    If I first ask what is happening exactly for:

    Code:
    struct ValueList
    {
        int values[3];
    };
    I belive int value[3] is a normal array that I for example in this case store the first row for 2,3,0 in each place but what is the difference with struct ValueList, what is happening here. Does this store all 4 rows in a kind of structure ?
    Last edited by Coding; 01-21-2008 at 10:04 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    I belive int value[3] is a normal array that I for example in this case store the first row for 2,3,0 in each place but what is the difference with struct ValueList, what is happening here. Does this store all 4 rows in a kind of structure ?
    No, it is intended to represent one line of values in your input file. You could just as easily have written it as:
    Code:
    struct ValueList
    {
        int value1;
        int value2;
        int value3;
    };
    You may also want to make this into a full fledged class with private member variables and public member functions, but for this example I have chosen to make it a plain old data (POD) struct that just has public member variables.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    383
    okay I see... then I got a bit more logic in it.. I will try to experiment with this and see what I can do...
    Thanks..

  6. #6
    Registered User
    Join Date
    Dec 2007
    Posts
    383
    I am a bit stuck with this. As my example only consists of 4 rows but in reality it could consist of more than thousands of rows I beleive I can use vector 2D arrays for this, that I know how these works ?

    I can manage for the example to store the values in:

    Code:
    Values[3][2];
    When this is stored, what is the next step from here. ?
    (I take a chance that I can begin a solution like this)

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    As my example only consists of 4 rows but in reality it could consist of more than thousands of rows I beleive I can use vector 2D arrays for this, that I know how these works ?
    That's not a problem for the generic sort algorithm to handle, of course.

    When this is stored, what is the next step from here. ?
    The next question you will probably be asking is how to read in the data from the file when it could have thousands of lines and you do not know exactly how many it will be.

    As such, follow my example. Use a struct/class to model a line of data, and then use a vector to store the lines.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    383
    I have a method to read in the data into the arrays with Getline(file, Data1, ',') etc...
    This is not a problem.

    So how do I continue from here when all data is stored in the vector ex:

    Values[3][2];

    Sorry for taking it so slowly... I beleive I have to understand this step by step...
    Thanks...

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    So how do I continue from here when all data is stored in the vector ex:

    Values[3][2];

    Sorry for taking it so slowly... I beleive I have to understand this step by step...
    Sure. Just a moment here though: just what is Values[3][2]?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Dec 2007
    Posts
    383
    I will read in the four lines in the file with getline into 2D vector while using a count = count + 1; for each row it is going through(using a while loop) and from here I will put the values like this:
    Code:
    Values[count][1 2 or 3];
    I beleive the maximum of rows that will be readed in the array will be 1000 so a declaration of 1100 will be a good marginal for this:
    Code:
    std::vector<std::vector<int> > Values(1100, std::vector<int>(10));

    2,3,0
    1,2,0
    2,2,0
    1,3,0

    So when the file is readed with getline etc... I will have stored the above values into this array:

    Values[3][2];

    EX: Values[0][0] represents: The First "2" , Values[0][1] represents: "3" in the same line etc...
    Last edited by Coding; 01-21-2008 at 11:40 AM.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    Great, we're on the same page at least. However, since you only have 3 values per line, it should be:
    Code:
    std::vector<std::vector<int> > Values(1000, std::vector<int>(3));
    Anyway, the next step is that you want to sort this vector after reading in the input. So you just use std::sort, but a catch here is that you want to compare based on some special criteria. As such, a solution is to write a function object to be a predicate for the comparison.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Dec 2007
    Posts
    383
    Yes I understand.. this is the catch so you considered a solution like this:

    Code:
    class ValueListComparator
    {
    public:
        bool operator()(const ValueList& x, ValueList& y) const
        {
            return x.values[0] < y.values[0]
                || (x.values[0] == y.values[0] && x.values[1] < y.values[1]);
        }
    };
    Code:
    std::sort(values.begin(), values.end(), ValueListComparator());
    The problem here is that I dont really understand whats going on exactly in the code. I dont know if it will look different now as we have the already stored array values[3][2] ?

    For the code I understand that the catch is ValueListComparator() that is the extra here. Like some criterias/rules that is made for the sorting.

    Though I dont really understand the logics like:
    bool operator()
    the x and y values (What does these represent in the case values[3][2];

    It is kind of diffus for me yet...
    Last edited by Coding; 01-21-2008 at 11:56 AM.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    The basic idea is this: suppose we have a function that takes two arguments of the same type and returns a bool if one argument is considered "less than" the other. This basically describes a predicate, a comparator.

    Now, suppose we have a class that overloads operator(). If we have an object of this class named x, x() looks like a call of a function named x, but actually it is a member function call of an object named x. This is the idea behind function objects - they can be used with the same syntax as functions, but actually they are objects.

    So, the idea here is to come up with some boolean expression that describes our notion of "less than". In this case, we say that a line of values is "less than" another line of values if the first value of one line is less than the first value of the other line, or the first values are equal but the second value of the first line is less than the second value of the second line. This mouthful of words is expressed as:
    Code:
            return x.values[0] < y.values[0]
                || (x.values[0] == y.values[0] && x.values[1] < y.values[1]);
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Dec 2007
    Posts
    383
    I think I am following you here now.
    So I have some questions to be sure.

    For the line:
    Code:
       
    bool operator()(const ValueList& x, ValueList& y) const
    ValueList... should this be changed to another name as we havent declared a ValueList or is it ment
    to do like this:


    Code:
    struct ValueList
    {
        std::vector<std::vector<int> > Values(1000, std::vector<int>(3));
    };
    Last edited by Coding; 01-21-2008 at 12:26 PM.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,647
    ValueList... should this be changed to another name as we havent declared a ValueList or is it ment
    to do like this:
    You should probably change it to:
    Code:
    bool operator()(const std::vector<int>& x, const std::vector<int>& y) const
    Putting the entire vector of vectors into a struct is something different: my suggestion earlier was equivalent to putting a vector into the struct, and then manipulating a vector of structs.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 01:48 PM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  4. sort my linked list alphabetically
    By alfd6z in forum C Programming
    Replies: 2
    Last Post: 12-14-2002, 12:33 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21