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

> 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

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

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).

if you know that it is always positive integers, look into RADIX sort. Its about the fastest you'll get.

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

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));

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;

}

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.

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

Didnt read anything from above yet.. how bout Bubble Sort?

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;
    }
   }
}

Why don't you just use qsort? It is standard and is quite fast.

Radix! Radix! Radix!

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

Radix! Radix! Radix!

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.