c++ - 什么是排序算法(以及它在 GPU 上运行的效率如何)

Question

我已经实现了一个用于排序像素的着色器:

void main()
{
    vec4 renderedImagePixel = texture2D(CalculatedImage,v_texcoord);

    if(int(numRenderPass) == int(v_texcoord.y*float(height)) && fbo ){

        vec2 coordTHIS = vec2(v_texcoord.x,v_texcoord.y-1.0/float(height));
        float THIS = unpack(texture2D(CalculatedImage,coordTHIS));
        renderedImagePixel = texture2D(CalculatedImage,coordTHIS);

        if(sieveCycle == true){ //even Cycle

            //Even cell
            if(mod(int(v_texcoord.x*float(width)),2) == 1){
                //CHANGES IN CODE HERE
                vec2 coordTHAT = vec2(v_texcoord.x+1.0/float(width),v_texcoord.y-1.0/float(height));
                float THAT = unpack(texture2D(CalculatedImage,coordTHAT));

                //CHANGES IN CODE HERE
                if( THIS > THAT ){
                    renderedImagePixel = texture2D(CalculatedImage,coordTHAT);
                }
            }else{
            //Odd cell
                //CHANGES IN CODE HERE
                vec2 coordTHAT = vec2(v_texcoord.x-1.0/float(width),v_texcoord.y-1.0/float(height));
                float THAT = unpack(texture2D(CalculatedImage,coordTHAT));

                //CHANGES IN CODE HERE
                if( THAT > THIS ){
                    renderedImagePixel = texture2D(CalculatedImage,coordTHAT);
                }
            }

        }else{ //odd cycle

            //Even cell
            if(mod(int(v_texcoord.x*float(width)),2) == 0){
                //CHANGES IN CODE HERE
                vec2 coordTHAT = vec2(v_texcoord.x+1.0/float(width),v_texcoord.y-1.0/float(height));
                float THAT = unpack(texture2D(CalculatedImage,coordTHAT));

                //CHANGES IN CODE HERE
                if( THIS > THAT ){
                    renderedImagePixel = texture2D(CalculatedImage,coordTHAT);
                }
            }else{
            //Odd cell
                //CHANGES IN CODE HERE
                vec2 coordTHAT = vec2(v_texcoord.x-1.0/float(width),v_texcoord.y-1.0/float(height));
                float THAT = unpack(texture2D(CalculatedImage,coordTHAT));

                //CHANGES IN CODE HERE
                if( THAT > THIS ){
                    renderedImagePixel = texture2D(CalculatedImage,coordTHAT);
                }
            }

        }
    }

    gl_FragColor = renderedImagePixel;

}

现在我想知道它的效果如何？

我的想法是，如果在一个循环中计算每个像素，那么算法在最坏情况下应该是 O(n)。这是正确的吗。以防它只是冒泡排序的派生词。

这是排序示例的图像:

Answer 1

您正在实现 sorting network并使用了奇偶排序算法。

在输出完全排序之前，这需要 O(n) 次迭代。

然而，更高效的算法存在，如 bitonic sort .这只需要 O(log² n) 迭代。着色器将变得更加复杂，因为 other 值将根据迭代次数发生变化。

您可以通过使用另一个纹理来简化它，其中将对另一个索引进行编码以及是否采用最小值或最大值。