Sorting an array by using a linked list

[dnulho]

I have two arrays of characters that I want to combine and sort according to an internal variable (init) using a forward-iterating linked list. The two arrays must stay separated, as one of the arrays (the enemies) is contained within the object (encounter), the other is passed in via pointers (the players). The array inside the object will be destroyed later (when the encounter is over and the enemies are hopefully dead) while the one that is passed in must survive to be passed into other objects at a later time (the next encounter). My thought is to sort each array by linked list separately first, then iterate through and combine the two lists, But I have no idea how to do this and no support IRL. Any suggestions would be much appreciated.

// DECLARATION OF CLASSES //

class character{
public:
    character();                    // Constructor
    bool operator== (character);    // use when comparing init of objects
    bool operator< (character);
    bool operator> (character);
    string getname ()const ;        // return name of object
    string getname ();
    int getinit () const;           // return init of object
    int getinit ();
    void set_init (int a);          // set init of object to 'a'
    void heal_full();               // max out hp and 0 nl dam
    void heal(int amt);             // modify hp by given amount
    void heal_nl (int amt);         // heal nl dam by given amount
    void dam_nl (int amt);          // give nl dam by given amount, checks for disabled or unconscious state.
    int getHP();                    // return current hp
    int getnlDam();                 // return nl dam
    void SetnMob (character* nmob); // Sets next mob
    character* GetnMob ();          // Gets the address of next mob.

private:
    string name;            // name of character
    int mHP;                // max hit points
    int HP;                 // current hit points
    int nlDam;              // amount of non lethal damage object currently has
    int init;               // initiative of character
    character* nextMob;     // points to next mob to iterate to
};
class encounter{
public:
    encounter (character*, int);        // Constructor
    void listFull ();
private:
    int ENEMIES;                        // number of enemies in this encounter
    character enemy[];                  // array of all enemies in encounter
    character* holding[];               // array of pointers to all mobs currently holding turn
    character* player;                  // pointer to array of player mobs
    character* firstMob;                // pointer to highest init mob
    void setInits (character ary[], int arraySize);
    character* sortAryLL (character* ary[], int arraySize);
};

Full code at: http://ideone.com/CSJXdz

[Duthomhas]

Sort the separate lists first, then 'sort' them together.

In both cases, the way to do it is via mergesort.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/mergesort/

You will need two versions of the algorithm, of course, to handle the second case of not actually combining the lists...


Another consideration is to make yourself an array of pointers to the nodes in the list, and sort that (based upon a proper dereference comparison functor) using the std::sort() method. You can reorder the original linked lists from the sorted array of pointers at any time.


Good luck!