Skip to main content
gamedev.net
🔒 Locked

Sorting a simple number array

Started by Koetjeboe Jan 3, 2003 at 12:40 PM 6 replies 500+ views
Original Post
Koetjeboe
Koetjeboe
Hi, I need to sort a really simple array full of y coords really fast, what would be the fastest algorithm to use? Quicksort? It''s a rather small array to, about 10 to 999 int numbers, the only problem is that I need to sort it really quick. Thanks
dalleboy
dalleboy
std::sort(begin, end) or std::sort(begin, end, pred)


  

#include <algorithm>

#include <iostream>

// Return whether first element is greater than the second

bool MyGreater(int elem1, int elem2)
{
   return elem1 > elem2;
}

int main()
{
   int array[10] = { 5, 1, 3, 9, 0, 2, 4, 6, 7, 8 };
   int ix;

   std::sort(array, array + 10);
   std::cout << "Sorted = ( ";
   for (ix = 0; ix < 10; ++ix)
   {
      std::cout << array[ix] << " ";
   }
   std::cout << ")" << std::endl;

   std::sort(array, array + 10, MyGreater);
   std::cout << "Sorted (MyGreater) = ( ";
   for (ix = 0; ix < 10; ++ix)
   {
      std::cout << array[ix] << " ";
   }
   std::cout << ")" << std::endl;
}


EDIT1: Added example code.


Update GameDev.net system time campaign: 'date ddmmHHMMYYYY'

[edited by - dalleboy on January 3, 2003 2:00:42 PM]
rm3
rm3
I did the same thing (having to sort a bunch of y coords) for clipping in a tile engine. I used quick sort, but a question to dalleboy: If std sort is faster than a quick sort I write, how can I use it with an array of structures, or do I have to put the specific data members from the structures I want to sort into an int array first, then sort that.

Armitage
Armitage
std::sort usually relies on quick sort and swaps to heap sort if it notices that things are going badly (intro sort). It's not the 'fastest' - but should be fast enough. And more memory efficient than faster alternatives.

Oh, and you can always modify your comparison function to something like this:

bool MyGreater(MyStruct* elem1, MyStruct* elem2){   return elem1->intVal > elem2->intVal;}




[edited by - Armitage on January 3, 2003 2:41:32 PM]
A polar bear is a rectangular bear after a coordinate transform.
dalleboy
dalleboy
Read this article about sorting speeds on the C/C++ Users Journal Web Site: The Standard Librarian: Sorting in the Standard Library[^]
Extract from article:

Sorting a vector of 700000 doubles.
  sorting method    t (sec)
            sort    0.971
           qsort    1.732
     stable_sort    1.402
       heap sort    1.282
       list sort    1.993
        set sort    3.194


Extract from article:
"You shouldn't use qsort in new code. It's slower than sort. Its interface is ugly and, because it requires casting, error-prone. Writing a comparison function to pass to qsort can be nontrivial, especially in generic code. You can't use qsort to sort objects with constructors or virtual member functions, or to sort any data structure other than a C array. Although qsort isn't formally deprecated, its only real use is backward compatibility with C."

EDIT1: Added extract from the article.
EDIT2: Added another extract from the article.

Update GameDev.net system time campaign: 'date ddmmHHMMYYYY'


[edited by - dalleboy on January 3, 2003 2:53:47 PM]
Koetjeboe
Koetjeboe
Hmm, thanks for clearing that speed issue up, thanks for all the replies

But lets say I need to sort an array like 'int something[xx]' but I want to know how the xx is changed, how do I keep track of that?

This sort of describes what I want to do. I want to sort a class npc[ i ].y ascending so I can blit them in the correct order. But I cant 'sort' that array because its way to big (with all the members and stuff). So I need to track in what order I need to blit them.

[edited by - Koetjeboe on January 3, 2003 3:11:00 PM]
dalleboy
dalleboy
Something like this?

  
struct HugeStruct
{
   ...
   int valueToSortBy;
};

struct SortStruct
{
   int valueToSortBy;
   int originalPosition;
};

bool Sorter(const SortStruct& e1, const SortStruct& e2)
{
   return e1.valueToSortBy < e2.valueToSortBy;
}

void foo()
{
   const int NUM_ELEMENTS = 10000;
   HugeStruct hugeArray[NUM_ELEMENTS] = something();
   SortStruct sortArray[NUM_ELEMENTS];
   int i;

   for (i = 0; i < NUM_ELEMENTS; ++i)
   {
      sortArray[i].valueToSortBy = hugeArray[i].valueToSortBy;
      sortArray[i].originalPosition = i;
   }

   std::sort(sortArray, sortArray + NUM_ELEMENTS, Sorter);

   for (i = 0; i < NUM_ELEMENTS; ++i)
   {
      Blit(hugeArray[sortArray[i].originalPosition]);
   }
}


Or you could sort an array of the pointers to the huge objects...


Update GameDev.net system time campaign: 'date ddmmHHMMYYYY'

[edited by - dalleboy on January 3, 2003 3:40:38 PM]
Koetjeboe
Koetjeboe
-__- just make a struct for it, ofcourse Thanks alot, it works like a charm

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.