Sign in to follow this  
Jack Lol

Quicksorting vectors with a struct type

Recommended Posts

I have this quicksort function (If you have a better one then post it away): void quickSort(int numbers[], int array_size) { q_sort(numbers, 0, array_size - 1); } void q_sort(int numbers[], int left, int right) { int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = numbers[left]; while (left < right) { while ((numbers[right] >= pivot) && (left < right)) right--; if (left != right) { numbers[left] = numbers[right]; left++; } while ((numbers[left] <= pivot) && (left < right)) left++; if (left != right) { numbers[right] = numbers[left]; right--; } } numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot) q_sort(numbers, left, pivot-1); if (right > pivot) q_sort(numbers, pivot+1, right); } I want it to sort this vector by 'prio': struct sprEntry { bgeSprite *spr; bgeVector pos, size; UINT prio; DWORD Colors[4]; float rotation; bool visible; bool del; }; std::vector<sprEntry*>m_sprites; So that if I have 3 elements in the vector: elmnt1->prio = 2 elmnt2->prio = 3 elmnt3->prio = 1 After sorting it will be: elmnt3->prio = 1 elmnt1->prio = 2 elmnt2->prio = 3 Thanks in Advance.

Share this post


Link to post
Share on other sites

typedef boost::shared_ptr<sprEntry> spritePtr;

std::vector<spritePtr> m_sprites;

bool is_lower_priority(spritePtr const & lhs, spritePtr const & rhs) {
return lhs->prio < rhs->prio;
}

std::sort(m_sprites.begin(), m_sprites.end(), is_lower_priority);
}


Much better, if you ask me [wink].

Cheers,
Pat.

Share this post


Link to post
Share on other sites

struct sprEntrySort
{
bool operator()(sprEntry*& spr1, sprEntry*& spr2)
{ // define how to compare your sprEntry's here
return spr1->prio < spr2->prio;
}
};

std::sort(m_sprites.begin(), m_sprites.end(), sprEntrySort());

Share this post


Link to post
Share on other sites
I want to use my function if it's possible, and I just want to do what it does with vectors that have structs, like I showed above.
Oh and what algorithm does std::sort use?

Share this post


Link to post
Share on other sites
Quote:
Original post by Jack Lol
I want to use my function if it's possible, and I just want to do what it does with vectors that have structs, like I showed above.
Oh and what algorithm does std::sort use?


A fast one. It has the potential to be faster than qsort as the compiler can completely inline the call if it chooses to do so.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this