Thread: simple int sort

  1. #1
    Used Registerer jdinger's Avatar
    Join Date
    Feb 2002
    Posts
    1,065

    simple int sort

    I've never done any sorting before and I've reached the point in
    my game's development that I need to sort the units based on
    their current map Y coordinate (a long) for proper blitting order.

    I played around with my pen and notepad and came up with a
    very simple algorithm to sort them.

    I've tested it in the game and it works out fine. The only problem
    (and it may not even be a problem) is that it just seems too
    easy) . I know that may sound crazy but I just wanted to get
    some input to see if anyone sees any possible problems I may
    have missed.

    Code:
    //sample code//
    //CBot is an object (class) that represents units in the game
    ////global declaration//
    CBot cbot[12], *pcbot[12], *pcbottemp;
    int i, j;
    
    ////at game/level start, initialize the pcbot array with the values
    ////contained in their cbot array counterparts
    for(i=0;i<12;i++)
    {
        pcbot[i]=&cbot[i];
    }
    
    ////right before the main game loop, sort based on map Y value
    for(i=0;i<12;i++)
    {
       for(j=0;j<12;j++)
       {
          if(pcbot[i]->ptMap.y<pcbot[j]->ptMap.y)
          {
            pcbottemp=pcbot[i];
            pcbot[i]=pcbot[j];
            pcbot[j]=pcbottemp;
          }
       }
    }
    Thanks in advance!

    Jason
    Last edited by jdinger; 08-05-2002 at 12:30 AM.

  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
    > if anyone sees any possible problems I may have missed.
    Functionally, nothing - but you've just re-invented bubble sort, which is about the worst there is in terms of performance.

    It's not too noticeable with small arrays, but if you were to go to 100 or 1000 elements, it would really start to hurt.

    Did you know that qsort() is already provided in stdlib.h

    For sort comparisions, see
    http://www.cs.ubc.ca/spider/harrison...ting-demo.html

  3. #3
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    Here is another link that contains a couple of sorting algorithms. Also, it has visual displays.

    http://ciips.ee.uwa.edu.au/~morris/Y...10/ds_ToC.html

  4. #4
    Used Registerer jdinger's Avatar
    Join Date
    Feb 2002
    Posts
    1,065
    Thanks for the info and link, Salem, and thanks for the link, gg4.

    As far as my current project (a game with a 24 month dev cycle, currently in month 6) the design is concrete as far as the number of units per team (human and ai). So, the maximum number of units to be sorted would be 20. I haven't yet (and don't forsee) any performance issues with the generic little bubble sort.

    As a matter of fact I have updated my sort algorithm to sort all of the units (both CPOW and CBot) by copying their data into an array of pointers to CTrpr objects (their shared base class), then sorting the CTrpr array and running the clip/blit routine from that array (the clipping/blitting routines are defined in the base class).

  5. #5
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    if you know that it is always positive integers, look into RADIX sort. Its about the fastest you'll get.

  6. #6
    Unregistered
    Guest
    but hey, you can always play around with the sort functions to meet certain problem scenarios.

  7. #7
    Unregistered
    Guest
    Why reinvent a wheel? Especially since your wheel is square, and the free one's are generally round...

    Code:
    vector<int> vec;
    
    // insert some integers
    copy(istream_iterator<int>(cin), istream_iterator(), back_inserter(vec));
    
    // sort them (worst case: N*N, best case: N*log(N)
    sort(vec.begin(), vec.end());
    
    // Or:
    // sort(vec.begin(), vec.end(), greater<int>());
    // Or:
    // sort(vec.begin(), vec.end(), less<int>());
    
    // Or
    // "N*log(N)*log(N) algo that improves toward N*log(N) when
    // the system has sufficient memory" - Stroustrup
    // stable_sort(vec.begin(), vec.end());
    
    // display results
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout));

  8. #8
    Unregistered
    Guest
    To avoid any complaints of half-baked code...

    Code:
    #include <iterator>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <functional>
    using namespace std;
    
    int main()
    {
    vector<int> vec;
    
    // insert some integers
    cout<<"Enter integers (Ctrl-Q to quit): ";
    copy(istream_iterator<int>(cin), istream_iterator(), back_inserter(vec));
    
    // sort them (worst case: N*N, best case: N*log(N)
    sort(vec.begin(), vec.end());
    
    // Or:
    // sort(vec.begin(), vec.end(), greater<int>());
    // Or:
    // sort(vec.begin(), vec.end(), less<int>());
    
    // Or
    // "N*log(N)*log(N) algo that improves toward N*log(N) when
    // the system has sufficient memory" - Stroustrup
    // stable_sort(vec.begin(), vec.end());
    
    // display results
    cout<<"Results: ";
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout));
    
    return 0;
    
    }

  9. #9
    Used Registerer jdinger's Avatar
    Join Date
    Feb 2002
    Posts
    1,065
    Isn't the STL a bit slow for game developement though? I've got limited experience with STL, but I've been told it's slow.

  10. #10
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    optimization is picked up in use of correct algorithms and good memory allocation technique. STL is fairly optimized for certain applications so it depends on what you are trying to do in a particular piece of code. Since you are talking about Z depth sorting I would suspect that Radix is your fastest (has to be positive integers) but quicksort might be your best bet. Unregistered posted a pretty good STL example that I don't think would be too slow for your game.

    Myself, I'd look at throwing away the negatives (provided they are behind you in your coord system) and using Radix

  11. #11
    x4000 Ruski's Avatar
    Join Date
    Jun 2002
    Location
    Outer Space!
    Posts
    542
    Didnt read anything from above yet.. how bout Bubble Sort?
    what does signature stand for?

  12. #12
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Bubble sort aint no good Bubba. Read about O'Noation, I think it's called. It explains the amount of time the algorithm takes and it's growth rate.
    Code:
    int i, ii;
    for ( i = 0; i < SIZE; i++)
    {
     // S ..L...O.......W
      for(ii = i + 1; ii < SIZE; ii++)
      {
        if (arr[i] < arr[ii])
        {
          int temp = arr[i];
          arr[i] = arr[ii];
          arr[ii] = temp;
        }
       }
    }

  13. #13
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    Why don't you just use qsort? It is standard and is quite fast.

  14. #14
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    Radix! Radix! Radix!

    He's doing integer sorting, the choice is obvious if you know how Radix and Quicksort both work!

    Radix! Radix! Radix!

  15. #15
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Heh - there's plenty of choice. Let jdinger finish the program, and if it needs optimising, then this is one area which would be simple to replace with the most appropriate algorithm.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Debug Error Really Quick Question
    By GCNDoug in forum C Programming
    Replies: 1
    Last Post: 04-23-2007, 12:05 PM
  2. Replies: 2
    Last Post: 03-24-2006, 08:36 PM
  3. Need help understanding info in a header file
    By hicpics in forum C Programming
    Replies: 8
    Last Post: 12-02-2005, 12:36 PM
  4. Switch/case Problems (long code in post)
    By Wraithan in forum C++ Programming
    Replies: 2
    Last Post: 12-01-2005, 06:40 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM