# simple int sort

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 08-05-2002
jdinger
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;       }   } }```

Jason
• 08-05-2002
Salem
> 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
• 08-05-2002
golfinguy4
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
• 08-05-2002
jdinger
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).
• 08-05-2002
FillYourBrain
if you know that it is always positive integers, look into RADIX sort. Its about the fastest you'll get.
• 08-05-2002
Unregistered
but hey, you can always play around with the sort functions to meet certain problem scenarios.
• 08-06-2002
Unregistered
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));```
• 08-06-2002
Unregistered
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; }```
• 08-06-2002
jdinger
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.
• 08-06-2002
FillYourBrain
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
• 08-06-2002
Ruski
Didnt read anything from above yet.. how bout Bubble Sort?
• 08-06-2002
Troll_King
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;     }   } }```
• 08-06-2002
golfinguy4
Why don't you just use qsort? It is standard and is quite fast.
• 08-06-2002
FillYourBrain