# Sorting a vector using array version of quick sort

I'm coding a simple rendering engine using OpengGL and I wrote a class that manages a particle system. The class creates the particles and pushes them into a vector to be used by a renderer to draw them on screen. I need to order the particles from the farthest to the nearest to the camera (in order to solve problems with alpha blending and depth, having disabled depth testing for transparency), so I tried with the following code:

void ParticleRenderer::render()
{
// prepare renderer
.....
// update particle state (position,ecc..) and remove it if necessary
// update returns a bool indicating if particle is still alive
while (it != mParticles.end())
{
if (!(*it)->update())
{
delete *it;
it = mParticles.erase(it);
if (it == mParticles.end())
break;
else
continue;
}
it++;
}
if (mParticles.size() > 0)
sortParticles(&mParticles[0], 0, mParticles.size() - 1);
for (Particle *particle : mParticles)
{
.....
// render particle
.....
std::cout << getCameraDistance(particle) << std::endl;
}
std::cout << "*************************************" << std::endl;
mShader.unuse();
glDisable(GL_BLEND);
}

void ParticleRenderer::sortParticles(Particle **particles, int low, int high)
{
if (low >= high)
return;
Particle *temp = particles[low];
while (true)
{
while (compareParticles(temp, particles[high]) >= 0 && low < high)
high--;
if (low == high)
break;
else
particles[low++] = particles[high];
while (compareParticles(temp, particles[low]) < 0 && low < high)
low++;
if (low == high)
break;
else
particles[high--] = particles[low];
}
particles[high] = temp;
int middle = high;
sortParticles(particles, low, middle - 1);
sortParticles(particles, middle + 1, high);
}

double ParticleRenderer::compareParticles(Particle *particle1, Particle *particle2)
{
return  getCameraDistance(particle1) - getCameraDistance(particle2);
}

double ParticleRenderer::getCameraDistance(Particle *particle)
{
glm::vec3 distance = mCamera.getPosition() - particle->getPosition();
return glm::length(distance);
}


but what I get on the console are all unsorted particles (the cout statement) and of course I have problems when the particles are rendered on screen. Am I missing something?

I know I could use std::sort and the STL algorithms, but since I'm learning I would like to know what I am doing wrong.

• did you try with std::sort? did you try your algorithm with a array of just numbers (eliminate where the error could be coming from)? – ratchet freak Jul 4 '17 at 8:59
• @ratchetfreak yes, I've tried with a vector of ints (just to see if something was wrong with accessing vector elements as a contiguous array, but I learned that it's ok) and it works... so I don't know where's the error – Luca Jul 4 '17 at 9:17

## 1 Answer

Actually my recursive quicksort was wrong. While testing with a vector of ints I used a slightly different version, in wich the partitioning of the array was performed in another function. This version is flawed since I'm passing to the recursive quicksort (divide and conquer I understand..) the same high and low indices that are used in the algorithm...so I'm passing the same index...hence no sorting.