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 值将根据迭代次数而变化。

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